먹고 기도하고 코딩하라

파이썬으로 정렬 알고리즘 본문

자료구조&알고리즘/이론

파이썬으로 정렬 알고리즘

2G Dev 2021. 7. 26. 00:05
728x90
728x90

 

1. 선택 정렬

선택 정렬(selection sort)이중 for 루프를 이용해 자료구조를 정렬하는 정렬 방식이다.

바깥 루프는 0에서 자료 개수 n - 1까지, 안쪽 루프는 바깥 루프의 인덱스 i + 1부터 자료 개수 n까지 루프를 돌린다. 일반화하면 시간복잡도는 O(n^2)이다.

매 바깥 루프가 시작할 때마다 min_idx는 i로 정해진다. i 이전 인덱스까지는 이미 정렬이 됐다고 보고(실제로 그렇다), 매 시작 시마다 정렬이 안 된 것들 중에서 가장 작은 값을 가리키는 인덱스는 임의로 i로 설정하겠다 이 말씀이다.

오름차순 정렬일 경우 바깥 for 루프가 한 번 끝나면, i 인덱스는 남은 값들 중 가장 작은 값을 담는 인덱스가 된다. 왜냐하면, 안쪽 for 루프에서 나온 min_idx가 남은 데이터들 중 가장 작은 값을 가리키는 인덱스이기 때문에 이것과 i를 바꾸면 i가 곧 가장 작은 값을 가리키는 인덱스가 되기 때문이다.

안쪽 for 루프에서 현재 j 인덱스(안쪽 for 루프의 인덱스) 값과 min_idx 인덱스 실제 값 중 어떤 것이 더 작은지 비교하고, j 인덱스 안의 값이 더 작다면 min_idx를 j로 변경한다.

들여쓰기에 주의해서 코드를 보자.

 

def solution(l):
  for i in range(len(l)-1):
    min_idx = i
    for j in range(i+1, len(l)):  # i부터 시작할 필요가 없는 게 그럼 l[i] == l[i] 하는 꼴이기 때문에 i+1부터 시작
      if l[min_idx] > l[j]:
        min_idx = j # 더 작은 값을 찾았다면 min_idx를 바꿔주는 작업도 필요
    l[i], l[min_idx] = l[min_idx], l[i]


l = [2, 4, 5, 1, 3]
solution(l)
print(l)

이 때,

for i 루프 1회전이 끝나면 [1, 4, 5, 2, 3]이 된다. 즉, 1, 2, 3, 4, 5 중 가장 작은 값인 1이 i의 위치에 간 것이다.

for i 루프 2회전이 끝나면 [1, 2, 5, 4, 3]이 된다. 남은 2, 3, 4, 5 중 가장 작은 값인 2가 i의 위치에 갔다.

for i 루프 3회전이 끝나면 [1, 2, 3, 4, 5]가 된다. 남은 3, 4, 5 중 가장 작은 값인 3이 i의 위치에 갔다.

for i 루프 4회전이 끝나면 [1, 2, 3, 4, 5]가 된다. for j 루프도 딱 한 번만 돌리고, 4와 5가 제 위치를 찾았기 때문에 특별히 값을 서로 바꿔주지 않고 종료한다. 

 

더보기에는 그림이 포함되어 있다.

 

만약 내림차순 정렬로 바꿔주고 싶다면 if 문의 대소비교연산자를 거꾸로 바꿔주면 된다.

 

(핵심) min_idx 값만 안쪽 루프에서 계속 바꿔주고, 실제로 값을 바꿔 앞쪽 i 인덱스가 가장 작은 값을 담게끔 값을 바꿔주는 건 내부 loop가 모두 끝난 다음에 일어난다. 즉, 실제로 값을 바꾸는 건 바깥 for 루프 횟수만큼 일어난다. 인덱스를 기반으로 값을 서로 trade하는 식으로 정렬하는 방식이다. 0~n-1까지 순차적으로 정렬하게 된다. 

비교하는 시간복잡도는 O(n^2), 실제 교환하는 시간복잡도는 O(n)이다. for j 루프 안의 if 연산이 핵심 연산이므로 요소 개수가 n개일 때 n^2번 정도를 실행하기 때문이다.

 

 

2. 삽입 정렬

