알고리즘 [Algorithm] - 퀵 정렬 (4) (C, Python)

퀵 정렬

이번에는 퀵 정렬에 대해 알아보자. 퀵 정렬이란 대표적인 '분할 정복'알고리즘으로 평균 속도가 O(N*logN)인 알고리즘이다. 이전에 배웠던 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 데이터의 갯수가 10만개가 넘어가면 사용하기 매우 어려운 알고리즘이다. 따라서 더욱 빠른 정렬 알고리즘이 필요하고 대표적인 알고리즘이 퀵 정렬 알고리즘이다.

---

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

---

퀵 정렬은 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 정렬한다. 다시 말해 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

 

예시를 통해 보자.

퀵 정렬에는 기준 값이 사용된다. 이를 피벗(Pivot)이라고도 하는데, 보통 첫 번째 원소를 피벗 값으로 설정하고 사용한다. 문제와 다른 배열을 사용해보자.

 

(3) 7 8 1 5 9 6 10 2 4

먼저 3(피벗값)보다 큰 숫자를 왼쪽부터 찾고, 3보다 작은 숫자를 오른쪽부터 찾는다. 이때 3보다 큰숫자는 바로 7, 3보다 작은 숫자는 2가 나오므로 둘의 자리를 바꿔준다. 다음도 똑같이 큰 숫자를 왼쪽부터 찾고, 3보다 작은 숫자를 오른쪽부터 찾는다. 8과 1의 자리를 바꿔준다. 이후 왼쪽부터 찾은 큰 숫자와 오른쪽부터 찾은 작은 숫자가 엇갈린다면 피벗 값과 작은 값의 자리를 바꿔준다. 이렇게 하면 3을 기준으로 3의 왼쪽에는 3보다 작은 값들이, 3의 오른쪽에는 3보다 큰 값들이 위치하게 된다. 3을 기준으로 분할된 배열에 대해 계속해서 같은 과정을 진행한다. 

 

#include <stdio.h>

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

void show(){
	int i;
    for(i=0; i<number; i++){
    	printf("%d",data[i]);
        }
}

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

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

퀵정렬 알고리즘은 재귀함수를 통해 구현되며, 기본적으로 N번씩 탐색하되 반으로 쪼개 들어간다는 점에서 log N을 곱한 복잡도를 가진다. 퀵 정렬의 평균 시간 복잡도는 O(N*logN)이지만, 최악 시간 복잡도는 O(N^2)이다.

 

정렬이 되어있는 경우를 생각해보자.

---

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 2 3 4 5 6 7 8 9 10

 

---

위와 같이 이미 정렬이 완료된 경우 퀵정렬의 시간 복잡도는 O(N^2)에 가깝다. 하지만 이전에 다룬 삽입정렬을 사용하면 굉장히 빠르게 문제를 풀 수 있다. 즉 정렬할 데이터의 특성에 따라 적절한 알고리즘을 사용하느 것이 중요하다.

 

파이썬

def quicksort(data,start,end): #start는 분할된 집합의 첫번째 값, end는 분할된 집합의 마지막 값
  if start >= end: #원소가 1개인 경우
    return
  
  key = start # 피벗 값은 첫번째 원소
  i = start +1
  j = end 

  while ( i<= j): #엇갈릴 때 까지 반봅
    while i<=end and data[i] <= data[key] : # i가 오른쪽 값보다 작다면 
      i+=1
    while(data[j]>= data[key] and j>start): # j가 왼쪽보다 크다면
      j -=1

    if i>j: #현재 엇갈린 상태면
      temp = data[j]
      data[j] = data[key]
      data[key] = temp
    else:
      temp = data[j]
      data[j] = data[i]
      data[i] = temp
  quicksort(data,start,j-1)
  quicksort(data,j+1,end)


a = [1,10,5,8,7,6,4,3,2,9]
quicksort(a,0,len(a)-1)
a

 

---

이 글은 나동빈님의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 참고해 작성하였습니다.

https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz