[알고리즘] 퀵정렬

버블, 선택, 삽입, 병합, 퀵 정렬 등이 있는데 이 중에서 가장 빠른 정렬이 퀵정렬이다. 시간복잡도가 O(NlogN)이다. 속도가 log로 나온다면 연산해야 할 횟수가 절반 혹은 1/n으로 줄어든다는 뜻이다. 가장 느릴때는 O(N^2)이 나오기도 하지만 매번 한개의 원소와 나머지 원소로 나누어지는 경우는 많지는 않으므로 보통 O(NlogN)이 나온다.

https://upload.wikimedia.org/wikipedia/commons/f/fe/Quicksort.gif

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
   피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다.
2. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

⌨️ (Java) 작성한 코드 - list 사용

public List<Integer> quickSortList(List<Integer> arr){
    if(arr.size() <= 1){
        return arr;
    }
    //1. 기준값 뽑는 로직 구현
    int mid = arr.size()/2;
    int pivot = arr.get(mid);

    //2. 기준값 기준으로 왼쪽 오른쪽으로 나누어 담는 로직 구현
    List<Integer> left = new ArrayList<>();
    List<Integer> right = new ArrayList<>();
    for (int i = 0; i < arr.size(); i++) {
        if(i != mid){
            if(arr.get(i) < pivot){
                left.add(arr.get(i));
            } else{
                right.add(arr.get(i));
            }
        }
    }
    left = quickSortList(left);
    right = quickSortList(right);

    List<Integer> result = new ArrayList<>();
    result.addAll(left);
    result.add(pivot);
    result.addAll(right);

    return result;
}

⌨️ (Java) 작성한 코드 - array 사용

    public int[] QuickSort (int[] arr, int start, int end){
        if(start >= end){
            return arr;
        }
        int pivot = (start+end)/2;
        int left = start;
        int right = end;
        while(left <= right){
            while(arr[left] < arr[pivot]){left++;}
            while(arr[right] > arr[pivot]){right--;}

            if(left <= right){
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
                right--;
                left++;
            }
        }
        QuickSort2(arr, start, right);
        QuickSort2(arr, left, end);
        return arr;
    }

⌨️ (Java) wiki code

public void quickSort(int[] arr, int left, int right) {
    // base condition
    if (left >= right) {
        return;
    }
    int pivot = arr[right];
    
    int sortedIndex = left;
    for (int i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            swap(arr, i, sortedIndex);
            sortedIndex++;
        }
    }
    swap(arr, sortedIndex, right);
    quickSort(arr, left, sortedIndex - 1);
    quickSort(arr, sortedIndex + 1, right);
}

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

⌨️ (Python) widi code

def quicksort(x):
    if len(x) <= 1:
        return x

    pivot = x[len(x) // 2]
    less = []
    more = []
    equal = []
    for a in x:
        if a < pivot:
            less.append(a)
        elif a > pivot:
            more.append(a)
        else:
            equal.append(a)

    return quicksort(less) + equal + quicksort(more)

⌨️ (Python) widi code - no cache

def partition(arr, start, end):
    pivot = arr[start]
    left = start + 1
    right = end
    done = False
    while not done:
        while left <= right and arr[left] <= pivot:
            left += 1
        while left <= right and pivot <= arr[right]:
            right -= 1
        if right < left:
            done = True
        else:
            arr[left], arr[right] = arr[right], arr[left]
    arr[start], arr[right] = arr[right], arr[start]
    return right


def quick_sort(arr, start, end):
    if start < end:
        pivot = partition(arr, start, end)
        quick_sort(arr, start, pivot - 1)
        quick_sort(arr, pivot + 1, end)
    return arr