삽입 정렬(insertion sort)이중 for 루프 혹은 for 루프와 while 루프를 이용해 구현하는 정렬 알고리즘이다.

바깥 루프는 1~n까지 도는데 for 문 안의 while 루프 조건이 좀 특이하다.

 

def solution(l):
  for i in range(1, len(l)):  # 1부터 n까지 i
    key = l[i]  # 일단 key는 l[i]의 값. 아직 정렬이 안 된 정렬해야 하는 값임
    # 인덱스가 아니라 아예 데이터를 저장하는 방식
    j = i - 1 # j는 i보다 1 작은 인덱스로 시작
    
    while j >= 0 and l[j] > key:  # j가 0보다 크고, j 안의 값이 key보다 크다면
      l[j+1] = l[j] # 앞의 값을 뒤로 복사한다(덮어씀)
      j -= 1  # 그리고 j는 앞으로 한 칸 옮김
    
    l[j+1] = key  # while 루프에서 탈출하면, 루프 1회마다 l[j+1]에 현재 key를 복사함. 
    # 이제 찾은 위치에 정렬 대상인 key를 삽입한다

d = [2, 4, 5, 1, 3]
solution(d)
print(d)

선택 정렬과 다른 점을 살펴보자. 일단 key는 인덱스가 아니라 정렬해야 할 값 자체를 가지고 있다는 점이 다르다.

그 다음 j는 for 루프가 아니라 while 문 조건으로 쓰이는데, j는 i보다 1 작은 인덱스로 시작한다.

j가 0보다 같거나 크고(리스트에 접근할 수 있는 인덱스여야 하니까. 물론 파이썬은 음수 인덱싱이 가능하지만 뒤로 넘어가는 건 이 정렬 알고리즘에서 배제해야 하므로 0보다 같거나 커야 함), 리스트의 j번 인덱스가 담은 값이 key보다 큰 경우이다.

 

자 한 번 곰곰이 생각해보자. 루프를 돌 때 j가 i보다 커질 수 있을까?

그렇지 않다. j를 조작하는 건 위 코드에서 2번 나오는데 바로 while 문 전에 j = i - 1 문장과 while 루프 안에서의 j -= 1 문장이다. j에는 덧셈 연산이 없고 뺄셈 연산뿐이다. 그러므로 j는 i보다 커질 수 없다.

그래서, l[j] > key가 나타내는 것은 l[i]번 인덱스보다 왼쪽에 l[i]번 값보다 더 큰 것이 있냐? 하고 묻는 것이다. 만약 그렇다면 정렬이 필요한 경우이다. while 루프는 j가 0보다 작아지거나(즉, 왼쪽에 더 이상 비교할 값이 없거나) l[j] <= key일 때(즉, 왼쪽의 값이 key보다 작거나 같아서 정렬할 필요 없을 때) 탈출하게 된다. 

이 때 선택 정렬과는 다른 방식으로 독특하게 진행하는데, 이 조건에 해당한다면 l[j+1], 즉 j 한 칸 뒤에 있는 값에 l[j] 값을 복사해서 덮어쓰는 것이다. 그리고 j를 앞으로 한 칸 옮긴다. 

이렇게 대책없이 덮어쓰면 l[j+1] 값은 어떻게 되는 거지 궁금할 것이다. 걱정할 거 없다. 맨 처음 l[j+1] = l[j]가 실행되는 경우라면 이 때에 l[j+1] 값은 key가 들고 있다. 그리고 while 루프 처음이 아니더라도, l[j+1] 값은 이미 이전에 while 루프에서 l[j+1] 자리에 덮어씌워놨기 때문에 값이 유실될 염려는 없다.

 

for i 루프 1회전이 끝나면, 값은 2 4 5 1 3 이 된다. (key가 4인데, 왼쪽에 2보다는 4가 크기 때문이다.)

for i 루프 2회전이 끝나면, 값은 2 4 5 1 3 이 된다. (key가 5인데, 왼쪽의 2, 4보다는 5가 크기 때문이다.)

for i 루프 3회전이 끝나면, 값은 1 2 4 5 3 이 된다. (key가 1인데, 왼쪽 값 전부보다 1이 작기 때문에 맨앞으로 간다.)

