퀵 정렬(quick sort)

1) 퀵 정렬(quick sort) 이란?

- 정렬 알고리즘의 꽃

- 기준점(pivot) 을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성

- 각 왼쪽(left), 오른쪽(right) 은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함

- 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴

 

 

2) 알고리즘 구현

 

▼ 파이썬

def qsort(data):
    if len(data) <= 1:
        return data
       
    left, right = list(), list()
    pivot = data[0]
    
    for idx in range(1, len(data)):
        if pivot > data[idx]:
            left.append(data[idx])
        else:
            right.append(data[idx])
    
    return qsort(left) + [pivot] + qsort(right)

1. 만약 리스트의 갯수가 한 개이면 해당 리스트를 리턴

2. 그렇지 않은 경우, 리스트 제일 앞의 데이터를 기준점(pivot) 으로 놓기

3. left, right = list(), list()

4. for idx in range(1, len(data)) 로 데이터를 호출

5. 호출한 데이터를 기준점(pivot)과 비교

   - 기준점(pivot) 보다 작으면 left.append(호출한 데이터)

   - 기준점(pivot) 보다 크면 right.append(호출한 데이터)

6. return qsort(left) + [pivot] + qsort(right) 로 재귀 호출

 

결과

import random

data = random.sample(range(100), 10)
print(qsort(data))

 

 

▼ 파이썬(위의 코드 간소화)

def qsort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]
    
    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    
    return qsort(left) + [pivot] + qsort(right)

 

결과

import random

data = random.sample(range(100), 10)
print(qsort(data))

 

 

▼ 파이썬(동빛나님 코드)

int data[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

void show() {
    for(int i = 0; i < data.length; i++) {
    	print(data[i]);
    }
}

void quickSort(int[] arr, int start, int end) {
    if(start >= end) {	// 원소가 1개인 경우 그대로 두기
        return;
    }
    
    int key = start;	// 키는 첫 번째 원소
    int i = start + 1, j = end, tmp;
    
    while(i <= j) {		// 엇갈릴 때까지 반복
        while( i <= end && arr[i] <= arr[key] ) {	// 키값보다 큰 값을 만날 때까지
            i++;
        }
        while( j > start && arr[j] >= arr[key] ) {	// 키값보다 작은 값을 만날 때까지
            j--;
        }
        
        if(i > j) {	// 현재 엇갈린 상태면 키값과 교체
            tmp = arr[j];
            arr[j] = arr[key];
            arr[key] = tmp;
        } else {	// 엇갈리지 않는다면 i 와 j 교체
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    quickSort(arr, start, j - 1);
    quickSort(arr, j + 1, end);
}

int main(void) {
    quickSort(arr, 0, number - 1);
    show();
    return 0;
}

 

 

 

▼ 자바 

public class Test {
	
    public static void main(String[] args) throws IOException {
        int[] arr = { 3, 6, 1, 7, 4, 5, 9, 10, 1, 8, 2 };
        quickSort(arr);
        for(int i: arr) {
            System.out.println(i);
        }
    }
    
    public static void quickSort(int[] arr) {
    	quickSort(arr, 0, arr.length - 1);
    }
    
    private static void quickSort(int[] arr, int left, int right) {
    	// 더이상 분할이 되지 않으면 종료
        if(left >= right) return;
        
        int mid = partition(arr, left, right);
        quickSort(arr, left, mid - 1);
        quickSort(arr, mid, right);
    }
    
    // 분할
    private static int partition(int[] arr, int left, int right) {
    	int pivot = arr[(left + right) / 2];
        
        // 엇갈리지 않으면 계속 반복
        while(left <= right) {	// 1. 배열에 값이 중복해서 들어가는 경우는 <=
        	
            // left 와 right 찾기
            while(arr[left] < pivot) left++;
            while(arr[right] > pivot) right--;
            
            // 엇갈리지 않으면 swap 
            if(left <= right) {	// 2. 1과 동일
            	swap(arr, left, right);
                left++;
                right--;
            }
        }
        return left;
    }
    
    private static void swap(int[] arr, int a, int b) {
    	int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

 

 

3) 알고리즘 분석

- 병합 정렬과 유사, 시간 복잡도는 O(nlogn)

- 제일 처음 pivot 이 가장 크거나 가장 작은 경우 모든 데이터를 비교하는 상황이 나옴(최악의 경우) : O(n^2)

 

 

 

참고)

1. 패스트캠퍼스 '코딩 알고리즘 온라인 완주반'

2. https://blog.naver.com/ndb796/221226813382

5. 퀵 정렬(Quick Sort)

3. 퀵 정렬이란? (tistory.com)

퀵 정렬이란?