Quick sort(퀵 정렬)

Quick sort(퀵 정렬)

원칙1: pivot을 고른다.(주로 첫번째 또는 마지막 값을 선정하는 편이다.)

원칙2: pivot값을 기준으로 작은쪽, 큰쪽으로 나누어 서로간의 swap으로 위치를 교환한다.(증가될 수 없는 배열이라고 가정....)

원칙3: swap이 끝나면 그 나눈 중심에 pivot을 두고 작은쪽, 큰쪽을 각각 퀵소트한다.

Best case: O(n) 

Average case: O()

Worst case: O() 

# 재귀함수로 구현한 Quick sort

public class QuickSort implements ISort {

    @Override

    public void sort(Comparable[] array) {

        quickSort(array, 0, array.length - 1);

    }

    private void quickSort(Comparable[] array, int startIndex, int endIndex) {

        if (startIndex >= endIndex) {

            return;

        }

        final Comparable pivot = array[startIndex];

        int left = startIndex + 1;

        int right = endIndex;

        do {

            while (array[left].compareTo(pivot) < 0 && left < endIndex) {

                left++;

            }

            while (array[right].compareTo(pivot) > 0 && startIndex < right) {

                right--;

            }

            if (left < right) {

                swap(array, left, right);

            }

        } while (left < right && left < endIndex && startIndex < right);

        swap(array, startIndex, right);

        quickSort(array, startIndex, right - 1);

        quickSort(array, right + 1, endIndex);

    }

    private void swap(Comparable[] array, int i, int j) {

        Comparable temp = array[i];

        array[i] = array[j];

        array[j] = temp;

    }

}

Reference:

- https://en.wikipedia.org/wiki/Quicksort