for i 루프 4회전이 끝나면, 값은 1 2 3 4 5 가 된다. (key가 3인데, j = 1일 때 l[j] = 2라서 여기서 멈추고, l[2] 자리에 들어간다.)

 

더보기에는 그림이 포함되어 있다.

 

(핵심) 오름차순 정렬의 경우 key보다 큰 값이 앞에 있을 때, 큰 값이 있는 위치와 key값의 위치를 trade하는 게 아니라 key값의 왼쪽에 더 이상 key보다 큰 값이 없을 때까지 값들을 한 칸씩 뒤로 밀고 key가 가장 앞에 들어가는 정렬 방식이다. 그래서 1회 루프가 끝났다고 해도 맨 앞에 가장 작은 값이 있으리라는 보장이 없다. 심지어 초반에는 루프가 끝나도 아무것도 제자리를 찾지 못할 수도 있다.

모두 정렬되어 있을 때는 아주 효율적으로 진행할 수 있지만, 역정렬이 되어 있는 경우라면 매 루프마다 while 문을 통과해야 하기 때문에 아주 비효율적이다. 정렬할 항목의 수에 비해 아주 작은 저장 공간을 추가로 사용하는 제자리 정렬(in-place sort)의 한 예이다. key와 i, j 정도만 추가로 사용하기 때문이다. 

평균적인 시간복잡도는 O(n^2)이다.

 

 

3. 거품 정렬

거품 정렬(bubble sort)은 리스트 요소의 이웃 요소와 비교(인접한 두 항목을 비교)해 이웃 요소와 정렬이 안 되어 있을 경우 서로 자리를 바꿔주는 방식의 정렬이다. 이웃 요소와 비교해 바꾸는 것이 거품이 올라오는 것 같아서 버블 정렬이라는 이름이 붙었다는 설명을 몇 년 전 알고리즘 강의에서 들었는데... 글쎄 공감은 잘 안 된다. 여튼 오름차순 정렬의 경우, 리스트의 맨 끝부터 정렬이 완료된다. (맨 끝에 가장 큰 요소가 자리를 잡으며 루프 1회전이 끝나게 됨)

def solution(l):
  for i in range(len(l)-1):
    for j in range(len(l)-1-i):
      if l[j] > l[j+1]:
        l[j], l[j+1] = l[j+1], l[j]

d = [10, 2, 3, 4, 1, 7, 0]
solution(d)
print(d)

이중 for 루프를 사용해서 구현한 거품 정렬이다. 루프를 돌리는 range 값에 주목하라. 바깥 루프는 전체 리스트 l - 1, 안쪽 루프는 전체 리스트 l - 1 - i이다. 안쪽 루프에서 i를 빼주는 이유는 for i 루프 1회전이 끝나면 적어도 1개의 요소는 정렬을 통해 맨끝의 제자리를 찾은 것이기 때문에 빼는 것이다.

그것을 제외하면 심플하다. min_idx나 max_idx 같은 걸 사용하지도 않고 그냥 j와 j+1 인덱스의 실제 값을 비교해 정렬이 안 되어 있으면 2개를 계속 바꿔주는 방식으로 진행한다. 사정이 이렇다 보니 좀 번잡스럽긴 하다. 

 

for i 루프 1회전이 끝나면 결과는 [2, 3, 4, 1, 7, 0, 10]이 되어 10이 제자리를 찾는다.

for i 루프 2회전이 끝나면 결과는 [2, 3, 1, 4, 0, 7, 10]이 되어 7이 제자리를 찾는다.

for i 루프 3회전이 끝나면 결과는 [2, 1, 3, 0, 4, 7, 10]이 되어 4가 제자리를 찾는다.

for i 루프 4회전이 끝나면 결과는 [1, 2, 0, 3, 4, 7, 10]이 되어 3이 제자리를 찾는다.

for i 루프 5회전이 끝나면 결과는 [1, 0, 2, 3, 4, 7, 10]이 되어 2가 제자리를 찾는다.

for i 루프 6회전이 끝나면 결과는 [0, 1, 2, 3, 4, 7, 10]이 되어 0과 1이 제자리를 찾아 정렬이 끝난다.

 

더보기에는 그림이 포함되어 있다.

 

