編集履歴

回答編集履歴

補足追加、用語統一

2018/12/26 14:43

投稿

スコア0

test CHANGED Viewed

@@ -18,11 +18,11 @@
 インデックスiからインデックスlenまでの配列要素にpivot以上の値が集まっています。
-**その時(pivot以上の値が格納されている配列の)先頭位置はA+iで、その配列の長さはlen-iなので**
+**その時(pivot以上の値が格納されている配列の)開始位置はA+iで、その配列の長さはlen-iなので**
 quicksort(A + i, len - i); // *2 という関数の呼び方をしています。
-つまり「A[i]からA[len]までの配列にpivot以上の値が格納されている、それをソートしてください」という意味です。
+つまり「A[i]からA[len](A[i+(len-i)])までの配列にpivot以上の値が格納されている、それをソートしてください」という意味です。
 3.0）~~中央値を選ぶことはできません。中央値を選ぼうとする行為に時間がかかってしまうので。なので少ない計算量で中央値に近い値を選ぶことがポイントです。たとえば二つの値をランダムにとってその平均をpivotにするとか。~~

補足追加

2018/12/26 14:43

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -8,9 +8,9 @@
 疑問2.0)はい、そうです。
-疑問2.1)第一引数が配列の開始位置です。第二引数には配列の長さを渡しています。
+疑問2.1)第一引数がその配列の開始位置です。第二引数にはその配列の長さ**（開始位置に長さを足せばその配列の末尾がわかる）**を渡しています。
-*1を抽象的に言うと「pivot以下の値が集まった配列をクイックソートしてください、その配列の開始位置はAでその配列の要素の数はiです」という意味です。
+*1を抽象的に言うと「pivot以下の値が集まった配列をクイックソートしてください、その配列の開始位置はAでその配列の要素の数はiです」という意味です。つまり「A[0]からA[i]までの配列にpivot以下の値が格納されている、それをソートしてください」という意味です。
 今、インデックス0からインデックスiまでの配列要素にpivot以下の値が集まっています。
@@ -22,6 +22,8 @@
 quicksort(A + i, len - i); // *2 という関数の呼び方をしています。
+つまり「A[i]からA[len]までの配列にpivot以上の値が格納されている、それをソートしてください」という意味です。
 3.0）~~中央値を選ぶことはできません。中央値を選ぼうとする行為に時間がかかってしまうので。なので少ない計算量で中央値に近い値を選ぶことがポイントです。たとえば二つの値をランダムにとってその平均をpivotにするとか。~~
 ごめんなさい、質問内容が読めてませんでした。その三つの値から中央値を選ぶことは可能です。

表記の統一

2018/12/26 14:38

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -8,19 +8,19 @@
 疑問2.0)はい、そうです。
-疑問2.1)第二引数には配列の長さを渡しています。
+疑問2.1)第一引数が配列の開始位置です。第二引数には配列の長さを渡しています。
-*1を抽象的に言うと「pivot以下の値が集まった配列をクイックソートしてください、その配列の要素の数はlargeです」という意味です。
+*1を抽象的に言うと「pivot以下の値が集まった配列をクイックソートしてください、その配列の開始位置はAでその配列の要素の数はiです」という意味です。
-第一引数が配列の開始位置です。今、インデックス0からインデックスiまでの配列要素にpivot以下の値が集まっています。
+今、インデックス0からインデックスiまでの配列要素にpivot以下の値が集まっています。
 ~~インデックスlen-iからインデックスlenまでの配列要素にpivot以上の値が集まっています。~~
 インデックスiからインデックスlenまでの配列要素にpivot以上の値が集まっています。
-**その時(pivot以上の値が格納されている配列の)先頭位置はA+iで、その配列の長さはlen-iなので
+**その時(pivot以上の値が格納されている配列の)先頭位置はA+iで、その配列の長さはlen-iなので**
-quicksort(A + i, len - i); // *2 という関数の呼び方をしています。**
+quicksort(A + i, len - i); // *2 という関数の呼び方をしています。
 3.0）~~中央値を選ぶことはできません。中央値を選ぼうとする行為に時間がかかってしまうので。なので少ない計算量で中央値に近い値を選ぶことがポイントです。たとえば二つの値をランダムにとってその平均をpivotにするとか。~~

