[정렬] Quick Sort - JS, Python

퀵 정렬 알고리즘

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터 위치 바꾸는 방법
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 됨
• 가장 기본적인 퀵정렬은 첫번째 데이터를 기준 데이터(pivot)으로 설정
• Divide and Conquer전략 사용

 

퀵정렬 ⓒssafy-story

1. pivot 데이터 설정 (맨 앞)

2. pivot의 다음 값을 left로, 배열 맨 끝을 right로 설정

3. left값이 pivot보다 크고 right값이 pivot보다 작을 때까지 동작 (left는 idx+1, right는 idx-1)

4. right의 idx가 left의 idx보다 클 경우 right값과 left값을 교환해줌

5. right의 idx가 left의 idx보다 작을 경우(교차 되는 경우) right값과 pivot값을 교환
   이때 pivot값을 기준으로 왼쪽은 pivot보다 작은 값 왼쪽은 pivot보다 큰 값으로 정렬된다 
   피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)라고 한다

6. 재귀를 이용해 pivot보다 작은수 모음, pivot보다 큰 수모음도 위와 같은 순서로 정렬 수행

 

BIG O

• 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있음
  • 너비 x 높이 = N x logN= NlogN

Worst : O(n^2) - 이미 정렬된 배열을 정렬하는 경우

Best : O(nlogn)

 

장점

매우 빠른 정렬 방법 

분할 정복의 좋은 예

 

단점

위 방법대로 정렬을 진행하게 되면 별도의 메모리 공간을 필요로 함(Unstable방식) => 공간적인 낭비 심해짐

stable한 방식도 나중에 정리해 보겠습니다

 

Python 코드

# 퀵 정렬

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return 
    
    pivot = start # 피벗은 첫번째 원소
    left = start + 1
    right = end
    while (left <= right):
        # 왼쪽은 피벗보다 큰 데이터 찾을 때까지 반복
        while (left <= end and array[left] <= array[pivot]):
            left += 1
        while (right > start and array[right] >= array[pivot]):
            right -= 1
        if (left > right): # 엇갈렸다면 작은 데이터와 피벗 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    # print('반복2', array, left, right)
    quick_sort(array, right + 1, end)
    # print('반복3', array, left, right)

quick_sort(array, 0, len(array)-1)
print(array)

혹시 코드가 복잡하다면 Python Tutor사이트를 이용해보세요 :-0

CF. Python을 이용한 간단 코드 구현

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만 담고 있다면 종료
    if len(array) <= 1:
        return array
    pivot = array[0] # 피벗은 첫번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분
    # print(left_side, pivot, right_side)

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

# [x for x] 테스트

# array = [1, 2, 3, 4, 5]
# a = [x for x in array if x <= 3]
# b = [x for x in  array if x > 3]

# print(a, b)

JS 코드

let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

const quickSort =  function(array, start, end) {
    // 원소가 1개일 경우
    if (start >= end){
        return 
    }

    let pivot = start // 맨 앞의 값을 pivot으로 설정
    let left = start + 1
    let right = end 

    while (left <= right) { // left가 right보다 작으면 종료
        // left가 end보다 크거나 array[left]값이 array[pivot]보다 크면 종료
        while (left <= end && array[left] <= array[pivot] ) {
            left += 1
        }
        // right가 start보다 작거나 같고 array[right]가 array[pivot]보다 작으면 종료 
        while (right > start && array[right] >= array[pivot]) {
            right -= 1
        }
        // 교차 됐으면 right와 pivot idx에 있는 값 교환
        if (left > right){
            let swap = array[pivot]
            array[pivot] = array[right]
            array[right] = swap
        } 
        // 교차 되지 않았으면 right와 left index값의 자리 바꿔줌
        else {
            let swap = array[left]
            array[left] = array[right]
            array[right] = swap
        }
    }
    quickSort(array, 0, right-1)
    quickSort(array, right+1, end)

    return array
}

const sorted = quickSort(array, 0, array.length - 1)
console.log(sorted)