Java 퀵소트 구현

• QuckSort
• Main
• Tip
• 1. ArrayIndexOutOfBoundsException
• 2. 무한루프
• 3. nextPivot

B형 준비하려면 구현을 해야하는데 소팅 알고리즘 하나 구현해봤다.

퀵소트 많이들 쓰는 것 같아서 구현해봤다. 엄청 오래걸렸음. 퀵소트 하니까 피봇은 생각났는데 구현 방법을 다 까먹었다.

결국 유튜브에 검색해서 동작원리 좀 봤다. 데이터가 오름차순, 내림차순 정렬일 경우 시간복잡도는 N^2인 소팅방법이다.

pivot은 아무거나 해도 되는데 제일 왼쪽에 두고 구현하는데 한참 걸렸다. 메모리 엄청 터지고.. 어쨌든 완성시키긴 했다.

(190721 수정. 가독성을 위해 수정)

QuckSort

class QuickSort {

    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

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

        final int pivot = start;
        final int pivotData = arr[pivot];

        int left = start + 1;
        int right = end;

        while (left < right) {
            while (arr[left] <= pivotData && left < right) left++;
            while (arr[right] >= pivotData && left < right) right--;

            swap(arr, left, right);
        }

        int nextPivot = left;
        if (pivotData < arr[nextPivot]) {
            nextPivot -= 1;
        }

        swap(arr, pivot, nextPivot);

        sort(arr, start, nextPivot - 1);
        sort(arr, nextPivot + 1, end);
    }

    private static void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }

}

   

Main

public class Main {
    public static void main(String[] args) {
        final int SIZE = 15;
        final int MAX_VALUE = 10;

        int[] arr = new int[SIZE];
        for (int i = 0; i < SIZE; i++) {
            arr[i] = (int) (Math.random() * MAX_VALUE);
        }

        System.out.println(Arrays.toString(arr)); // [0, 9, 5, 0, 9, 3, 2, 8, 4, 4, 8, 2, 1, 5, 5]
        QuickSort.sort(arr);
        System.out.println(Arrays.toString(arr)); // [0, 0, 1, 2, 2, 3, 4, 4, 5, 5, 5, 8, 8, 9, 9]
    }
}

   

Tip

1. ArrayIndexOutOfBoundsException

while (left < right) {
    while (arr[left] <= pivotData) left++; // && left < right 빠짐
    while (arr[right] >= pivotData) right--; // && left < right 빠짐

    swap(arr, left, right);
}

위의 코드는 ArrayIndexOutOfBoundsException 이 발생한다.

• arr => [1,2,3,4,5]
  • 두 번째 while문은 left를 계속 증가시킴
    • left = 5 일 때에도 두번째 while문을 돌기 때문에 arr[left]로 터짐

 

2. 무한루프

while (left < right) {
    while (arr[left] < pivotData && left < right) left++; // 등호가 빠짐
    while (arr[right] > pivotData && left < right) right--; // 등호가 빠짐

    swap(arr, left, right);
}

두, 세번째 while문의 조건에 등호가 생략되어 있을 경우, 무한루프에 빠진다.

• arr => [1, 1, 2, 3, 1]
  • pivot의 값(arr[0]) => 1
  • left의 값(arr[1]) => 1
  • right의 값(arr[4]) => 1
  • left는 ++되지 않으며, right는 –되지 않음
    • 무한루프

따라서 두 while 문 중 적어도 하나에는 등호를 붙여야 하며, 둘 다 붙여도 상관없다.

 

3. nextPivot

int nextPivot = left;
if (pivotData < arr[nextPivot]) {
    nextPivot -= 1;
}

첫번째 while문을 탈출할 때에는 left == right 이다. 그 이후 nextPivot에 left를 넣어주었다.

• arr[nextPivot] 은 arr[pivot] 보다 작을 수도 있고 클 수도 있음
  • 작다면, nextPivot 을 그대로 쓰면 됨
  • 크다면, nextPivot 을 1 감소시켜야 함
    • 만약 그대로 쓰면 pivot의 왼쪽에 arr[pivot] 보다 큰 값이 들어가버림
      • (pivot의 왼쪽의 값들은 pivot의 값보다 작아야 함)
      • (pivot의 오른쪽의 값들은 pivot의 값보다 커야 함)
    • arr[nextPivot-1] 은 arr[pivot] 보다 항상 작거나 같음