誤記修正

2018/12/26 14:33

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -18,7 +18,7 @@
 インデックスiからインデックスlenまでの配列要素にpivot以上の値が集まっています。
-**その時開始位置はa+iで、その配列の長さはlen-iなので
+**その時(pivot以上の値が格納されている配列の)先頭位置はA+iで、その配列の長さはlen-iなので
 quicksort(A + i, len - i); // *2 という関数の呼び方をしています。**

疑問2.1の誤記修正

2018/12/26 14:25

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -14,7 +14,13 @@
 第一引数が配列の開始位置です。今、インデックス0からインデックスiまでの配列要素にpivot以下の値が集まっています。
-インデックスlen-iからインデックスlenまでの配列要素にpivot以上の値が集まっています。
+~~インデックスlen-iからインデックスlenまでの配列要素にpivot以上の値が集まっています。~~
+インデックスiからインデックスlenまでの配列要素にpivot以上の値が集まっています。
+**その時開始位置はa+iで、その配列の長さはlen-iなので
+quicksort(A + i, len - i); // *2 という関数の呼び方をしています。**
 3.0）~~中央値を選ぶことはできません。中央値を選ぼうとする行為に時間がかかってしまうので。なので少ない計算量で中央値に近い値を選ぶことがポイントです。たとえば二つの値をランダムにとってその平均をpivotにするとか。~~

誤記修正

2018/12/26 14:23

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -12,9 +12,9 @@
 *1を抽象的に言うと「pivot以下の値が集まった配列をクイックソートしてください、その配列の要素の数はlargeです」という意味です。
-第一引数が配列の開始位置です。今、AからA+1までの配列要素にpivot以下の値が集まっています。
+第一引数が配列の開始位置です。今、インデックス0からインデックスiまでの配列要素にpivot以下の値が集まっています。
-A+iからA+lenまでpivot以上の値が集まっています。
+インデックスlen-iからインデックスlenまでの配列要素にpivot以上の値が集まっています。
 3.0）~~中央値を選ぶことはできません。中央値を選ぼうとする行為に時間がかかってしまうので。なので少ない計算量で中央値に近い値を選ぶことがポイントです。たとえば二つの値をランダムにとってその平均をpivotにするとか。~~

疑問3.0に対する回答修正

2018/12/26 14:15

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -20,9 +20,31 @@
 ごめんなさい、質問内容が読めてませんでした。その三つの値から中央値を選ぶことは可能です。
-その場合は配列の中からランダムに三つ選んで、中央値を返してあげればいいと思います。
+三つの値のとりかたはランダムに選ぶのもいいですし、質問者様がいうように先頭、真ん中、末尾の値でもいいと思います。
+質問者様が実装した関数でpivotを選んでも上手く動作しました。
-実装としては引数に、１）対象となる配列の先頭要素、２）その配列の長さ　を渡して関数内で配列の中からランダムに三つ選んで中央値を返す（もしくはその添字）ようにすればいいかと思います。
+pivot部分を以下のように書き換えれば上手く動作すると思います
+```c
+  int index;
+  index = median3(A,0,len/2,len);
+  int pivot = A[index];
+```

疑問3.0に対する回答を修正

2018/12/26 14:04

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -16,7 +16,13 @@
 A+iからA+lenまでpivot以上の値が集まっています。
-3.0）中央値を選ぶことはできません。中央値を選ぼうとする行為に時間がかかってしまうので。なので少ない計算量で中央値に近い値を選ぶことがポイントです。たとえば二つの値をランダムにとってその平均をpivotにするとか。
+3.0）~~中央値を選ぶことはできません。中央値を選ぼうとする行為に時間がかかってしまうので。なので少ない計算量で中央値に近い値を選ぶことがポイントです。たとえば二つの値をランダムにとってその平均をpivotにするとか。~~
+ごめんなさい、質問内容が読めてませんでした。その三つの値から中央値を選ぶことは可能です。
+その場合は配列の中からランダムに三つ選んで、中央値を返してあげればいいと思います。
+実装としては引数に、１）対象となる配列の先頭要素、２）その配列の長さ　を渡して関数内で配列の中からランダムに三つ選んで中央値を返す（もしくはその添字）ようにすればいいかと思います。

