퀵 정렬 (Quick Sort) - Java

퀵 정렬이란?

• 시간복잡도 : O(NlogN)
• Divide and Conquer 방식
• Divide 단계 
  • pivot(기준점)을 기준으로 왼쪽엔 더 작은 값, 오른쪽엔 더 큰 값을 위치하게 한 후 Partitioning
  • pivot 은 왼쪽 값, 중간 값, 오른쪽 값 세 가지로 지정할 수 있다. 
• Conquer 단계 
  • 나누어진 각각을 정렬
  • Divide 단계부터 진행 => 재귀적으로 진행된다. 
• Combine : 이미 pivot 을 기준으로 왼쪽은 더 작고, 오른쪽은 더 큰 값만 들어있으므로 합치기만 하면 된다. 

 

 

partition 하기 (pivot 을 오른쪽 끝 값으로 설정하는 경우)

int partition(int[] my_list, int start, int end) {
	// partition 로직
    return b;
}

// b : big 그룹의 시작

(my_list 의 타입은 배열이나 컬렉션 편한대로 지정해도 될 것 같다.)

• my_list : 정렬해야 하는 배열
• start, end : partition 하려는 범위를 나타낸다. (인덱스 값)

 

파티션을 하기 위해 먼저 네 개의 그룹으로 나누어 생각할 수 있다.

1. Pivot 값
2. Small 그룹 : Pivot 보다 작은 값을 가지는 그룹
3. Big 그룹 : Pivot 보다 큰 값을 가지는 그룹
4. Unknown 그룹 : 아직 Pivot 값과 비교하지 않은 그룹

변수

• start : partition 하는 범위의 시작점
• end : partition 하는 범위의 끝점 = p (pivot 값과 동일하다)
• b : Big 그룹의 시작
• i : Unknown 그룹의 시작

 

Partition 진행과정

1. 시작

• b, i 는 가장 왼쪽 인덱스를 가리킨다.
• 아직 pivot 과 비교하기 전이므로 pivot 값을 제외한 나머지는 모두 Unknown 그룹에 속한다.

2. 비교 대상이 pivot 값 보다 큰 경우

• 16은 pivot 7 보다 크다. => big 그룹 => i 만 오른쪽으로 한 칸 이동

3. 비교 대상이 pivot 값보다 작은 경우

• 세번째 요소 6의 경우 pivot 값보다 작다.
  => smal 그룹 에 들어가야 한다. 
  => b가 가리키는 값과 i 가 가리키는 값의 자리를 바꾼다. 
  => b와 i 모두 오른쪽으로 한 칸씩 이동

 

4. i  가 pivot 값의 위치로 왔을 때 (i == end)

• pivot 값과 b 의 요소 자리를 바꾼다. 
  => pivot 왼쪽은 모두 pivot 보다 작은 값이, pivot 오른쪽은 모두 pivot 보다 큰 값이 위치한 상태

 

5. pivot 의 인덱스 리턴(b)

 

 

Partition 함수 구현

import java.util.Arrays;

public class Partition {
    public static void swap(int[] myList, int index1, int index2) {
        int tmp = myList[index1];
        myList[index1] = myList[index2];
        myList[index2] = tmp;
    }

    public static int partition(int[] myList, int start, int end) {
        int b = start;
        int i = start;
        int p = end;

        while(i <= end) {
            if(i == end) {
                swap(myList, b, p);
                break;
            }
            else if(myList[i] > myList[p]){
                i++;
            }
            else {
                swap(myList, i, b);
                i++;
                b++;
            }
        }
        // pivot 인덱스 리턴 : pivot 의 위치가 b가 되었으므로 b 리턴
        return b;
    }

    public static void main(String[] args) {
        int[] myList = {6, 1, 2, 6, 3, 5, 4};
        System.out.println(Arrays.toString(myList)); // 파티션 전
        int pivot = partition(myList, 0, myList.length - 1);
        System.out.println(pivot); // pivot 값
        System.out.println(Arrays.toString(myList)); // 파티션 후
    }
}

// 출력 결과
[6, 1, 2, 6, 3, 5, 4]
3
[1, 2, 3, 4, 6, 5, 6]

 

 

Quick Sort 구현

public class QuickSort {
    public static void swap(int[] myList, int index1, int index2) {
        int tmp = myList[index1];
        myList[index1] = myList[index2];
        myList[index2] = tmp;
    }

    public static int partition(int[] myList, int start, int end) {
        int b = start;
        int i = start;
        int p = end;

        while(i <= end) {
            if(i == end) {
                swap(myList, b, p);
                break;
            }
            else if(myList[i] > myList[p]){
                i++;
            }
            else {
                swap(myList, i, b);
                i++;
                b++;
            }
        }
        // pivot 인덱스 리턴 : pivot 의 위치가 b가 되었으므로 b 리턴
        return b;
    }

    public static void quicksort(int[] myList, int start, int end) {
        // base case
        if(start >= end) {
            return;
        }

        int pivot = partition(myList, start, end);

        quicksort(myList, start, pivot - 1);
        quicksort(myList, pivot, end);
    }

    public static void main(String[] args) {
        int[] myList = {28, 13, 9, 30, 1, 48, 5, 7, 15};
        System.out.println(Arrays.toString(myList)); // 퀵정렬 전 myList
        quicksort(myList, 0, myList.length - 1);
        System.out.println(Arrays.toString(myList)); // 퀵정렬 후 myList
    }
}

// 출력 결과
[28, 13, 9, 30, 1, 48, 5, 7, 15]
[1, 5, 7, 9, 13, 15, 28, 30, 48]