- 締切済み
クイックソート
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- sakusaker7
- ベストアンサー率62% (800/1280)
あー、すみません。 ちょっと読み違えてました。 > 9 1 8 5 3 4 2 6 7 まずここから、右端の7をpivotに選択しました。 9 1 8 5 3 4 2 6 6 1 8 5 3 4 2 9 >=7 の 9 と <7 の6を交換 6 1 2 5 3 4 8 9 >=7 の 8 と <7 の2を交換 とここまではいいのですよね? ここまでで、7以上と7未満との分割は終わったので、 次は分割されたそれぞれの部分に対して同じ手順を繰り返します。 つまり、 6 1 2 5 3 4 と 8 9 7 とを別々のものとして処理します。 [7未満の配列][7以上の配列] と分かれているので、それぞれが昇順になれば 全体としても昇順に並んでいる。 ということなんですけどこういう説明でわかりますか? クイックソート http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html で紹介されているやり方でいうと、 質問者さんは int k=partition(a,i,j,a[p]); この partition の呼び出しから返ってきたところまではできたので、続いて quickSort(a,i,k-1); quickSort(a,k,j); という二つの手順をすればよいのです。
- sakusaker7
- ベストアンサー率62% (800/1280)
>どうしたら昇順に導けますか？ それ以前にどういう手順で処理したらこういう結果になるのか見当がつきません。 pivot をどう選択して、どのように分割したのか説明してもらえませんか?
補足
まずpivotを7にします。そしてleftPtrが7よりでかいとき、そしてrightPtrが7より小さいときに入れ替えしてやるという方法でやりました。
関連するQ&A
- クイックソートって？？
どこに載せればいいのかわからなかったので ここに載せてみました。 クイックソートってなんですか？？ 簡単なアルゴリズムで答えてください！？ （自分も何言っているのかわらない？？） 簡単に言えばクイックソートってナに？？ です。 よろしくお願いします。 わかるように簡単でね！！
- ベストアンサー
- その他（プログラミング・開発）
- Ｃ言語 クイックソートについて
以下の数字を用いて・・・・ num[10] = {21, 46, 87, 9, 32, 33, 57, 87, 12, 43} クイックソートで整列する時，データの入れ替え状況，配列の内容の変化について，データの入れ替え過程をプログラムでない形で説明をお願いします。アルゴリズムの特徴がわかる説明と入れ替え過程を示してほしいです。 以下の数字を用いてお願いします。 例: ●●で分割: { } ●●で分割: { } ・ ・ ・ ・ 整列後: { }
- 締切済み
- C・C++・C#
- クイックソートについて
下記のソースプログラムのquick_sort_coreの部分がわかりません。 わかる方助けてください。 あとこのソースを降順にした場合の変更点も教えていただけると助かります。 #include <stdio.h> /* printf()利用のため */ #include <stdlib.h> /* rand()利用のため */ #include <time.h> /* clock()利用のため */ #define N 10 /* 整列対象要素数 */ /** * 配列の中身を表示する関数 * @param a 表示する配列 * @param n 配列の要素数 */ void print_array(const int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /** * 整列されているかどうか確認する関数 * @param a 確認対象配列 * @param n 配列の要素数 */ void is_sorted(const int a[], int n) { int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { printf("昇順に整列されていません\n"); return; } } printf("昇順に整列されています\n"); } /** * クイックソートの本体 * @param a 整列対象配列 * @param l 対象の最初の要素番号 * @param r 対象の最後の要素番号 */ void quick_sort_core(int a[], int l, int r) { /* ここを実装する */ } /** * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 * @param a 整列対象配列 * @param n 配列の要素数 */ void quick_sort(int a[], int n) { quick_sort_core(a, 0, n - 1); } int main(void) { int i; int n = N; /* 整列対象要素数 */ int a[N]; clock_t start,end; /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */ for (i = 0; i < n; i++) { a[i] = rand(); /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */ } /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 開始時刻の取得 */ start = clock(); /* クイックソート関数の呼び出し */ quick_sort(a, n); /* 終了時刻の取得 */ end = clock(); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 実行時間の表示 */ printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); return 0; }
- 締切済み
- C・C++・C#
- バブル・ソート、クイック・ソート
N個（N=4,5,6）のデータが全て等しいデータ列（例えばN個の数字全部が1のとき）をバブルソートで並び替えたとき、データの交換回数は何回か。また、同じデータ列をクイックソートで並び替えたときはどうか。 という問題があるのですが、どう比較するのかがわかりません。詳しい方、説明よろしくお願いします。
- 締切済み
- C・C++・C#
- クイックソートしながら重複要素削除アルゴリズム
アルゴリズムが苦手な上、アルゴリズム解説自体C言語ベースで書かれ ている物が多く処理のイメージが沸かずクイックソートもコピペや既存 の関数で処理していて、満足に理解出来ていないのですが。 以下の問題を、お解かりになるかた教えて頂けませんでしょうか？ ■問題 2万件位の数値データの中から重複要素を削除しながら昇順または降順で、 ソートするアルゴリズム(※１) ■条件 BASIC的(※２)な記述やプログラム中のコメントなどの形式でも構いま せん出来るだけ簡単に示して頂けると助かります。 補足 (※１)ソートする際、重複要素を消すともっと処理が早くなるのではと 思ったので。 目的は、処理の速さを求める事と、次回から応用が聞くよ うにソート自体を理解したいのでクイックソートで無くても構いません。 (※２)実際に動かなくても構いません、イメージが掴みやすい方が良いと いう意味でとって下さい。
- ベストアンサー
- その他（プログラミング・開発）
- クイックソートのソート
2 8 7 1 3 5 6 4 という数字が並んでいて ４を基準に左から昇順にクイックソートするとしたら 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 1 7 8 3 5 6 4 (1) 2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4 2 1 3 4 8 7 5 6 8 というふうになりますが (1)の状態は８と７が交換されていますが これは間違いなのでしょうか 教科書に載っていたのですが
- ベストアンサー
- その他([技術者向] コンピューター)
- クイックソート
クイックソートには再帰を使わない方がいいんですか？ 再帰を使わないとすると明示的にスタックで管理することになると思うのですが，整列させたい要素数がバラバラの時はどのようにすればよいですか？
- ベストアンサー
- Visual Basic
- クイックソートの比較回数について
中央値をピボットとするクイックソートで、入力データ数が１０２４で昇順データの場合はＯ(nlogn)の関係より10240回の比較回数が得られる、というのは合っているでしょうか？ ご回答お願い致します。
- ベストアンサー
- C・C++・C#
- 探索・整列アルゴリズムのメリット・デメリットについ
「コンピューターはなぜ動くのか？」の第５章の「アルゴリズムと仲良くなる7つのポイント」のところにて、主な定番アルゴリズムとして、 表5.1 主な定番アルゴリズム (1)ユーグリットの互除去 (2)エラトステネスのふるい (3)線型探索 (4)2分探索 (5)ハッシュ法 (6)バブル・ソート (7)クイック・ソート 上記のアルゴリズムがあり、そのアルゴリズムの用途には (1)最大公約数のアルゴリズム (2)素数のアルゴリズム (3)データ探索のアルゴリズム (4)整列のアルゴリズム 上記のアルゴリズムがありますが、(3)～(4)のアルゴリズムの用途においてのメリット・デメリット ・データ探索のアルゴリズム (3)線型探索 (4)2分探索 (5)ハッシュ法 についてのメリット・デメリット ・整列のアルゴリズム (6)バブル・ソート (7)クイック・ソート についてのメリット・デメリット これらを教えて頂けばと思っております。 よろしくお願いたします。
- 締切済み
- その他([技術者向] コンピューター)
お礼
お返事のほう遅れて申し訳ないですm(__)m 大変よく理解できました。ありがとうございます。