[Python] 퀵 정렬 알고리즘/ 이것이 코딩테스트다 정렬편

 

퀵 정렬
"기준을 정하고 기준보다 큰 데이터와
작은 데이터의 위치를 바꾸는 정렬"

 

우리는 정렬할 배열의 0번째 인덱스를 기준으로 삼을 것이다.

이 기준을 피벗이라고 부른다.

퀵 정렬을 사용하여 리스트 [5,7,9,0,3,1,6,4,8]을 오름차순으로 정리해보도록 하자

 

(1) 리스트의 왼쪽부터 피벗보다 큰 값을 찾고, 오른쪽부터는 피벗보다 큰 값을 찾은 후,

둘의 위치를 바꿔준다

 

 

(2) 다시 왼쪽부터 탐색하여 피벗(5)보다 큰 수(9), 작은 수(3)의 위치를 바꿔주자

 

 

(3) 위 과정을 반복하게 되면 작은 수와 큰 수가 엇갈리게 되어 바꿀 수 없는 상황이 온다 !!

(4) 이럴 땐 작은 수와 피벗의 위치를 바꾼다

 

(5) 이렇게 되면 피벗의 왼쪽은 피벗보다 작은 수 

오른쪽은 큰 수가 정렬된다.

 

(6) 각각 나누어 또 다시 퀵정렬을 실행하여, 더 이상 정렬할 게 없을 때까지 반복한다.

(7)

정렬이 끝나게 되면 리스트는 오름차순이 되고 퀵정렬은 마무리가 된다.

 

 

 

 

코드작성

 

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

def quick(arr):
  if len(arr) <= 1: #리스트 값이 1개이면 종료
    return arr
    
  pivot = arr[0] #기준이 될 피벗
  tail = arr[1:] #피벗을 제외한 나머지 리스트
  
  left = [x for x in tail if x <= pivot] #피벗을 제외한 리스트 tail 중 피벗보다 작은 값을 담음
  right = [x for x in tail if x > pivot] #피벗을 제외한 리스트 tail 중 피벗보다 큰 값
  
  return quick(left) + [pivot] + quick(right) # 왼쪽 + 피벗 + 오른쪽 합침 재귀함수로 반복됨

print(quick(arr))

pivot: 리스트의 0번째로 기준이 된다.

tail: 피벗을 제외한 나머지 [1:]

왼쪽과 오른쪽으로 나뉘어  왼쪽에는 피벗보다 작은 값, 오른쪽엔 피벗보다 큰 값을 배열로 만듬

왼쪽 + 피벗 + 오른쪽으로 나눠서 다시 배열에 담겨 다시 arr이 됨

재귀함수를 통해 더 이상 바꿀 수 없을 때까지 실행한다.

 

퀵 정렬의 단점:
이미 정리되어있을 경우, 시간복잡도가 복잡함