[정렬 알고리즘] ▲ 예제3 - 퀵정렬(Quick Sort)(168p)

[이코테] 예제3 - 퀵정렬(Quick Sort)(168p)

(한줄평) 예제 문제지만 quick sort가 익숙치 않아 복습이 꼭 필요!!!

풀이2는 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드다. 전통 퀵 정렬의 분할 방식과는 조금 다른데, pivot과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간면에서는 조금 비효율적이다. 하지만 더 직관적이고 기억하기 쉽다는 장점이 있다.

(풀이1) 일반적인 코드

풀이 시간: 30분 이내

1) 문제 해결 아이디어

<퀵 정렬>
Pivot(기준)을 설정하여 정렬을 수행한 후 Pivot을 기준으로 왼쪽 리스트, 오른쪽 리스트에서 각각 정렬을 수행(왼쪽: pivot보다 작은 수들, 오른쪽: pivot보다 큰 수들)

 

<동작 과정>

1. 리스트의 원소가 1개인 경우 종료

2. Pivot(기준)을 리스트 첫번째 데이터로 설정

3. 왼쪽에서부터 Pivot보다 큰수(array[left]), 오른쪽에서부터 Pivot보다작은수(array[right])를 찾음

4-1. 큰수 인덱스(left)가 작은수 인덱스(right)보다 크다면 엇갈린 것이므로,

작은수(array[right])와 기준(array[pivot])의 위치를 서로 바꿈

4-2. 큰수 인덱스(left)가 작은수 인덱스(right)보다 작거나 같다면,

큰수(array[left])와 작은수(array[right])의 위치를 서로 바꿈

5. 큰수 인덱스(left)와 작은수 인덱스(right)가 엇갈리지 않을 때까지, 3 ~ 4 반복

6. 분할 이후 왼쪽, 오른쪽 부분에 대해 각각 정렬 수행(재귀 호출)

재귀 호출할 때 매개변수 값을 올바른 값으로 잘 넘겨주어야 한다!!

 

2) 소스코드

# 퀵 정렬(Quick Sort)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 오름차순 정렬
def quickSort(array, start, end):
  if start >= end:  # 원소가 1개가 되면 종료
    return
  pivot = start  # pivot은 첫 번째 원소   
  left = start + 1
  right = end
  
  while left <= right:
    # pivot보다 큰 값을 찾을 때까지 반복
    while left <= end and array[left] <= array[pivot]:
      left += 1  # 오른쪽으로 한칸 이동
    # pivot보다 작은 값을 찾을 때까지 반복
    while right > start and array[right] >= array[pivot]:
      right -= 1  # 왼쪽으로 한칸 이동
    # 왼쪽값과 오른쪽 값이 엇갈리면
    if left > right:
      # 작은 데이터(오른쪽 값)과 pivot을 서로 변경
      array[pivot], array[right] = array[right], array[pivot]
    # 왼쪽값과 오른쪽 값이 엇갈리지 않았으면
    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)

(풀이2) 리스트 컴프리헨션(list comprehension)을 사용한 코드

풀이 시간: 20분 이내

1) 문제 해결 아이디어

재귀 호출이 아직도 익숙하지 않아서 처음부터 직접짜라고 했으면 어려움을 많이 겪었을 것 같다.

주석한 부분을 해제하면 왼쪽 부분, 오른쪽 부분이 어떤식으로 분할되는지 차례대로 출력되어 확인이 가능하다.

 

<동작 과정>

1. 리스트 원소가 1개 이하면 리스트(array) 리턴

2. pivot을 첫번째 원소로 설정, pivot을 제외한 정렬을 수행할 리스트(tail) 생성

3. 왼쪽 부분(left_side)에 pivot보다 작거나 같은 값 넣기

4. 오른쪽 부분(right_side)에 pivot보다 큰 값 넣기

5. 분할 이후 왼쪽, 오른쪽 부분을 각각 정렬 수행 한 전체 리스트 리턴

 

2) 소스코드

# 퀵 정렬(Quick Sort)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 오름차순 정렬
def quickSort(array):
  # 리스트 원소가 1개이하면 종료
  if len(array) <= 1:  
    return array
  
  pivot = array[0]  # pivot은 첫번째 원소로 설정
  tail = array[1:]  # pivot을 제외한 리스트

  left_side = [x for x in tail if x <= pivot]  # 분할된 왼쪽 부분(pivot보다 작거나 같은 값)
  right_side = [x for x in tail if x > pivot]  # 분할된 오른쪽 부분(pivot보다 큰 값)

  #print(left_side, right_side)
  # 분할 이후 왼쪽, 오른쪽 부분 각각 정렬 수행 후 전체 리스트 반환
  return quickSort(left_side) + [pivot] + quickSort(right_side)

print(quickSort(array))