アルゴリズム体操9
Quick Sort
説明
Quick sort はソートアルゴリズムの中でも有名な "Divide and Conquer"を使ったアルゴリズムです。
とても有名なので、Quick Sort がどんなアルゴリズムか聞いたことがなければこちらを参考に。
Solution
Runtime Complexity O（nlogn)
pivot を配列の一番左側として選ぶ場合、
1）配列はすでに同じ順序でソートされている
2）配列はすでに逆順でソートされている
3）すべての要素が同じ
の三つの条件の以外の場合は、O(nlogn)ですが、偶然この条件に遭遇した場合はO(n^2)となります。
Memory Complexity O(logn)
pivotから見て右側と左側を分けて、ソートしていきます。このとき、再帰関数を使うので
スタック上のメモリを消費するため、O（logn）となります。
大まかなアルゴリズムの流れ
- 配列からピボット要素を選択します。配列の最初の要素をPivotとして選択します。
- Pivotよりも小さな値がPivotの左側へ、大きな値がPivotの右側に来るように Swapして行きます。
- Pivotの右側と左側の部分配列を再帰的に並べ替えることができます。
実装
quickSort.java
class quickSort{
public int partition(int[] arr, int low, int high) {
int pivot_value = arr[low];
int i = low;
int j = high;
while (i < j) {
while( i <= high && arr[i] <= pivot_value) i++;
while(arr[j] > pivot_value) j--;
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[low] = arr[j];
arr[j] = pivot_value;
return j;
}
public void quick_sort_recursive(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quick_sort_recursive(arr, low, pivot - 1);
quick_sort_recursive(arr, pivot + 1, high);
}
}
public void quick_sort(int[] arr) {
quick_sort_recursive(arr, 0, arr.length - 1);
}
}
Author And Source
この問題について(アルゴリズム体操9), 我々は、より多くの情報をここで見つけました https://qiita.com/yutakihara/items/2f89ab8cc1530896a282著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .