[알고리즘/정렬 알고리즘] 퀵 정렬(Quick sort) Java, Python

퀵 정렬(Quick sort) 알고리즘의 개념

• 퀵 정렬(Quick sort)은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘
• '찰스 앤터니 리처드 호어(C. A. R. Hoare)가 개발한 정렬 알고리즘
• 불안정 정렬에 속하며, 원소들과의 비교만으로 정렬을 수행
• 분할 정복 알고리즘 중 하나

퀵 정렬(Quick sort) 알고리즘 세부 과정

1. 먼저 하나의 요소를 선택한다. 이렇게 고른 요소를 피벗(pivot)이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 값을 피벗기준 왼쪽으로, 큰 값을 피벗기준 오른쪽으로 정렬한다.
3. 피벗을 제외한 왼쪽 값들과 오른쪽 값들을 다시 정렬한다.
4. 위처럼 나눈 값들의 길이가 1이 될 때까지 반복한다.

퀵 정렬(Quick sort) 알고리즘 예제

• 배열의 요소가 5, 7, 1, 4, 6, 2, 3, 9, 8 순으로 저장돼있고 오름차순을 기준으로 정렬할 때 예를 확인해보자

pivot값을 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 나누는 과정

 

• 위처럼 left값이 right값보다 크면 반복문이 종료된다.

 

두 번째 단계

• 첫 번째 단계가 끝나고 구분한 기준으로부터 각각 나눠 left와 right, pivot을 두고 첫 번째와 같은 계산을 반복한다
• 분할 정복 단계가 나뉜 배열의 크기가 1일 때까지 진행한다.

[Java 코드]

public class QuickSort {
    
    public static void swap(int[] arr, int pl, int pr) {
        int temp = arr[pl];
        arr[pl] = arr[pr];
        arr[pr] = temp;
    }
    
    public static void quickSort(int[] arr, int left, int right) {
        int pl = left;
        int pr = right;
        int pivot = arr[ (arr[left] + arr[right]) / 2];
        
        do {                                //정복단계
            while(arr[pl] < pivot) pl++;
            while(arr[pr] > pivot) pr--;
            if(pl <= pr) {
                swap(arr, pl, pr);
                pl++;
                pr--;
            }
        }while(pl <= pr);
        
        if(left < pr) quickSort(arr, left, pr);
        if(pl < right) quickSort(arr, pl, right);
        
    }
    
    public static void main(String[] args) {
        int[] arr = { 5, 7, 1, 4, 6, 2, 3, 9, 8 };
        int N = arr.length;
        quickSort(arr, 0, N-1);
        
        for(int a : arr) {
            System.out.print(a +" ");
        }
    }
}

 

[Python 코드]

def quick_sort(arr):
    if len(arr) < 2:
        return arr
 
    pivot = arr[0]  # 파이썬에서는 맨 처음 값을 피봇으로 정해보겠다.
    left = [i for i in arr[1:] if i <= pivot]  # 피벗과 같은 값이 사라지는 것을 방지
    right = [i for i in arr[1:] if i > pivot]
    newarr = quick_sort(left) + [pivot] + quick_sort(right)
 
    return newarr
 
 
arr = [5, 7, 1, 4, 6, 2, 3, 9, 8]
arr = quick_sort(arr)
 
print(arr)