- 締切済み
Ｃ言語 クイックソートについて
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- Trick--o--
- ベストアンサー率20% (413/2034)
Wikipediaが詳しいです。
関連するQ&A
- C言語 クイックソートについて
クイックソートでわからない点があるため、 質問させていただきます。 ----------------------------------------------------- ～省略～ data = [5, 3, 4, 2, 6, 1]; no = 6; //データの個数 ～省略～ dqsort(data, 0, no-1); ～省略～ void dqsort(double data[], int lower, int upper) { int i, boundary; //boundaryは配列の前半と後半の境界を示す if(lower >= upper) { return; } //基準値となる値（データの中央に位置する値）とデータの先頭の値を入れ替える swapdata(&data[lower], &data[(lower + upper)/2]); boundary = lower; //boundaryを先頭に移動させる for(i=lower+1; i<=upper; i++) { if(data[i] < data[lower]) { //配列の前半部分に移動し、境界を移動する swapdata(&data[++boundary], &data[i]); } } //最後に基準値を境界位置にコピー swapdata(&data[lower], &data[boundary]); //配列の前半部分をクイックソート dqsort(data, lower, boundary-1); //配列の後半部分をクイックソート dqsort(data, boundary+1, upper); } void swapdata(double *i, double *j) { int temp; temp = *i; *i = *j; *j = temp; } --------------------------------------------------------- 基準値と配列の先頭のデータを入れ替えた後、 データは、[4, 3, 5, 2, 6, 1]となり、lower = 0であるため、 data[boundary]はdata[0]となります。 for文の最初のループでdata[0]<data[1]なら、 swapdata(&data[++boundary], &data[i]); となっているのですが、 [++boundary]の部分はboundary=0に1を足してから処理するため、 swapdata(&data[1], &data[1]); となると思うのですが、そうすると同じデータを入れ替えることになってしまいます。 何が間違っているのか、教えていただけますでしょうか。
- ベストアンサー
- 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#
- クイックソート（C言語）
こんにちは<_ _> クイックソートについての質問です。 左端を軸にクイックソートでデータを昇順にソートする プログラムを作ったのですがうまく動きません #include<stdio.h> void quick(int *,int,int); #define N 10 int main(void) { static int a[]={41,24,76,11,45,64,21,69,19,36}; int k,b=0; quick(a,0,N-1); for(k=0;k<N;k++) printf(" %d",a[k]); return 0; } void quick(int a[],int left,int right) { int s,t,i,j; t=right; i=left+1; j=a[left]; if(right>left){ while(1){ while(a[++i]>j); while(a[--t]<j && t>0); if(i>=t){ break; } s=a[i]; a[i]=a[t]; a[t]=s; } s=a[i]; a[i]=j; a[left]=s; quick(a,left,t-1); quick(a,t+1,right); } } 値の入れ替え、軸の入れ替えもしましたが結果として 「41 41 76 69 45 64 41 19 0 36」 このような結果で出力されてしまいます・・・ 時間に余裕のある方いましたらご指導をお願いします。 よろしくお願いします。<_ _>
- ベストアンサー
- C・C++・C#
- バブル・ソート、クイック・ソート
N個（N=4,5,6）のデータが全て等しいデータ列（例えばN個の数字全部が1のとき）をバブルソートで並び替えたとき、データの交換回数は何回か。また、同じデータ列をクイックソートで並び替えたときはどうか。 という問題があるのですが、どう比較するのかがわかりません。詳しい方、説明よろしくお願いします。
- 締切済み
- C・C++・C#
- Ｃ言語 ソートについて
#include <stdio.h> #include <stdbool.h> #define NUM_ARRAY 4 #define NUM_DATA 5 int count_swap = 0; // 交換回数 int count_comparison = 0; // 比較回数 void selection_sort(int a[], int n) { } int main(void) { int data[NUM_ARRAY][NUM_DATA] = {{9, 7, 5, 6, 8}, {9, 8, 7, 6, 5}, {5, 6, 7, 8, 9}, {5, 6, 8, 7, 9}}; for (int i = 0; i < NUM_ARRAY; i++) { count_swap = 0; count_comparison = 0; int d[NUM_DATA]; copy_array(data[i], d, NUM_DATA); // 配列のコピー printf("----------------\n"); print_array(d, NUM_DATA); // ソート前の配列の表示 selection_sort(d, NUM_DATA); // 挿入ソートの実行 print_array(d, NUM_DATA); // ソート後の配列の表示 printf("比較回数: %d\n", count_comparison); // 比較回数の表示 printf("交換回数: %d\n", count_swap); // 交換回数の表示 } } 上の雛形を使って選択ソートを実行するという問題なのですが途中までそれっぽいのは出来たのですが上手くいかないので解答をお願いします。 下に自分が今書いているものを置いておきます。 #include <stdbool.h> #include <stdio.h> #define NUM_ARRAY 4 #define NUM_DATA 5 int count_swap = 0; int count_comparison = 0; void swap(int d[], int i, int j) { count_swap += 1; printf("swap a[%d] = %d, a[%d] = %d\n", i, d[i], j, d[j]); int temp = d[i]; d[i] = d[j]; d[j] = temp; } void copy_array(int *a, int *b, int n) { for (int i = 0; i < n; i++) { b[i] = a[i]; } } void print_array(int d[], int n) { for (int i = 0; i < n; i++) { printf("%d ", d[i]); } printf("\n"); } bool compare(int d[], int i, int j) { count_comparison += 1; printf("compare a[%d] = %d, a[%d] = %d\n", i, d[i], j, d[j]); if (d[i] > d[j]) { return true; } else { return false; } } void selection_sort(int d[], int n) { int min; for (int i = 0; i < n - 1; i++) { min = i; for (int j = i + 1; j < i; j++) { if (compare(d, min, j)) { min = j; } } swap(d, i, min); print_array(d, n); } } int main(void) { int data[NUM_ARRAY][NUM_DATA] = { {9, 7, 5, 6, 8}, {9, 8, 7, 6, 5}, {5, 6, 7, 8, 9}, {5, 6, 8, 7, 9}}; for (int i = 0; i < NUM_ARRAY; i++) { count_swap = 0; count_comparison = 0; int d[NUM_DATA]; copy_array(data[i], d, NUM_DATA); // 配列のコピー printf("----------------\n"); print_array(d, NUM_DATA); // ソート前の配列の表⽰ selection_sort(d, NUM_DATA); // 挿⼊ソートの実⾏ print_array(d, NUM_DATA); // ソート後の配列の表⽰ printf("⽐較回数: %d\n", count_comparison); // ⽐較回数の表⽰ printf("交換回数: %d\n", count_swap); // 交換回数の表⽰ } }
- ベストアンサー
- 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#
- c言語 配列 や ソート datファイル読み込みについて
初投稿でC言語初心者なのでよろしくお願いします。 課題でdatファイルから１００万個の数字を読み込んで、ソートのタイムを競うのがでました。 ソートのアルゴリズム等は分かるのですが、100万個の数字を読み込むのがわかりません。 datファイルには、縦にずらっと数字が並べられていてどこを区切り文字としてとりだすのとか。 int配列も100万個も格納できないので3次元配列つかうのかなと思ってみたりしてます。 どうやって格納すればソートで使いやすいかご教授お願いいたします。
- 締切済み
- その他（学問・教育）
- アルゴリズムの問題なのですが、マージソートとクイックソートについて教え
アルゴリズムの問題なのですが、マージソートとクイックソートについて教えてください。 数列の(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を選んだ) これではいけないのでしょうか。 長くなりましたが、よろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
