퀵 정렬 알고리즘

퀵 정렬(quick sort)은 지금까지 가장 많이 쓰고 있는 정렬 알고리즘이다. 

이유는 말그대로 빠르기 때문이다.

 

퀵정렬, 병합정렬 두 알고리즘은 프로그래밍에서 정렬 라이브러리의 근간이 되는 알고리즘이 된다.

 

바로 퀵 정렬에 대해 알아보자.

 

퀵 정렬

 

퀵 정렬에서는 '피벗(pivot)'이라는 용어를 사용하는데

과환하기 위한 기준이 되는 숫자 혹은 수치를 의미한다.

 

퀵 정렬은 여러 파트를 나누어서 정렬을 하게 되는데 일단 한번 살펴보자.

 

 

퀵 정렬은 왼쪽 오른쪽을 나눠서 진행 방향을 나눠서 시작하는데 

왼쪽에서 진행될때는 피벗보다 큰 수를 선택하고, 왼쪽에서는 피벗보다 작은 수를 선택한다.

 

선택 된 수는 서로 바뀐다.

 

part 1

5 7 9 0 3 1 6 2 4 8이 배열 상에 존재한다고 하자.

 

step 0 

리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 '5'이다.

왼쪽에서부터 5보다 큰 데이터를 선택하므로 7이 선택되고, 오른쪽에서부터는 5보다 작은 4가 선택된다.

그럼 7과 4를 바꿔준다.

---->            <----

5 7 9 0 3 1 6 2 4 8           -->              5 4 9 0 3 1 6 2 7 8

 

 

step 1

다음 계속 진행한다. 왼쪽에서 피벗(5)보다 큰 수 는 9 오른쪽에서 피벗보다 작은 수는 2가 된다.

그럼 또 다시 9와 2를 바꿔준다.

---->            <----

5 4 9 0 3 1 6 2 7 8          -->               5 4 2 0 3 1 6 9 7 8

 

step 2

계속 진행한다. 이번에는 왼쪽에서 피벗(5) 보다 큰 수를 찾으려 했지만 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈렸다. 이럴 때는 엇갈린 수(1, 6) 중에 작은 값을 피벗(5)와 위치를 바꿔주면 된다. 즉, 1과 5를 바꿔준다.

 

---->            <----

 5 4 2 0 3 1 6 9 7 8         -->              1 4 2 0 3 5 6 9 7 8

 

step 3

위치를 바꿔준 후 리스트를 살펴보면 피벗(5)을 중심으로 왼쪽 오른쪽을 살피면,

왼쪽은 피벗(5)보다 작은 수들이 오른쪽은 피벗(5)보다 큰 수들이 모여 있다.

이렇게 나눠지면 파트를 두가지로 나눠서 다시 순열 작업을 진행 하면 된다.

 

 

 

part 2

step 1

왼쪽 파트의 피벗은 1이 되고 위  과정처럼 왼쪽 진행방향에서는 1보다 큰 수, 오른쪽 진행 방향에서는 1보다 작은 수를 찾아

서로 바꿔주면 된다.

여기서는 4와 0이 선택되므로 바꿔주면

->       <-

1 4 2 0 3  -->  1 0 2 4 3

 

중간 생략

 

ste 2

계속 정렬을 실행하다 보면 왼쪽 리스트는  0 1 2 3 4로 정렬 될 것이다.

 

 

part 3

과정은 위와 동일하다.

step 1

->    <-

6 9 7 8  -->   6 7 9 8 

 

결국 6 7 8 9

 

0 1 2 3 4 5 6 7 8 9가 된다.

 

파이썬 코드로 한번 만들어보자.

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]


def quick_sort(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]
  quick_sort(array, start, right - 1)
  quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)