(핵심) 안쪽 for 루프의 if 연산이 핵심이다. 정렬은 바깥 for 루프 1회전이 끝날 때마다 가장 큰 값이 가장 오른쪽에 자리를 잡음으로써 이뤄진다.

버블 정렬의 시간복잡도는 O(n^2)이다.

 

 

4. 병합 정렬

병합 정렬(merge sort)재귀 방식을 이용해서 리스트의 요소들을 정렬하는 방식이다. 분할 정복(divide & conquer) 방식으로 문제를 푸는데, divide & conquer란 어떤 문제가 있을 때 그 문제를 작은 단위의 문제로 쪼개서 더 이상 쪼갤 수 없을 때까지 쪼갠 다음 작아진 문제를 해결해서 다시 위로 거슬러 올라가는 방식이다. 분할 정복은 보통 재귀 함수를 이용해서 구현하게 된다.

분할 정복은 다음 3단계로 이뤄진다.

1. 분할 : 해결할 수 있는 단계까지 문제를 분할한다.
2. 정복 : 분할한 문제를 해결한다.
3. 결합 : 분할 결과를 결합해 마무리한다. (문제에 따라 이 단계는 생략하기도 함)

 

def solution(l):
  if len(l) <= 1: return  # 정렬할 리스트 개수가 1개 이하면 정렬 필요 x
  
  # 그룹을 나눠 각각 병합 정렬 호출
  mid = len(l) // 2  # 중간을 기준으로 두 그룹으로 나누기
  g1 = l[:mid]  
  g2 = l[mid:] 
  solution(g1)
  solution(g2)
  
  # 두 그룹 병합
  i1 = 0  # 1번 그룹 인덱스
  i2 = 0  # 2번 그룹 인덱스
  il = 0  # 함수에 주어진 리스트 인덱스

  while i1 < len(g1) and i2 < len(g2):
    if g1[i1] < g2[i2]: # 만약 1번 그룹의 i1 인덱스 실값이 2번 그룹의 i2 인덱스 실값보다 작다면
      l[il] = g1[i1]  # 리스트에는 g1[i1] 값이 먼저 담김
      i1 += 1 # 다음 진행을 위해 인덱스 수 + 1
    else:
      l[il] = g2[i2]
      i2 += 1
    il += 1

  # while 루프 후 남아 있는 자료들을 결과에 추가
  while i1 < len(g1):
    l[il] = g1[i1]
    i1 += 1
    il += 1
  while i2 < len(g2):
    l[il] = g2[i2]
    i2 += 1
    il += 1


d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
solution(d)
print(d)

병합 정렬의 종료 조건은 함수 인자로 넘어온 리스트의 요소 개수가 1 이하일 때이다. 이 경우에는 리스트에 아무것도 없거나 딱 한 개의 요소만 들어 있어 정렬이 필요없는 경우이므로 종료한다.

리스트를 반으로 계속 나눠서 정렬되지 않은 리스트를 만들고, 이 리스트 요소 개수가 1이 될 때까지 리스트를 반으로 계속 쪼개서 병합 정렬 함수를 호출해 리스트를 정렬, 병합하는 방식이다.

실제로 병합 정렬이 이뤄지는 과정은 solution(g1), solution(g2)에서 모두 return이 이뤄진 다음에 일어나게 된다.

병합 정렬을 이용해 오름차순 정렬하는 과정은 다음과 같다.

 

1. 일단 리스트 요소 개수를 반으로 나눠 이것을 토대로 2개의 그룹을 만든다. 요소 개수가 홀수일 때도 걱정할 건 없다. // 연산자로 나누면 앞의 g1 요소 개수는 g2 요소 개수보다 1 작게 될 뿐 나누는 데는 문제 없다. (분할)

2. 이 2개의 리스트를 인자로 넘겨 solution을 각각 호출한다.

3. 만약 둘 다 return이 되어 넘어왔다면 더 이상 나눌 수 없을 때까지(혹은 나눈 문제를 해결한 다음임) 나뉜 것이므로 병합하기 위해 g1과 g2, 전체 리스트 l의 인덱스를 만들어 각각 0으로 초기화시킨다.

