[알고리즘] 퀵 정렬

퀵 정렬이란

퀵 정렬은 pivot을 하나 구해놓고, pivot보다 작은 수와 pivot보다 큰 수의 위치를 바꿔주는 정렬이다. 이 정렬은 이름과 같이 정렬 중 빠른 정렬로 많이 사용된다.

1. pivot은 5이다.
2. start는 pivot + 1, end는 배열의 마지막 값으로 정한다.
3. pivot보다 큰 수를 찾을 때까지 start++를 한다.
4. pivot보다 작은 수를 찾을 때까지 ent--를 한다.
5. start와 end의 값의 위치를 바꿔준다.

위의 과정을 start와 end가 만날 때까지 반복한다.
start와 end가 만났다면, pivot과 start의 위치를 바꿔준다.

정렬이 모두 끝날 때까지 반복한다.

java 소스

퀵 정렬을 java로 구현하면 아래와 같다.

    public int majorityElement(int[] nums) {
        //정렬
        quickSort(nums, 0, nums.length-1);
    }

    private void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        int pivot = start;
        int lo = start + 1;
        int hi = end;

        while (lo <= hi) {
            while (lo <= end && arr[lo] <= arr[pivot]) {
                lo++;
            }

            while (hi > start && arr[hi] > arr[pivot]) {
                hi--;
            }

            if (lo > hi) {
                int temp = arr[hi];
                arr[hi] = arr[pivot];
                arr[pivot] = temp;
            } else {
                int temp = arr[lo];
                arr[lo] = arr[hi];
                arr[hi] = temp;
            }

        }

        quickSort(arr, start, hi - 1);
        quickSort(arr, hi + 1, end);
    }