정렬 알고리즘 ② - 퀵 정렬

퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort) 은 분할 정복(Divide and Conquer) 방식을 사용하는 정렬 알고리즘이다.

여기서 기준이 되는 값(pivot)을 정한 뒤 그 값을 기준으로 작은 값과 큰 값을 나누어 정렬한다.

 

이 때, Pivot이 어떤 값인지에 따라 정렬 성능이 달라질 수 있다.

동작 방식

1️⃣ Pivot 선택하기

먼저 기준이 될 값(pivot) 을 하나 선택한다. pivot은 상황에 따라 다르게 정할 수 있는데, 

보통

• 첫 번째 값
• 마지막 값
• 랜덤 값
• 중앙값

을 사용한다.

---

2️⃣ Pivot 기준으로 값 나누기 

이제 pivot을 기준으로 배열을 나눈다.

• pivot보다 작은 값 → 왼쪽
• pivot보다 큰 값 → 오른쪽으로 이동하게 된다.

예를 들어

[7, 5, 2, 4, 8, 1, 3]

pivot = 4 

분할 후 
→ 3, 1, 2 |  4 |  8,  5,  7

 

작은 값 | pivot | 큰 값 형태로 나뉘게 된다.

 

다만, 이 단계에서 완전히 정렬되는 것은 아니며 이후 다시 재귀적으로 정렬이 진행된다.

---

3️⃣ 같은 과정 반복하기 (재귀 호출)

pivot 기준으로 나뉜 왼쪽 부분 배열과 오른쪽 부분 배열에도 똑같은 과정을 반복한다.

 

---

4️⃣ 종료

더 이상 나눌 수 없을 때 정렬은 끝난다. 배열의 크기가1개, 즉 원소가 하나만 남은 배열은 이미 정렬된 상태이기 때문이다.

 

 

아래의 과정을 보면서 퀵 정렬이 어떤 방식으로 작동하는 지 보자. 

💻 구현

def quick_sort(arr,left,right):
  pL= left
  pR= right
  pivot= arr[(pL+ pR) //2 ] # 중간값을 pivot으로

  while pL <= pR: # pL과 pR이 cross되는 지점이 되기 전까지 반복 -> cross되는 순간 pivot 기준으로 왼쪽 / 오른쪽으로 나눔 

    while arr[pL] <pivot: # arr[pL]이 pivot값보다 작을 때까지 pL 포인터를 한칸씩 오른쪽으로 
      pL+=1

    while arr[pR] > pivot: # 오른쪽에 저장된 값이 더 크면 통과
      pR-=1 

    # pL과 pR이 멈췄을 때 
    if pL <= pR: # pL이 pR보다 작거나 같을때, 
      arr[pL],arr[pR] = arr[pR],arr[pL] # 문제가 발생한 두 지점의 값을 swap 

     # 값 교환 후 pL과 pR 이동 시킴 
      pL+=1  # pL 포인터 오른쪽으로 한칸 이동
      pR-=1 # pR 포인터 왼쪽으로 한칸 이동 

  #  ㄴ> 이 작업을 또 나누어 각자 또 실행해야 함 (원소가 하나씩으로 나누어질때 까지) 

  # 재귀 호출해줘야 함 
  # 원소가 하나 남았을 때 그룹을 오,왼 그룹으로 나누어서 비교해야 함 
  # 한 번 나눠지면 left ~ pR | pL ~ right
  # 원소가 한개 남았을 때 : left = pR , right= pL 

  if left < pR:
    quick_sort(arr,left,pR) 

  if pL < right :
    quick_sort(arr,pL,right)

  return arr




unsorted_arr=[70,6,28,26,60,56,24]
print(quick_sort(unsorted_arr,0,len(unsorted_arr)-1))

실행 결과