[퀵 정렬] Quick Sort - Python

퀵 정렬 Quick Sort

 

Quick Sort

퀵 정렬

• 시간복잡도는 Worst 경우 O(n^2), Average : O(nlogn), Best - O(nlogn)
• pivot을 어떻게 설정하느냐에 따라 성능이 달라질 수 있음
• 값들이 이미 정렬되어 있는 경우 Worst Case : Random하게 섞어주는 방식 사용 가능
• 퀵정렬 과정
  1. 리스트 개수가 1개일 때 재귀 종료
  2. 0번째 값을 pivot으로 설정
  3. pivot보다 작거나 큰 값을 low, high 리스트에 저장
  4. 저장한 low, high에 각각 재귀적으로 quick을 적용
  5. 최종 low, high, pivot을 병합

def quick(data):
  # 재귀 함수 종료 조건
  if len(data) < 2:
    return data

  result = []
  # pivot값 설정
  pivot = data[0]

  # pivot보다 작거나 큰 값 리스트
  low = []
  high = []

  # pivot보다 작으면 low, 크면 high에 저장
  for i in range(1, len(data)):
    if pivot > data[i]:
      low.append(data[i])
    else:
      high.append(data[i])

  # 결과값 low, high 리스트에 대해 각각 quick정렬
  low = quick(low)
  high = quick(high)

  # 정렬된 값들을 하나로 병합
  result += low
  result += [pivot]
  result += high

  return result

data = [7,5,3,1,4,2,6,8]
print(quick(data))

퀵 정렬 - Index를 사용해 추가 메모리를 사용하지 않고 정렬

def quick(data, left, right):
  # 재귀 함수 종료 조건
  if left >= right:
    return

  # pivot 설정
  pivot=data[left]

  l = left
  r = right
  # pivot보다 작은값과 큰값의 위치 변경
  while l <= r:
    while pivot > data[l]:
      l = l+1
    while pivot < data[r]:
      r = r-1

    # l이 r보다 작거나 같을 때에만 위치를 바꿔야함
    # l, r이 어긋난 경우에는 실시하지 않음
    if l <= r:
      print('현재 pivot값 = {0}, 데이터 = {1}'.format(pivot, data))
      data[l], data[r] = data[r], data[l]
      print('현재 pivot값 = {0}, 정렬후 = {1}\n'.format(pivot, data))
      l, r = l+1, r-1

  # pivot을 기준으로 quick 재귀호출
  quick(data, left, l-1)
  quick(data, l, right)

data = [7,5,3,1,4,2,6,8]
quick(data, 0, len(data)-1)
print(data)

 

 

퀵 정렬 다른 예시 - 지식 in

kin.naver.com/qna/detail.nhn?d1id=1&dirId=104&docId=376841051

퀵정렬 알고리즘 좀 풀어주세요

퀵 정렬의 핵심은 Pivot을 기준으로 왼쪽과 오른쪽으로 나뉜다는 것입니다.

1번의 수행을 거치면 Pivot 왼쪽에는 모두 작은값, Pivot 오른쪽에는 모두 큰 값이 세팅됩니다.

그리고 다시 왼쪽과 오른쪽 값들에 대해서 퀵정렬을 각각 수행합니다.

퀵정렬을 구현하는 방법에는 여러 가지가 있지만 보통 Pivot을 어떻게 설정하느냐의 차이입니다.

교재의 예시는 다음과 같습니다.

지식in 질문 - 퀵정렬 과정

1. 0번째값 Pivot 설정

2. 1번째값 l, 마지막 6번째값 r 설정

3. l값이 pivot보다 작으면 다음칸으로 이동, r값이 pivot보다 크면 다음칸으로 이동

4. l,r 이동이 멈춘 경우 두 위치 교환

5. 다시 3번 규칙에 의해 이동 후 l이 r을 만나면 pivot과 l이 이전에 가리키던 값의 위치 교환

6. pivot의 왼쪽, 오른쪽값들에 대해 1~5 과정을 수행합니다.

지식in - 퀵정렬 답변

 

참고한 사이트

www.daleseo.com/sort-quick/

[알고리즘] 퀵 정렬 - Quick Sort (Python, Java)

yabmoons.tistory.com/250

[ 정렬 ] 정렬별 장단점 및 시간복잡도

koreanfoodie.me/107

퀵 정렬(Quick sort) - 파이썬 코드 구현

https://koreanfoodie.me/107

퀵 정렬(Quick sort) - 파이썬 코드 구현