[4.15] 문제 11. 퀵 정렬(ing)

2021.4.15

 

퀵 정렬

 

쉽게 설명한 퀵 정렬 알고리즘

 

def quick_sort(a):
  n = len(a)
  if n <= 1:
    return a
  pivot = a[-1]
  g1 = []
  g2 = []
  for i in range(0, n-1):
    if a[i] < pivot:
      g1.append(a[i])
    else:
      g2.append(a[i])
  return quick_sort(g1) + [pivot] + quick_sort(g2)

a = [3, 6, 9, 1, 2, 4, 5]
print(quick_sort(a))

 

퀵 정렬의 과정

 

#복습 중...
def quick_sort(a):
  #종료 조건
  n = len(a)
  if n <= 1:
    return a
  pivot = a[-1]
  #지금 a를 pivot을 기준으로 두 그룹으로 나눈다.
  g1 = []
  g2 = []
  for i in range(0, n-1):
    if a[i] < pivot:
      g1.append(a[i])
    else:
      g2.append(a[i])
  #재귀호출로 n = 1 일 때까지 g1, g2를 쪼개게 만든다. 
  #기준점 pivot을 리스트로 만들어 합친다. 
  return quick_sort(g1) + [pivot] + quick_sort(g2)

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

 

일반적인 퀵 정렬 알고리즘

 

def quick_sort_sub(a, start, end):
  if end - start <= 0:
    return
  pivot = a[end]
  i = start
  for j in range(start, end):
    if a[j] <= pivot:
      a[i], a[j] = a[j], a[i]
      i += 1
  a[i], a[end] = a[end], a[i]
  quick_sort_sub(a, start, i-1)
  quick_sort_sub(a, i+1, end)

def quick_sort(a):
  quick_sort_sub(a, 0, len(a)-1)

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

 

퀵 정렬의 과정

 

#복습 중...
#g1, g2 리스트 없이 a 안에서 정렬함. 
#이게 머지..
def quick_sort_sub(a, start, end):
  #종료 조건. 
  if end - start <= 0:
    return
  # [start, ... ,end]
  pivot = a[end]
  i = start
  # [start, ..., 여기까지, end]
  for j in range(start, end):
    if a[j] <= pivot:
      #a[j]값이 a[end]보다 작으면, 
      #왜 i랑 j위치 바꾸는 거지? 
      #1) j = i = start
      # 
      a[i], a[j] = a[j], a[i]
      i += 1
  a[i], a[end] = a[end], a[i]
  #재귀호출
  quick_sort_sub(a, start, i-1)
  quick_sort_sub(a, i+1, end)

def quick_sort(a):
  quick_sort_sub(a, 0, len(a)-1)

윽 어렵다

a = [3, 4, 5, 1, 2, 6] quick_sort(a)  종료 조건 : end <= start 재귀 1. quick_sort_sub(a, 0, 5)  a = [3, 4, 5, 1, 2, 6] pivot = a[5] = 6 i = start = 0 for j in range(0, 6):   (a[end]가 최댓값이라 변화 X)   i = 5, a = [3, 4, 5, 1, 2, 6] quick_sort_sub(a, 6, 5) -> 종료 재귀 2. quick_sort_sub(a, 0, 4) a = [3, 4, 5, 1, 2, 6] pivot = a[4] = 2 i = start = 0 for j in range(0, 4): -> 이걸 왜 하는거지? 뭔가 정렬되긴 하는데 이해가 안감. 흠.. j = 0 a[0] = 3 > pivot = 2 -> pass j = 1 a[1] = 4 > pivot = 2 -> pass j = 2 a[2] = 5 > pivot = 2 -> pass j = 3 a[3] = 1 < pivot = 2 a[0], a[3] = a[3], a[0] -> 특히 이거 1.  i += 1 -> 이거 2.  -> i = 1, a = [1, 3, 4, 5, 2, 6] a[1], a[4] = a[4], a[1] -> 이것도 3.  a = [1, 2, 4, 5, 3, 6] quick_sort_sub(a, 0, 0) -> 종료 재귀 3. quick_sort_sub(a, 2, 4) pivot = a[4] = 3 i = 2 = start for j in range(2, 4):  j = 2 a[j] = 4 > pivot = 3 -> pass j = 3 a[j] = 5 > pivot = 3 -> pass a[i], a[end] = a[end], a[i] a = [1, 2, 3, 5, 4, 6] quick_sort_sub(a, 2, 1) -> 종료 재귀 4. quick_sort_sub(a, 3, 4) pivot = a[4] = 4 i = start = 3 for j in range(3, 4): j = 3 a[j] = 5 > pivot -> pass a[3], a[4] = a[4], a[3] 하면 끝 a = [1, 2, 3, 4, 5, 6] 신기하군..

아! 퀵 정렬이구나! 

* 퀵 정렬 - pivot(여기선 end)을 정해, 왼쪽(g1)에는 작은 애들, 오른쪽(g2)에는 큰 애들 배치한다. 

 

출처 : ( [알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog (gmlwjd9405.github.io) )

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog (gmlwjd9405.github.io)