Quick Sort

퀵 소트

pivot은 항상 j(분할된 배열의 부분중 가장 왼쪽)로 시작


[-] Collapse

#include<stdio.h>
#include<algorithm>
using namespace std;
void quick_sort(int j, int k, int* arr){
    int pivot = j;
    int left = j;
    int right = k;
    while (left < right){
        while (j < k){
            if (arr[j] >= arr[pivot] && j != pivot) break;
            j++;
        }
        while (j < k){
            if (arr[k] < arr[pivot]) break;
            k--;
        }
        if (j == k){
            if (arr[j] < arr[pivot])
                swap(arr[j], arr[pivot]);
            swap(j, pivot);
            break;
        }
        else
            swap(arr[j], arr[k]);
    }
    if (left < pivot-1)
        quick_sort(left, pivot - 1, arr);
    if (pivot < right)
        quick_sort(pivot, right, arr);
}

int main(){
    const int num = 6;
    int arr[num] = { 1, 1, -1, 1, 3, 2 };
    int temp[num];
    do{
        for (int i = 0; i < num; i++)
            temp[i] = arr[i];

        quick_sort(0, num-1, temp);

        for (int i = 0; i < num; i++)
            printf("%d ", temp[i]);

        printf("\n");

    } while (next_permutation(arr, arr + num));

}