- 締切済み
クイックソートで並べ替え
yama5140の回答
- yama5140
- ベストアンサー率54% (136/250)
No.3 です。 ＞私含めて本人もソースだとかプログラムが一切分かりません。 ＞手順自体は、検索したようで理解しているらしいのですが、回答に自信がないらしく正解を知りたいとのことです。 「Ｃ＆Ｃ＋＋でプログラムし、結果（比較回数）を回答しろ」、ということですね。 でしたらこのコミュニティーには相応しくないのでは・・。 ☆アンケート形式にしちゃえば、ぎりぎりセーフかも。 昇順にソートしたとき、比較○回に１票。 降順にソートしたとき、比較◇回に１票・・とか。 ＞軸要素は先頭の２要素のうち大きいほうとせよ って、対象が、2,4,8,1,6,5,2,7,3,7 となっていることから自明ですよね。 （「先頭」は１つしかないっつうツッコミは無しとして） ☆「軸要素は４とせよ」という記述ではないことから、やはり（様々な条件に対応可能な）プログラムを作る、のが「そもそも」ではないでしょうか。 +++++++++++++++++++++++++++++++++++++ アンケート形式として、年寄りは、 昇順にソートしたとき、比較 15 回に１票。 降順にソートしたとき、比較 16 回に１票。 注：全然自信がありません（まっアンケートだから、「良」として下さい）。 「バブル」なら 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 で固定かなぁ・・？。
関連するQ&A
- バブルソートとクイックソート
まだソートについて勉強し始めたばかりですが バブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対し クイックソートはそれほど増加しないのはなぜでしょうか？？ 検索してみてもプログラムが書いてあってよくわからないので... 根本的なところなのでしょうがどなたか教えてください!
- ベストアンサー
- C・C++・C#
- バブル・ソート、クイック・ソート
N個（N=4,5,6）のデータが全て等しいデータ列（例えばN個の数字全部が1のとき）をバブルソートで並び替えたとき、データの交換回数は何回か。また、同じデータ列をクイックソートで並び替えたときはどうか。 という問題があるのですが、どう比較するのかがわかりません。詳しい方、説明よろしくお願いします。
- 締切済み
- C・C++・C#
- クイックソート
クイックソートには再帰を使わない方がいいんですか？ 再帰を使わないとすると明示的にスタックで管理することになると思うのですが，整列させたい要素数がバラバラの時はどのようにすればよいですか？
- ベストアンサー
- Visual Basic
- アルゴリズムの問題なのですが、マージソートとクイックソートについて教え
アルゴリズムの問題なのですが、マージソートとクイックソートについて教えてください。 数列の(21 99 38 22 15 6)をマージソートで並び変えて、クイックソートでも並び変えたいのです。 マージソートで並び変えた手順は (21 99 38 22 15 6) (下矢印) (21 99 38)(22 15 6) (下矢印) (21 99)(38)(22 15)(6) (下矢印) (21)(99)(38)(22)(15)(6) (下矢印) (21 99)(38)(15 22)(6) (下矢印) (21 38 99)(6 15 22) (下矢印) (6 15 21 22 38 99) となりました。 この時、分割回数と統合回数がともに5なのですが、どう見たら5回なのでしょうか。 分割回数は3で統合回数も3ではないのでしょうか？ クイックソートの方なのですが、 回答は (21 99 38 22 15 6) (下矢印) (15 6)(21)(99 38 22) (下矢印) (6)(15)(21)(22 38)(99) (15と38にした場合) (下矢印) (6)(15)(21)(22)(38)(99) となっていて、 最も効率のよいピボットを選択した場合分割回数は3となっています。 私がやってみたところ (21 99 38 22 15 6) (下矢印) (15 6)(21)(99 38 22) (下矢印) (6)(15)(21)(22)(38)(99) (15と38を選んだ) これではいけないのでしょうか。 長くなりましたが、よろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- クイックソートの考え方？
そこで、クイックソートのアルゴリズムで躓いています。 10,20,11,19,13,17,14,16,15 真中の値 13 を基準値として使う。 左から基準値と比較してより大きい値は 20。 右から基準値と比較して20 の手前までのより小さい値11。 両者を置換。 10,11,20,19,13,17,14,16,15 真中の値 13 を基準値として使って比較。 左から基準値と比較してより大きい値は 20。 右から基準値と比較して20 の手前までのより小さい値はない。 基準値と20とを置換。 10,11,13,19,20,17,14,16,15 真中の値 20 を基準値として使って比較。 左から基準値と比較してより大きい値はない。 右から基準値と比較してより小さい値は15。 両者を置換。 10,11,13,19,15,17,14,16,20 真中の値 15 を基準値として使って比較。 左から基準値と比較してより大きい値は19。 右から基準値と比較してより小さい値は14。 両者を置換。 10,11,13,14,15,17,19,16,20 真中の値 15 を基準値として使って比較。 左から基準値と比較してより大きい値はない。 右から基準値と比較してより小さい値はない。 これで15が真中と確定。 この後は、「同じ過程を再帰的に二つのサブセットに適用」するのは同じ。 これは、単に、クイックソートの処理手順を追えばわかる話です。 問題は、「なぜ、『右から基準値と比較して20 の手前まで』なのだ？」ということ。 そうでないと、「堂々巡りに陥るからだ！」というのはわかります。 が、私の理解はそこで立ち往生したままです。 還暦を迎えた私の頭は、オーバーヒート気味。 「そこは、このように考えたらよい」という回答をお願いします。 ※自らの理解力と理解度の問題で質問するのは非常に恐縮。 ※しかし、後一歩の理解の壁を超えたいので質問します。
- ベストアンサー
- Visual Basic
- クイックソートしながら重複要素削除アルゴリズム
アルゴリズムが苦手な上、アルゴリズム解説自体C言語ベースで書かれ ている物が多く処理のイメージが沸かずクイックソートもコピペや既存 の関数で処理していて、満足に理解出来ていないのですが。 以下の問題を、お解かりになるかた教えて頂けませんでしょうか？ ■問題 2万件位の数値データの中から重複要素を削除しながら昇順または降順で、 ソートするアルゴリズム(※１) ■条件 BASIC的(※２)な記述やプログラム中のコメントなどの形式でも構いま せん出来るだけ簡単に示して頂けると助かります。 補足 (※１)ソートする際、重複要素を消すともっと処理が早くなるのではと 思ったので。 目的は、処理の速さを求める事と、次回から応用が聞くよ うにソート自体を理解したいのでクイックソートで無くても構いません。 (※２)実際に動かなくても構いません、イメージが掴みやすい方が良いと いう意味でとって下さい。
- ベストアンサー
- その他（プログラミング・開発）
- クイックソートについて
下記のソースプログラムの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#
- クイックソートの比較回数について
中央値をピボットとするクイックソートで、入力データ数が１０２４で昇順データの場合はＯ(nlogn)の関係より10240回の比較回数が得られる、というのは合っているでしょうか？ ご回答お願い致します。
- ベストアンサー
- C・C++・C#
- クイックソートをC++で作りたいのですが・・・
題の通り、C++でクイックソートを作りたいのですが、以下のコードではセグメンテーションエラーで動きませんでした。partition関数があやしいと思い、色々と試してみたのですが、やはりできなかったので、質問させていただくことにしました。 結果としては、print関数で昇順に表示出来ればいいのですが・・・。 以下のコードのどこをどう変えれば良いのか、ご指摘の方、何卒よろしくお願い致します。 #include <iostream> #include <vector> using namespace std; class Array { private: vector<int> array; public: void insert( int value ){ array.push_back( value ); } int getSize( ){ return (int)array.size( ); } void quick_sort( ){ quick_sort( 0, (int)array.size( ) - 1 ); } void quick_sort( int left, int right ); int partition( int left, int right ); void swap(int *a,int *b){int tmp=*a;*a=*b;*b=tmp;} void print( ); }; // クイックソートにより配列の添字 left ～ right の部分を整列する関数 void Array::quick_sort( int left, int right ) { if ( left >= right ) { return; } int v = partition( left, right ); quick_sort( left, v - 1 ); quick_sort( v + 1, right ); } //この関数を考える // 配列の添字 left ～ right の部分を，pivot の値より小さい要素と，大きい要素に分割し pivot の位置を返す関数 int Array::partition( int left, int right ) { int i=left; //左からの処理位置 int j=right; //右からの処理位置 int pivot=array[(int)(left+right)/2]; //基準 int tmp=0; while(true){ while(array[i]<pivot){i++;} while(array[j]>pivot){j--;} if(i>=j){return i;} tmp=array[i]; array[i]=array[j]; array[j]=tmp; i++; j++; } } // 配列の内容を表示する関数 void Array::print( ) { for ( int i = 0; i < (int)array.size( ); i++ ) { cout << array[i] << " "; } cout << endl; } int main( ) { Array a1; a1.insert( 56 ); a1.insert( 34 ); a1.insert( 57 ); a1.insert( 64 ); a1.insert( 3 ); a1.insert( 87 ); a1.insert( 85 ); a1.insert( 37 ); a1.insert( 21 ); a1.insert( 4 ); a1.insert( 68 ); a1.insert( 62 ); a1.insert( 42 ); a1.insert( 55 ); a1.insert( 63 ); a1.insert( 95 ); a1.insert( 7 ); a1.insert( 32 ); a1.insert( 78 ); a1.insert( 11 ); cout << "要素数: " << a1.getSize( ) << endl; cout << "ソート前: "; a1.print( ); a1.quick_sort( ); // ここで，ソートを行う関数を呼び出す cout << "ソート後: "; a1.print( ); return 0; }
- ベストアンサー
- C・C++・C#
お礼
返信ありがとうございます。 本人は回答よりも筋道を知りたかったようですが、自己解決したらしいのでこれにて〆ます。 何度もありがとうございました。