前提・実現したいこと
1.関数に渡された配列の要素をクイックソートを用いて昇順に並び替えるプログラムの処理の流れと実装内容を理解しようとしています。
再帰処理の部分の実装内容を理解して全体の流れをイメージできるようになりたい。
2.プログラムの改変
理解したいソースコード
http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#C
C
1#include <stdio.h> 2 3void quicksort(int *A, int len); 4 5int main (void) { 6 int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; 7 int n = sizeof a / sizeof a[0]; 8 9 int i; 10 for (i = 0; i < n; i++) { 11 printf("%d ", a[i]); 12 } 13 printf("\n"); 14 15 quicksort(a, n); 16 17 for (i = 0; i < n; i++) { 18 printf("%d ", a[i]); 19 } 20 printf("\n"); 21 22 return 0; 23} 24 25void quicksort(int *A, int len) { 26 if (len < 2) return; 27 28 int pivot = A[len / 2]; 29 30 int i, j; 31 for (i = 0, j = len - 1; ; i++, j--) { 32 while (A[i] < pivot) i++; 33 while (A[j] > pivot) j--; 34 35 if (i >= j) break; 36 37 int temp = A[i]; 38 A[i] = A[j]; 39 A[j] = temp; 40 } 41 42 quicksort(A, i); // *1 43 quicksort(A + i, len - i); // *2 44}
自分が理解しやすいように書き直したソースコード
C
1#include <stdio.h> 2 3void swap_elms(int *array, int a, int b) 4{ 5 int buf; 6 7 buf = array[a]; 8 array[a] = array[b]; 9 array[b] = buf; 10} 11 12void quicksort(int *array, int len) 13{ 14 if (len < 2) return; 15 16 int pivot; 17 int large; 18 int small; 19 20 pivot = array[len / 2]; 21 large = 0; 22 small = len - 1; 23 while (1) 24 { 25 while (array[large] < pivot) 26 large++; 27 while (array[small] > pivot) 28 small--; 29 30 if (large >= small) 31 break; 32 33 swap_elms(array, large, small); 34 35 large++; 36 small--; 37 } 38 39 quicksort(array, large); // *1 40 quicksort(array + large, len - large); // *2 41} 42 43int main(void) 44{ 45 int i; 46 int size = 10; 47 int array[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; 48 49 for (i = 0; i < size; i++) 50 printf("%d, ", array[i]); 51 printf("\n"); 52 53 quicksort(array, size); 54 55 for (i = 0; i < size; i++) 56 printf("%d, ", array[i]); 57 58 return (0); 59} 60
疑問
1.0「*1は配列内のピボット以下の値が集まった範囲をソートするために quicksort()
を呼び出している。」という解釈で正しいのか。
1.1 「*1の quicksort()
に渡している第一引数は、配列内のピボット以下の範囲の先頭の要素を指し、第二引数は配列内のピボット以下の範囲の最後の要素の次の要素を指している。」という解釈で正しいのか。
2.0「*2はピボット以上の値が集まった範囲をソートするために quicksort()
を呼び出している。」という解釈で正しいのか。
2.1 *2の quicksort()
に渡している二つの引数はそれぞれ何を指しているのか。なぜ A + i
と len - i
となっているのか。(ここが一番理解できない部分ですので、初学者でも分かるように解説して頂けると幸いです。
3.0 このプログラムのピボット選択の部分を改変したいと思っています。配列の先頭、真ん中、最後の要素から中央値となる要素を選択してそれをピボットとして扱うにはどのような実装にすれば良いでしょうか。中央値を選択するための関数を作成して試行錯誤しましたが上手く実装できません。
ピボット選択時に3つの要素から中央値を選択するための関数
C
1int median3(int *array, int a, int b, int c) 2{ 3 if (array[a] < array[b]) 4 { 5 if (array[b] < array[c]) 6 return (b); 7 else if (array[c] < array[a]) 8 return (a); 9 return (c); 10 } 11 else 12 { 13 if (array[c] < array[b]) 14 return (b); 15 else if (array[a] < array[c]) 16 return (a); 17 return (c); 18 } 19}
よろしくお願い致します。
回答2件
あなたの回答
tips
プレビュー