4. i1과 i2가 각각 g1, g2의 길이 값을 넘지 않는 이상(즉, 어느 한쪽이 전부 소모되지 않은 이상) 다음을 진행한다.

4-1. g1[i1]과 g2[i2] 값을 비교한다.

만약 g2[i2]가 더 크다면 g1[i1]이 리스트 앞쪽에 들어가야 하므로, l[il]에 g1[i1]을 대입한 뒤 i1 인덱스를 1 증가시킨다. 

만약 g1[i1]이 더 크다면 g2[i2]가 리스트 앞쪽에 들어가야 하므로, l[il]에 g2[i2]을 대입한 뒤 i2 인덱스를 1 증가시킨다.

두 경우 모두 전체 리스트 l에 값이 들어가게 되므로 while 루프 1번을 돌 때마다 il 인덱스도 1 증가시켜 준다.

5. 위의 while 루프 탈출 조건에 걸려서 탈출하게 됐을 때, g1이나 g2에 남은 데이터들이 있을 수 있다. 이 경우에는 각 그룹에 남은 것들을 전체 리스트 l에 순차적으로 추가한다. 이 때는 값 비교를 따로 하지 않는다. 

정렬 안 하고 그냥 이렇게 넘기면 어떡하냐고? 괜찮다. 남은 것들은 이미 리스트에 들어간 값들보다 큰 값으로, 작게 호출한 함수에서 이미 정렬이 되어 있는 것들이다. 전체적으로 정렬이 안 되었을지라도 괜찮다. 그것은 상위 함수에서 해결할 일이다.

 

그럼 이제 [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]를 어떻게 병합 정렬로 정렬하는지 살펴보자.

5개로 나뉘었을 때에는 미미하게 정렬이 되다가 마지막에 합쳐질 때 한꺼번에 정렬이 되는 것처럼 보이지만, 사실 부분부분끼리도 정렬이 잘 되어 있는 상태였기 때문에 마지막에 정렬이 잘 된 것이다.

마지막 단계에서 병합하는 과정만 살펴보겠다.

 

어떤가? 가장 마지막 단계에서도 어떤 한 그룹에만 원소가 남을 수 있다. 이 때는 그냥 남은 원소들을 순서대로 리스트 끝에 넣어주면 끝인데, 왜냐하면 이 그룹이 아닌 다른 그룹이 모두 리스트에 들어간 것은, 그 다른 그룹의 원소 전부가 그룹의 남은 원소들보다 작기 때문이다.

또 남은 원소들은 이미 이전 단계에서 정렬이 되어 있는 상태이다. 그래서 그대로 넣어주면 정렬 끝이다.

 

(핵심) 더 이상 나뉘지 않을 때까지 나눴다가 나눈 두 그룹을 각자 함수에서 병합하는 알고리즘이다. 분할 과정이 재귀적이다. 이 때 종료 조건이 리스트 요소 개수가 1 이하라는 점에 주목하고, while 루프에서는 그룹 간 값을 비교해 리스트 앞쪽에 넣고, 남은 것은 일괄적으로 리스트에 넣는다는 것도 기억하면 좋겠다.

분할 정복을 이용한 병합 정렬 시간복잡도는 O(nlogn)이다. 

 

 

5. 퀵 정렬

퀵 정렬(Quick sort)은 병합 정렬처럼 재귀 함수를 이용하여 정렬을 하는 알고리즘인데, 병합 정렬이 리스트의 중간 인덱스를 기준으로 좌우로 그룹을 나눠 계속 쪼개나가 정렬하는 방식이라면 퀵 정렬은 피벗값(pivot)을 두고 그 피벗값과 다른 값들을 비교해 값들을 바꿔나가는 방식이 좀 다르다. 

 

def solution(l, start, end):
    # 정렬 대상이 1개 이하이면 종료
    if end - start <= 0: return

    pivot = l[end] # 기준값을 정함
    i = start
    for j in range(start, end):
        if l[j] <= pivot:	# 피벗값보다 j 값이 작거나 같다면
            l[i], l[j] = l[j], l[i]	# i와 j 실제 값을 바꿔줌
            i += 1	# i 인덱스는 한 칸 뒤로
    l[i], l[end] = l[end], l[i]

    # 재귀 호출
    solution(l, start, i - 1)   # 기준 값보다 작은 그룹을 재귀 호출로 정렬
    solution(l, i + 1, end) # 기준 값보다 큰 그룹을 재귀 호출로 정렬


