[python] 퀵 정렬(Quick sort)

퀵 정렬

• 분할-정복법(divide and conquer)에 근거한다.
• 퀵정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬하는 전형적인 분할-정복법을 사용한다.
• 합병 정렬과의 다른 점은 리스트를 비균등하게 분할한다는 점이다.
• 리스트 안의 한 요소를 피벗(pivot)으로 선택하면 피벗보다 작은 요소들은 피벗의 왼쪽으로, 피벗보다 큰 요소들은 피벗의 오른쪽으로 옮겨진다.
• 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.
• 합병 정렬과 마찬가지로 부분 리스트에 대해 순환 호출된다.

 

퀵 정렬의 과정

• 피벗을 5로 설정한 후, 5보다 작은 값은 왼쪽 리스트에, 큰 값은 오른쪽 리스트로 보내는 탐색과 교환 과정을 반복한다.
• low와 high 포인터가 서로 엇갈리게 되면 멈춘 후 피벗을 중앙으로 이동시켜 피벗을 기준으로 2개의 리스트로 나뉘어진다.
• 각 왼쪽, 오른쪽 리스트 별로 위와 같은 과정(pivot 설정 후 탐색-교환 과정)을 반복한다.

 

 

전체 과정

 

코드 정리

# 퀵 정렬

def quick1(arr, start, end):
  if start >= end:
    return
  
  pivot = start
  left = start + 1
  right = end
  while (left <= right): #left와 right가 교차하기 전까지
    while(left <= end and arr[left] <= arr[pivot]):
      #pivot보다 큰 데이터를 찾을 때까지 반복
      left += 1
    while(right > start and arr[right] >= arr[pivot]):
      #pivot보다 작은 데이터를 찾을 때까지 반복
      right -= 1
    if(left > right):
      #left와 right가 교차되었다면 작은 데이터와 피벗을 교체
      arr[right], arr[pivot] = arr[pivot], arr[right]
    else: 
      #교차되지 않았다면 작은 데이터와 큰 데이터를 교체
      arr[left], arr[right] = arr[right], arr[left]
  
  #분할 이후 왼쪽 부분과 오른쪽 부분 각각 정렬 수행
  quick1(arr, start, right - 1)
  quick1(arr, right + 1, end)


# 1번보다 더 직관적
def quick2(arr):
  if len(arr) <= 1:
    return arr
  
  pivot = arr[0]
  tail = arr[1:] #pivot 제외한 리스트
  
  left_side = [x for x in tail if x <= pivot]
  right_side = [x for x in tail if x > pivot]
  
  return quick2(left_side) + [pivot] + quick2(right_side)

 

출처 : https://freedeveloper.tistory.com/377