[알고리즘/Python] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort) 이란??

 

• 병합 정렬(Merge Sort)와 더불어 대표적인 분할 정복 알고리즘 중 하나이다.
• 리스트 값중 랜덤한 값을 pivot으로 설정한 뒤 pivot보다 작으면 왼쪽에, pivot보다 크면 오른쪽에 위치시킨다.
• pivot을 기준으로 나눠진 왼쪽과 오른쪽 리스트에 대해 또 다시 위의 과정을 재귀적으로 시행한다.
• 평균 시간복잡도는 O(n*log n), 최악의 시간복잡도는 O(n^2)이다.

 

 

def quick_sort(arr):
  #리스트가 하나 이하의 원소를 가지고 있다면 종료
  if len(arr)<=1:
    return arr
  pivot=arr[0]  #첫번째 원소를 피벗으로 설정

  #arr[1:] == 피벗을 제외한 리스트
  left_side=[x for x in arr[1:] if x<=pivot] #왼쪽부분
  right_side=[x for x in arr[1:] if x>pivot] #오른쪽 부분

  #왼쪽부분과 오른쪽부분에 대해 각각 재귀적으로 정렬을 수행하고 전체 리스트 반환
  return quick_sort(left_side)+[pivot]+quick_sort(right_side)

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

위의 코드처럼 파이썬의 리스트 슬라이싱 기법을 이용해서 아주 간단하게 구현할 수 있다.

 

하지만 재귀 호출을 할때마다 새로운 리스트를 생성하고 병합하기 때문에

메모리 소모량이 크고 병합에 필요한 연산이 요구된다.

한마디로 시간 복잡도와 공간 복잡도가 높다.

 

 

 

따라서 새로운 리스트를 생성하지 않는 코드를 작성해보자.

def quick_sort(arr,left,right):
  def partition(arr,left,right):
    pivot=left
    left+=1
    while(left<=right):
      while(left<=right and arr[left]<=arr[pivot]):
        left+=1
      while(left<=right and arr[pivot]<=arr[right]):
        right-=1
      if(left>right):
        arr[right],arr[pivot]=arr[pivot],arr[right]
      else:
        arr[left],arr[right]=arr[right],arr[left]
    return right
    
  if(left>=right):
    return
  p=partition(arr,left,right)
  quick_sort(arr,left,p-1)
  quick_sort(arr,p+1,right)
  

arr=[7,5,9,0,3,1,6,2,4,8]
quick_sort(arr,0,len(arr)-1)
print(arr)