[ch 10-2] 복잡하지만 효율적인 정렬 알고리즘_2(퀵 정렬)

[주제]

- 퀵 정렬에 대한 개념과 구현

[중요]

- 피벗의 시작 위치는 '맨 왼쪽 or 중간 or 맨 오른쪽'이 될 수 있음

- 좀 더 효율적이기 위해 처음:중간:마지막 숫자끼리 비교해서 중간 값을 피벗으로 설정하는 것이 효율적임

  또는, 맨 왼쪽(오른쪽) 3개 숫자를 비교

- 피벗을 중심으로 영역을 두 개로 분할하여 정렬

  ※ 재귀

■ 그림(퀵 정렬 과정)

- 숫자 '5, 7, 4, 2, 1, 8, 3, 6'을 오름차순으로 정렬

- 맨 왼쪽 숫자를 피벗으로 결정

- 비교 숫자(low)는 피벗 숫자의 오른쪽부터 시작

- 'low'는 해당 위치의 숫자가 피벗 위치의 숫자보다 높을 때까지 오른쪽으로 이동

- 'high'는 해당 위치의 숫자가 피벗 위치의 숫자보다 낮을 때까지 왼쪽으로 이동

  ※ 'low'의 이동이 끝나야 'high'가 이동 시작

- 'low'와 'high'가 서로 엇갈리기 전에 정지하면 해당 위치의 숫자르 서로 교체

- 교체가 끝나면 다시 이동

- 'low'가 'high'의 뒤로 이동하는 시점

- 'high' 위치의 숫자와 피벗 위치의 숫자와 교체

  ※ 피벗의 숫자가 중심으로 이동

- 피벗 숫자의 위치를 기준으로 2개의 영역이 분할됨

- 왼쪽 영역부터 정렬 시작

- 'high'가 'low' 이전까지 이동

- 더 이상 이동할 수 없기 때문에 피벗 위치의 숫자와 교체

- 피벗을 기준으로 왼쪽 영역이 없으니 남은 오른쪽 영역 정렬 시작

- 'low' 위치의 숫자가 피벗 위치의 숫자보다 높으므로 정지

- 'high' 위치의 숫자가 피벗 위치의 숫자보다 낮으므로 정지

- 'low'와 'high' 위치의 숫자를 서로 교체

- 'low'는 다시 이동 후 'right'에 도착했으므로 정지

- 'high'는 1칸 이동 후 피벗 위치의 숫자보다 낮으므로 정지

- 'low'와 'high'가 엇갈렸으므로, 'high' 위치의 숫자와 피벗 위치의 숫자와 교체

- 왼쪽은 정렬 완료

- 오른쪽 영역 정렬 시작

- 모든 변수들이 오른쪽 영역에 위치에 맞게 변경

- 'low'가 이동 후 'right' 위치에 도착했으므로 정지

- 'high'는 시작 위치의 숫자가 피벗 위치의 숫자보다 낮으므로 이동 없음

- 엇갈리진 않았지만 'low'가 끝에 도달했으므로 피벗 위치의 숫자와 'high' 위치의 숫자와 교체

[소스]

■ QuickSort.java

package sortQuick;
 
public class QuickSort {
 
    void Sort(int arr[], int left, int right) {
        if (left <= right) {
            int pivot = Partition(arr, left, right);    // 영역 분할
            Sort(arr, left, pivot-1);                   // 분할된 왼쪽 영역 정렬
            Sort(arr, pivot+1, right);                  // 분할된 오른쪽 영역 정렬
        }
    }
    
    void Swap(int arr[], int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
    
    int Partition(int arr[], int left, int right) {
        int pivot = arr[left];
        int low = left + 1;
        int high = right;
        
/*
 * 'low' 또는 'high'가 엇갈리기 전까지 반복
 * 'low'는 배열 마지막까지만 이동
 */
        while (low <= high) {
            while (pivot >= arr[low] && low <= right) {
                if (low == arr.length-1) {
                    break;
                }
                low++;
            }
            while (pivot <= arr[high] && high >= (left+1)) {
                high--;
            }
            
            if (low <= high) {
                Swap(arr, low, high);
            }
            if (low == arr.length-1) {
                break;
            }
        }
        
        Swap(arr, left, high);
        
        return high;
    }
}

■ mainClass.java

package sortQuick;
 
public class mainClass {
 
    public static void main(String[] args) {
 
        QuickSort qs = new QuickSort();
        
        int arr1[] = { 5, 7, 4, 2, 1, 8, 3, 6 };
        
        System.out.print("배열 1의 값(중복x): ");
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
        System.out.println();
        
        qs.Sort(arr1, 0, arr1.length-1);
        
        System.out.print("배열 1의 정렬 된 값: ");
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
        System.out.println("\n");
        
        int arr2[] = { 5, 7, 4, 4, 1, 8, 8, 6 };
        
        System.out.print("배열 2의 값(중복o): ");
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + " ");
        }
        System.out.println();
        
        qs.Sort(arr2, 0, arr2.length-1);
        
        System.out.print("배열 2의 정렬 된 값: ");
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + " ");
        }
    }
}

■ 실행결과

※ 중복 없는 숫자로된 배열과 중복 숫자가 존재하는 배열의 결과

[첨부 파일]

mainClass.java

QuickSort.java