Quick Sort

🌲

Quick Sort

by Hoare (1962)

Strategy

• Choose a pivot item randomly
• Partition into 2 subarrays
• Sort each subarray recursively

Ex

15 22 13 27 12 10 20 25

15 : pivot item

1. partition

10 13 12 15 22 27 20 25

remember pivot's position

2. Sort subarrays recursively

10 12 13 15 20 22 25 27

procedure quicksort (low, high, index);
var pivotpoint : index;
begin
    if high > low then {
        partition(low, high, pivotpoint);
        quicksort(low, pivotpoint - 1);
        quicksort(pivotpoint + 1, high);
}
end;

n, S : parameters x
main : quicksort(1, n);

Procedure partition (low, high, pivotpoint);
var i, j : index;
pivotitem : keytype;
begin
    pivotitem = S[low];
    j = low;
    for i = low + 1 to high do
        if S[i] < pivotitem then {
            j++;
            exchange S[i] & S[j];
}
pivotpoint = j;
exchange S[low] ans S[pivotpoint]
end;

Partition

pivot과 값을 비교해서 값을 바꾼다. 그럼 pivot 기준으로 앞뒤로 나눌 수 있음. 자세한 내용은 코드 참고

My Code

#include <stdio.h>

void quick_sort(int list[], int low, int high);
void swap(int* a, int*b);
int partition(int list[], int low, int high);

int main()
{
    int list[] = {15, 22, 13, 27, 12, 10, 20, 25};
    int i;
    quick_sort(list, 0, 7);
    for(i = 0; i < 8; i++)
        printf("%d ", list[i]);
    return 0;
}

void quick_sort(int list[], int low, int high){
    if (high > low){
        int pivotpoint = partition(list, low, high);
        quick_sort(list, low, pivotpoint - 1);
        quick_sort(list, pivotpoint + 1, high);
    }  
}

int partition(int list[], int low, int high){
    int i, j = low;
    int pivotitem = list[low];

    for (i = low + 1; i <= high; i++){
        if (list[i] < pivotitem) {
            j++;
            swap(&list[i], &list[j]);
        }
    }
    swap(&list[low], &list[j]);
    return j;
}

void swap(int* a, int*b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

Stable?

No. Why?

In-place?

Yes. If we ignore stack space.

Worst-case t.c.

n²

using stack

Procedure quicksort(low, high)
var pivotpoint{
    while low < high do {
        partition(low, high, pivotpoint);
        if pivotpoint - low <= high - pivotpoint {
                quicksort(low, pivotpoint - 1)
                low <- pivotpoint + 1;
        }
        else {
                quicksort(pivotpoint + 1, high);
                high <- pivotpoint - 1;
        }
    }
}

최악의 상황을 막기 위한 방법이다. 하지만 교수님 말에 따르면 렌덤으로 해도 괜찮다고 하신다.

Randomized Quicksort

QuickSort using Random Pivoting

Procedure rand_partition(low, high);
{
    i <- random(low, high);
    exchange s[low] ans s[i];
    partition(low, high, pivotpoint);
}

Procedure rand_Quicksort(low, high){
    if low > high then {
            rand_partition(low, high, pivotpoint);
            rand_Quicksort(low, pivotpoint - 1);
            rand_Quicksort(pivotpoint + 1, high)
    }
}

My Code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quick_sort(int list[], int low, int high);
void swap(int* a, int*b);
int partition(int list[], int low, int high);
int rand_partition(int list[], int low, int high);

int main()
{
    int list[] = {15, 22, 13, 27, 12, 10, 20, 25};
    int i;
    quick_sort(list, 0, 7);
    for(i = 0; i < 8; i++)
        printf("%d ", list[i]);
    return 0;
}

int rand_partition(int list[], int low, int high){
    int i;
    srand(time(NULL));
    i = low + rand() % (high - low);
    swap(&list[low], &list[i]);
    return partition(list, low, high);
}

void quick_sort(int list[], int low, int high){
    if (high > low){
        int pivotpoint = rand_partition(list, low, high);
        quick_sort(list, low, pivotpoint - 1);
        quick_sort(list, pivotpoint + 1, high);
    }  
}

int partition(int list[], int low, int high){
    int i, j = low;
    int pivotitem = list[low];

    for (i = low + 1; i <= high; i++){
        if (list[i] < pivotitem) {
            j++;
            swap(&list[i], &list[j]);
        }
    }
    swap(&list[low], &list[j]);
    return j;
}

void swap(int* a, int*b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}