def quick_sort(l):
    solution(l, 0, len(l)-1)

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quick_sort(d)
print(d)

코드만 보고 무슨 일이 일어나는지 한 번에 알아내기 쉽지는 않지만 일단 살펴보자. quick_sort 함수 내부적으로 solution이라는 함수를 호출하는데, 이 solution은 지금까지 본 여타 정렬 함수들과 달리 인자가 3개이다. 리스트에 start 와 end 값을 인자로 추가한 것이다. len(l)-1 을 한 것은 최초에 solution을 호출했을 때 리스트의 맨 마지막인 end 인덱스로 지정하기 위해서이다(그냥 len(l)을 했다면 out of range 에러가 났을 것이다).

solution을 계속 재귀 호출하는 방식으로 정렬이 이뤄지는데, 종료 조건은 end - start <= 0, 즉 정렬 대상이 1개 이하일 때이다. 이 때는 정렬할 것이 없으므로 그냥 종료한다.

피봇값은 임의로 end 로 정해준다. 그리고 i 는 start 값으로 정하는데, 이 start 실값부터 end 실값까지 비교해 나가며 정렬하는 것, 피벗값의 왼쪽으로는 피벗값보다 작은 값들, 오른쪽으로는 피벗값보다 큰 값들이 오도록 정렬하는 것이 solution 함수의 목표이다. 

 

그럼 이제 어떻게 정렬하는지 그 과정을 살펴보자.

정렬 대상 리스트는 [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]이다.

 

처음 solution(l, 0, 9)가 호출되고 9번 인덱스의 값인 5가 피벗값이 된다. i는 0이다.

j는 0부터 8까지 순회를 돌게 되는데, l[j]가 pivot보다 작거나 같다면 피벗보다 왼쪽에 있어야 하는 값이다. 그러므로 l[i]와 l[j] 값을 서로 바꿔준 다음, i를 1 증가시킨다. i를 1 증가시키지 않으면 아까 바꿔준 l[j] 값을 계속 가리키고 있게 되므로 꼭 1 증가시키는 것을 잊지 말아야 한다.

j가 8보다 커져 루프를 탈출하게 되면 그 때 피봇값과 i 인덱스 값을 바꿔준다. solution(l, 0, 9)에서 for 루프가 끝났을 때 리스트는 

[3, 1, 2, 4, 10, 8, 6, 9, 7, 5]가 되어 있다. i 는 4, 10을 가리키는데 피봇보다 큰 값이다. 여기서 i와 end 의 자리를 바꿔줘서

[3, 1, 2, 4, 5, 8, 6, 9, 7, 10]이 된다. 5를 기준으로 왼쪽으로는 작은 값, 오른쪽으로는 큰 값들이 있을 뿐이지 그 그룹 안에서 아직 정렬은 이루어지지 않았다는 것에 주목하라.

여기서 피봇(5)보다 작은 그룹인 0~3번, 큰 그룹인 5~9번 그룹을 나눠 또 solution 을 실행하게 된다.

solution(l, 0, 3)에서 리스트는 [3, 1, 2, 4]만 있는 것이나 마찬가지다. 불행히도 피봇값은 가장 큰 값인 4이다. 이 경우에는 피봇 왼쪽의 모든 값이 피봇보다 작으므로 i와 j가 같이 움직이게 된다. i 는 3이 되고, solution(l, 0, 2), solution(l, 4, 3)이 호출된다. 이 중 solution(l, 4, 3)은 end - start 값이 0보다 작으므로 그냥 종료한다.

solution(l, 0, 2)에서 리스트는 [3, 1, 2]이다. for 루프가 끝났을 때 리스트는 [1, 3, 2]이고, end 와 i 자리를 바꿔주면 [1, 2, 3]이 된다. 여기서 solution(l, 0, 0), solution(l, 2, 2)를 호출하고, 둘은 정렬 대상이 없으므로 여기서 종료한다. 

여기까지 상황을 정리해 보면 l(0, 3)까지는 [1, 2, 3, 4]로 잘 정렬이 되었다.

 

