Quick Sort
Quick sort is an algorithm that uses the famous "Divide and Conquer" sort algorithm. It's so famous that if you haven't heard of what Quick Sort is, here for reference.
Solution
Runtime Complexity O(nlogn) If you choose pivot as the leftmost of the array
Memory Complexity O(logn) Sort the right side and the left side separately from the pivot. At this time, since a recursive function is used It is O (logn) because it consumes memory on the stack.
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);
}
}
Recommended Posts