[Algorithm] 쿽 정렬은 뭐야?

퀵 정렬은 기준값(처음에는 제일 첫 번째 원소)을 기준으로 다른 원소들의 값을 비교하는 것만으로 수를 정렬하는 방법이다.

 

쿽 정렬은 배열의 왼쪽에서 피벗값 기준 큰 값을 찾고, 배열의 오른쪽에서 피벗값 기준 작은 값을 찾아서 2가지 값을 비교하여 큰 값의 위치가 작은 값의 위치보다 오른쪽에 위치해 있다면 작은 값과 피벗값의 위치를 바꿔주고, 반대의 경우에는 작은 값과 큰 값의 위치를 바꿔주는 연산을 정렬이 완료될 때까지 반복하는 정렬 방식이다.

 

앞서 말한 삽입 정렬과 선택 정렬은 O(N^2)의 시간 복잡도를 가지는 알고리즘으로 데이터의 개수가 10만만 넘어도 사용하기 힘들다는 단점이 있었다. 그렇기 때문에 더욱 빠른 알고리즘이 필요하고 퀵 정렬이 이에 속한다. 퀵 정렬은 평균 속도 O(N*logN)이다.

 

다음은 1부터 5까지의 숫자를 무작위로 배치한 정보를 퀵 정렬을 이용하여 정렬하는 방식이다.

퀵 정렬 순서 1번째

4,5,3,2,1 중에 제일 앞에 있는 원소 4를 정렬되었다는 가정을 하고, 피벗값으로 설정한다.

주황색 배경은 피벗값, 진한 회색 배경은 정렬 중인 값, 파란색 배경은 정렬된 값으로 하겠다.

 

퀵 정렬 순서 2번째

배열에서 왼쪽에서 4보다 큰 값은 5이고, 오른쪽에서 4보다 작은 값은 1이다. 이때 5의 위치가 1보다 왼쪽에 위치하므로 1과 5의 위치를 바꿔준다.

 

퀵 정렬 순서 3번째

배열의 왼족에서 4보다 큰 값은 5이고, 오른쪽에서 4보다 작은 값은 2이다. 이때 5의 위치가 2보다 오른쪽에 위치하므로 피벗값과 2의 위치를 바꿔주고, 5는 가만히 있는다.

 

퀵 정렬 순서 4번째

피벗값이었던 4는 왼쪽으로는 자신보다 작은 수가 존재하고, 오른쪽에는 자신보다 큰 수가 있기 때문에 정렬된 것으로 생각한다. 그리고 피벗값이었던 4를 기준으로 분할하여 쿽 정렬을 실행시킨다. 따라서 분할된 배열의 첫 인덱스인 2와 5가 피벗값으로 지정된다.

 

2,1,3의 경우 피벗값 2를 기준으로 큰 값은 3, 작은 값은 1이 된다. 3의 위치가 1보다 오른쪽에 위치하므로 피벗값과 1의 위치를 바꿔준다.

 

5의 경우 더 이상 퀵 정렬을 실행시켜줄 배열이 없으므로 정렬 된 상태로 만든다.

 

퀵 정렬 순서 5번째

1과 3은 이후 연산에서 피벗값으로 설정되지만 퀵 정렬을 실행시켜줄 배열이 없으므로 정렬된 상태로 만든다.

 

퀵 정렬 순서 6번째

위의 과정을 통해서 삽입 정렬의 순서를 알아보았다. 위에서 말했듯이 퀵 정렬의 평균 O(N*logN)의 시간 복잡도를 가지지만 최악의 경우에는 O(N^2)의 시간 복잡도를 가지게 된다. 여기서 말하는 최악의 경우는 거의 정렬된 정보일 경우를 말한다.

 

다음은 퀵 정렬의 과정을 코드로 표현한 것이다.

 

array = [4,5,3,2,1]
 
def quickSort(array,start,end):
  if start >= end:
    return
  pivot = start
  left = start + 1
  right = end
  
  while left < right:
    while left <= end and array[left] <= array[pivot]:
      left += 1
    while right > start and array[right] >= array[pivot]:
      right -= 1
    
    if left>right:
      array[right], array[pivot] = array[pivot], array[right]
    else:
      array[left], array[right] = array[right], array[left]
    
  quickSort(array, start, right - 1)
  quickSort(array, right + 1, end)
 
quickSort(array, 0, len(array)-1)
print(array)

 

퀵 정렬은 함수로 하나의 과정을 만들고, 재귀 함수를 이용하여 반복해주는 방식을 사용한다.

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