用語修正（集合→配列）

2018/12/26 13:43

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -10,7 +10,7 @@
 疑問2.1)第二引数には配列の長さを渡しています。
-*1を抽象的に言うと「pivot以下の値が集まった集合をクイックソートしてください、その集合の要素の数はlargeです」という意味です。
+*1を抽象的に言うと「pivot以下の値が集まった配列をクイックソートしてください、その配列の要素の数はlargeです」という意味です。
 第一引数が配列の開始位置です。今、AからA+1までの配列要素にpivot以下の値が集まっています。
@@ -88,7 +88,7 @@
     printspace(deep);
-    printf("集合の中身：");
+    printf("配列の中身：");
   for (k = 0; k < len; k++) {
@@ -108,7 +108,7 @@
     printspace(deep);
-    printf("集合の要素数が1以下なのでソート終了 要素の値:%d 深さ：%d\n",A[0], deep);
+    printf("配列の要素数が1以下なのでソート終了 要素の値:%d 深さ：%d\n",A[0], deep);
       return;
@@ -148,19 +148,19 @@
     printspace(deep);
-  printf("pivot:%d以下の集合leftをクイックソートする\n", pivot);
+  printf("pivot:%d以下の配列leftをクイックソートする\n", pivot);
   quicksort(A, i, deep+1);
     printspace(deep);
-  printf("pivot:%d以上の集合rightをクイックソートする\n", pivot);
+  printf("pivot:%d以上の配列rightをクイックソートする\n", pivot);
   quicksort(A + i, len - i, deep+1);
     printspace(deep);
-    printf("集合の中身(ソート後)：");
+    printf("配列の中身(ソート後)：");
   for (k = 0; k < len; k++) {
@@ -196,20 +196,20 @@
 「-----」このprint出力で再帰の深さを示しています。
-pivot:99以上の集合rightをクイックソートする
+pivot:99以上の配列rightをクイックソートする
------集合の中身：782 99 **★これがソート前の配列の中身**
+-----配列の中身：782 99 **★これがソート前の配列の中身**
------pivot:99以下の集合leftをクイックソートする
+-----pivot:99以下の配列leftをクイックソートする
-----------集合の中身：99
+----------配列の中身：99
-----------集合の要素数が1以下なのでソート終了 要素の値:99 深さ：2
+----------配列の要素数が1以下なのでソート終了 要素の値:99 深さ：2
------pivot:99以上の集合rightをクイックソートする
+-----pivot:99以上の配列rightをクイックソートする
-----------集合の中身：782
+----------配列の中身：782
-----------集合の要素数が1以下なのでソート終了 要素の値:782 深さ：2
+----------配列の要素数が1以下なのでソート終了 要素の値:782 深さ：2
------集合の中身(ソート後)：99 782 **★これがソート後の配列の中身**
+-----配列の中身(ソート後)：99 782 **★これがソート後の配列の中身**

見やすさ改善（ソート前とソート後に配列の中身を出力）

2018/12/26 13:31

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -158,6 +158,22 @@
   quicksort(A + i, len - i, deep+1);
+    printspace(deep);
+    printf("集合の中身(ソート後)：");
+  for (k = 0; k < len; k++) {
+    printf("%d ", A[k]);
+  }
+    printf("\n");
 }
@@ -177,3 +193,23 @@
 ```
+「-----」このprint出力で再帰の深さを示しています。
+pivot:99以上の集合rightをクイックソートする
+-----集合の中身：782 99 **★これがソート前の配列の中身**
+-----pivot:99以下の集合leftをクイックソートする
+----------集合の中身：99
+----------集合の要素数が1以下なのでソート終了 要素の値:99 深さ：2
+-----pivot:99以上の集合rightをクイックソートする
+----------集合の中身：782
+----------集合の要素数が1以下なのでソート終了 要素の値:782 深さ：2
+-----集合の中身(ソート後)：99 782 **★これがソート後の配列の中身**

コード　出力のみやすさ改善

2018/12/26 13:27

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -82,11 +82,33 @@
 void quicksort(int *A, int len, int deep) {
+    int k;
+    printspace(deep);
+    printf("集合の中身：");
+  for (k = 0; k < len; k++) {
+    printf("%d ", A[k]);
+  }
+    printf("\n");
   if (len < 2){
     printspace(deep);
-    printf("集合の長さが1以下なのでソート終了 要素の値:%d 深さ：%d\n",A[0], deep);
+    printf("集合の要素数が1以下なのでソート終了 要素の値:%d 深さ：%d\n",A[0], deep);
       return;
@@ -97,18 +119,6 @@
   int pivot = A[len / 2];
-    printspace(deep);
-    int k;
-  for (k = 0; k < len; k++) {
-    printf("%d ", A[k]);
-  }
-    printf("\n");
@@ -164,4 +174,6 @@
 }
 ```

余計な空白削除

2018/12/26 13:16

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -138,13 +138,13 @@
     printspace(deep);
-  printf("pivot:%d以下の集合leftをクイックソートする\n ", pivot);
+  printf("pivot:%d以下の集合leftをクイックソートする\n", pivot);
   quicksort(A, i, deep+1);
     printspace(deep);
-  printf("pivot:%d以上の集合rightをクイックソートする\n ", pivot);
+  printf("pivot:%d以上の集合rightをクイックソートする\n", pivot);
   quicksort(A + i, len - i, deep+1);

補足追加

2018/12/26 12:48

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -1,3 +1,7 @@
+勘違いして申し訳ございません。
 疑問1.0)はい、そうです。
 疑問1.1)はい、そうです。