이제 오른쪽을 살펴본다.

solution(l, 5, 9)에서 피봇값은 10이다. 피봇값 왼쪽으로 전부 작은 값들이므로 i와 j가 같이 움직인다. 리스트는 변화없이 [8, 6, 9, 7, 10]이고, solution(l, 5, 8), solution(l, 10, 9)가 호출된다. 

solution(l, 5, 8)에서 피봇값은 7이다. for 루프가 종료되었을 때 리스트는 [6, 8, 9, 7]이고, i는 6이다. 두 수를 바꿔주면 [6, 7, 9, 8]이 된다. 여기서 solution(l, 5, 5), solution(l, 7, 8)가 호출된다.

solution(l, 7, 8)에서 피봇값은 9이다. for 루프가 종료되었을 때 리스트는 똑같이 [9, 8]이고 i는 7이다. 두 수를 바꿔주면 [8, 9]가 된다. solution(l, 7, 6), solution(l, 8, 8)이 호출된다. 

상황을 정리해보면 l(5, 9)까지 [6, 7, 8, 9, 10]으로 잘 정렬되었다. 5는 최초 solution의 피봇값으로, 자기를 기준으로 왼쪽으로 작은 값, 오른쪽으로 큰 값들을 배치했으므로 정렬이 끝났다.

 

 

오름차순 정렬의 경우, 일단 피벗값을 임의로 정하고 피벗보다 작은 값은 왼쪽에, 피벗보다 큰 값은 오른쪽에 위치하도록 자리를 바꾼 뒤 또 작은 그룹과 큰 그룹끼리 나눠서 재귀 호출하는 방식으로 정렬한다. 일단 자기 왼쪽으로 작은 값들, 오른쪽으로 큰 값들이 위치하도록 자리를 바꾸는 것은 삽입 정렬과 비슷한 것도 같다. 

 

한편 퀵 정렬은 다르게 구현하는 방법도 있다. low와 high 인덱스를 정해 low를 오른쪽, high를 왼쪽으로 이동시키며 값들을 점검하다가 서로 교차되면 중지하고 피벗값과 high 값을 바꾸는 것이다. 퀵 정렬을 구현하는 방법은 여러 가지가 있는데 여기서는 위의 1가지만 살펴보기로 한다.

퀵 정렬의 시간 복잡도는 보통 O(nlogn)으로 설명할 수 있다. 하지만 최악의 경우에는 O(n^2)까지 시간복잡도가 나오기도 한다. 최악의 경우란 피봇값으로 정한 값이 중위값에서 한참 벗어난 극단적인 값(0, 10)일 때이다. 이 경우에는 리스트가 꼼짝도 않거나 계속 변경이 일어나기 때문에 비효율적이다. 그러나 현실적으로 대부분의 경우에는 O(nlogn)으로 마칠 수 있다고 한다. (좋은 피봇값을 정하는 알고리즘이 많이 연구됐다고 한다.)

 

 

6. 힙 정렬

힙 정렬(heap sort)은 힙의 루트에 가장 크거나 작은 값이 들어간다는 점을 이용해 정렬하는 알고리즘이다.

힙에서 루트가 아닌 다른 모든 노드는 부모 노드 값보다 작거나 큰 값을 갖는데, 이 점을 이용하면 pop을 했을 때 가장 작거나 큰 값이 나오므로 일단 힙에 다 집어넣고 순서대로 pop시켜서 리스트를 만들면 그게 바로 힙 정렬인 것이다.

import heapq

def heap_sort(lst):
  h = []
  for val in lst:
    heapq.heappush(h, val)
  return [heapq.heappop(h) for _ in range(len(h))]

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
new = heap_sort(d)
print(new)

heapq 모듈을 사용해 일단 lst의 모든 요소를 heappush로 h에 넣어버리고 반환할 때는 리스트 컴프리헨션으로 한 번에 반환한다. 시간복잡도는 O(nlogn)이다.

 

 

 

위 정렬 함수와 설명은 <모두의 알고리즘 with 파이썬> 정렬 파트 코드와 <파이썬 자료구조와 알고리즘>을 참고하여 공부한 내용을 토대로 작성한 것이다.

 

 

728x90
반응형
2 Comments
댓글쓰기 폼