[알고리즘] 패스트캠퍼스 알고리즘 학습 - 퀵 정렬(Quick Sort)

목차

1. 퀵 정렬 (Quick Sort) 이란?

• 정렬 알고리즘의 꽃
• 기준점(pivot이라 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽, 크면 오른쪽으로 모으는 함수를 작성한다.
• 왼쪽과 오른쪽은 재귀 용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다.
• 함수는 왼쪽 + pivot + 오른쪽 을 출력한다.
• 분할 정복에 속하는 정렬이라고 할 수 있다.

 

---

2. 퀵 정렬 코드 작성

소스코드

data_list = [49, 97, 53, 5, 33, 65, 62, 51]

def quick_sort(num_list):
    if len(num_list) <= 1:
        return num_list

    pivot = num_list[0]
    left, right = [], []

    for i in range(1, len(num_list)):
        if num_list[i] < pivot:
            left.append(num_list[i])
        else:
            right.append(num_list[i])

    return quick_sort(left) + [pivot] + quick_sort(right)

quick_sort(data_list)

>>> [5, 33, 49, 51, 53, 62, 65, 97]

 

알고리즘 구현 및 풀이

• quicksort 함수 만들기
  • 만약 리스트 개수가 한 개이면 해당 리스트 리턴
  • 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 놓기
  • left, right 리스트 변수를 만들고,
  • 맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교(pivot)
    • 기준점보다 작으면 left.append(해당 데이터)
    • 기준점보다 크면 right.append(해당 데이터)
  • return quicksort(left) + pivot + quicksort(right)로 재귀 호출

리스트로 만들어서 리턴하기: return quick_sort(left) + [pivot] + quick_sort(right)

랜덤 테스트

랜덤한 값을 넣어 test 해보면 정렬이 잘 되는 것을 확인할 수 있다.

import random

data_list = random.sample(range(100), 10)

quick_sort(data_list)

>>> [4, 31, 35, 51, 56, 60, 69, 73, 80, 81]

List Comprehension 코드 작성

def quick_sort_comp(num_list):
    if len(num_list) <= 1:
        return num_list

    pivot = num_list[0]
    left = [val for val in num_list[1:] if val < pivot]
    right = [val for val in num_list[1:] if val >= pivot]

    return quick_sort_comp(left) + [pivot] + quick_sort_comp(right)

quick_sort_comp(data_list)

파이썬의 list comprehension을 잘 활용하면, 더욱 간결하고 보기 좋은 소스코드를 작성할 수 있다.

---

[알고리즘] 패스트캠퍼스 알고리즘 학습 - 동적 계획법과 분할 정복 with 피보나치

[알고리즘] 패스트캠퍼스 알고리즘 학습 - 선택 정렬(Selection Sort)

[알고리즘] 패스트캠퍼스 알고리즘 학습 - 버블 정렬

[알고리즘] 패스트캠퍼스 알고리즘 학습 - 삽입 정렬(Insertion Sort)