@@ -13,3 +17,151 @@
 A+iからA+lenまでpivot以上の値が集まっています。
 3.0）中央値を選ぶことはできません。中央値を選ぼうとする行為に時間がかかってしまうので。なので少ない計算量で中央値に近い値を選ぶことがポイントです。たとえば二つの値をランダムにとってその平均をpivotにするとか。
+処理の流れを理解しやすくする為にprint文を仕込んでみました。
+これを実行してみてください。
+```c
+#include <stdio.h>
+void quicksort(int *A, int len, int deep);
+void printspace(int deep);
+int main (void) {
+  int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1,3};
+  int n = sizeof a / sizeof a[0];
+  printf("%d\n", n);
+  int i;
+  for (i = 0; i < n; i++) {
+    printf("%d ", a[i]);
+  }
+  printf("\n");
+  quicksort(a, n, 0);
+  for (i = 0; i < n; i++) {
+    printf("%d ", a[i]);
+  }
+  printf("\n");
+  return 0;
+}
+void quicksort(int *A, int len, int deep) {
+  if (len < 2){
+    printspace(deep);
+    printf("集合の長さが1以下なのでソート終了 要素の値:%d 深さ：%d\n",A[0], deep);
+      return;
+  }
+  int pivot = A[len / 2];
+    printspace(deep);
+    int k;
+  for (k = 0; k < len; k++) {
+    printf("%d ", A[k]);
+  }
+    printf("\n");
+  int i, j;
+  for (i = 0, j = len - 1; ; i++, j--) {
+    while (A[i] < pivot) i++;
+    while (A[j] > pivot) j--;
+    if (i >= j) break;
+    int temp = A[i];
+    A[i]     = A[j];
+    A[j]     = temp;
+  }
+    printspace(deep);
+  printf("pivot:%d以下の集合leftをクイックソートする\n ", pivot);
+  quicksort(A, i, deep+1);
+    printspace(deep);
+  printf("pivot:%d以上の集合rightをクイックソートする\n ", pivot);
+  quicksort(A + i, len - i, deep+1);
+}
+void printspace(int deep){
+    int i;
+    for(i=0;i<deep;i++){
+        printf("-----");
+    }
+}
+```