퀵 정렬/ 병합정렬

https://roytravel.tistory.com/328

[자료구조] 기본 정렬 알고리즘 총 정리

아주 잘 설명되어있음

https://www.toptal.com/developers/sorting-algorithms

https://visualgo.net/en

visualising data structures and algorithms through animation - VisuAlgo

 

 

 

퀵 정렬 (Quick Sort)

퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다. 

퀵 정렬에는 피봇(Pivot)이라는 개념이 사용된다. 피봇은 한 마디로 정렬 될 기준 원소를 뜻한다. 피봇 선택 방법에 따라 퀵 정렬의 성능이 달라질 수 있다. 최적의 피봇 선택이 어려우므로 임의 선택을 해야 한다. 보통 배열의 첫 번째 값이나 중앙 값을 선택한다. 퀵 정렬의 동작방식은 다음과 같다. 가령 예를 들어 배열 [5, 6, 1, 4, 2, 3, 7]이 있고, 피봇을 임의로 4를 선택했다 가정하자. 이후 4를 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 보내 [1, 2, 3] < 4 < [5, 6, 7]를 생성한다. 다시 왼쪽에서부터 임의의 피봇 2를 설정하여 [1] < 2 < [3]을 생성하고 오른쪽에선 임의의 피봇 6를 설정하여 [5] < 6 < [7]로 나눈다. 만약 배열 길이가 1이 된다면 가장 정렬 완료된 것이므로 분할된 배열을 합쳐 줌으로써 정렬을 마친다. 이를 알고리즘으로 구현하면 다음 코드와 같다.

def quick_sort(array : list) -> list:
    """ Best: O(nlogn) Average: O(nlogn) Worst: O(n^2) | O(nlogn) """
    if len(array) <= 1:
        return array

    pivot = array[len(array) // 2]
    small, equal, big = [], [], []

    for num in array:
        if num < pivot:
            small.append(num)
        elif num > pivot:
            big.append(num)
        else:
            equal.append(num)

    return quick_sort(small) + equal + quick_sort(big)

 

 

 

병합 정렬 (Merge Sort)

병합 정렬은 분할정복과 재귀 알고리즘을 사용하는 정렬 알고리즘이다.

퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가진다. 하지만 차이점은 퀵 정렬이 피봇 선택 이후 피봇 기준으로 대소를 비교하는 반면, 병합 정렬은 배열을 원소가 하나만 남을 때 까지 계속 이분할 한 다음, 대소관계를 고려하여 다시 재배열 하며 원래 크기의 배열로 병합한다. 예를 들어 배열 [6, 5, 1, 4, 3, 2, 8, 7]이 있을 때, 첫 번째로 [6, 5, 1, 4]와 [3, 2, 8, 7]로 분리한다. 두 번째로 [6, 5], [1, 4], [3, 2], [8, 7]로 나눈다. 세 번째로 [6], [5], [1], [4], [3], [2], [8], [7]로 나눈다. 이렇게 모든 원소가 분리되면 대소 관계를 고려하여 병합 과정을 거친다. 첫 번째로 [5, 6], [1, 4], [2, 3], [7, 8]이 되며, 두 번째는 [1, 4, 5, 6], [2, 3, 7, 8]이 된다. 마지막으로 하나의 배열로 병합되면서 [1, 2, 3, 4, 5, 6, 7, 8]와 같이 정렬이 완료되면서 알고리즘이 종료된다. 이를 코드로 나타내면 아래 코드와 같다.

def merge_sort(array: list) -> list:
    """ Best: O(nlogn) Average: O(nlogn) Worst: O(nlogn) | O(n) """
    if len(array) < 2:
    	return array
        
    mid = len(array)//2
    
    low = merge_sort(array[:mid])
    high = merge_sort(array[mid:])
    
    merged_array = []
    l, h = 0, 0
    
    while l < len(low) and h < len(high):
    	if low[l] < high[h]:
        	merged_array.append(low[l])
        	l += 1
        else:
                merged_array.append(high[h])
        	h += 1
            
    merged_array += low[l:]
    merged_array += high[h:]
    
    return merged_array

 

 

// 지피티 햄

🧩 1️⃣ 정렬의 기본 개념

정렬은 크게 두 가지로 나눌 수 있어:

• 비교 정렬(Comparison Sort) → 원소들을 서로 비교해서 정렬
  (예: 버블, 선택, 삽입, 퀵, 병합 정렬 등)
• 비교하지 않는 정렬(Non-Comparison Sort) → 값의 크기를 직접 이용
  (예: 계수 정렬, 기수 정렬 등)

우리는 비교 정렬 중 대표적인 퀵정렬(Quick Sort), **병합정렬(Merge Sort)**을 볼 거야!

---

⚡ 2️⃣ 퀵정렬 (Quick Sort)

“분할 정복(Divide and Conquer)” 원리로 작동하는 아주 빠른 정렬 알고리즘이야.

🧠 작동 원리

1. 배열에서 기준점(pivot) 을 하나 고른다.
2. pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈다.
3. 왼쪽과 오른쪽 배열 각각을 다시 재귀적으로 정렬한다.
4. 다 합치면 끝!

---

💻 예시 코드 (JavaScript)

 

function quickSort(arr) { if (arr.length <= 1) return arr; // 원소가 1개 이하라면 정렬 완료 const pivot = arr[Math.floor(arr.length / 2)]; // 가운데 값을 pivot으로 선택 const left = arr.filter(x => x < pivot); const right = arr.filter(x => x > pivot); const equal = arr.filter(x => x === pivot); return [...quickSort(left), ...equal, ...quickSort(right)]; } console.log(quickSort([5, 2, 8, 1, 3])); // 결과: [1, 2, 3, 5, 8]

⚙️ 특징 요약

항목설명

평균 시간 복잡도	O(n log n)
최악의 경우	O(n²) (이미 정렬된 배열일 때)
공간 복잡도	O(log n)
특징	실제로 매우 빠르고 실무에서도 많이 사용됨

---

🧠 3️⃣ 병합정렬 (Merge Sort)

이름 그대로 “정렬된 것을 병합하며 정렬”하는 알고리즘이야.

작동 원리

1. 배열을 반으로 계속 쪼갠다.
2. 원소가 1개가 될 때까지 나눈다.
3. 두 개씩 묶으면서 정렬된 순서로 병합(merge) 한다.
4. 모두 합쳐질 때 완전히 정렬된 상태가 된다.

---

💻 예시 코드 (JavaScript)

 

function mergeSort(arr) { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right); } function merge(left, right) { const result = []; let i = 0, j = 0; while (i < left.length && j < right.length) { if (left[i] < right[j]) result.push(left[i++]); else result.push(right[j++]); } return result.concat(left.slice(i)).concat(right.slice(j)); } console.log(mergeSort([5, 2, 8, 1, 3])); // 결과: [1, 2, 3, 5, 8]

⚙️ 특징 요약

항목설명

시간 복잡도	항상 O(n log n)
공간 복잡도	O(n) (새 배열 생성 필요)
특징	안정 정렬(Stable sort), 일정한 성능 보장

---

🎯 4️⃣ 요약 비교

구분퀵정렬 (Quick Sort)병합정렬 (Merge Sort)

분할 기준	Pivot 기준으로 분할	반으로 나누기
평균 속도	빠름 (O(n log n))	안정적 (O(n log n))
최악 속도	느림 (O(n²))	일정 (O(n log n))
공간 효율	높음 (O(log n))	낮음 (O(n))
안정성	❌ 불안정	✅ 안정적

 

 

 

 

 

 

// 코파일럿 지피티5햄

한눈에 차이

퀵정렬: 기준점(피벗)을 하나 고르고, 그보다 작은 것/큰 것으로 좌우로 갈라서 정복한다. “정중앙에 깃발 꽂고 좌우로 정렬” 느낌.
병합정렬: 반씩 쪼개서 매우 작은 조각들(거의 정렬이 필요 없는 크기)로 만든 뒤, “이미 정렬된 두 묶음끼리” 합치며 키운다. “작게 쪼개고, 정렬된 더미를 섞어 키운다” 느낌.

퀵정렬(Quick Sort) 직관

비유: 기준 물건 하나(피벗)를 책상 가운데에 두고, 더 가벼운 건 왼쪽, 더 무거운 건 오른쪽으로 휙휙 던져 두 무더기로 나눕니다. 그런 다음 왼쪽 더미, 오른쪽 더미에 대해 같은 일을 반복합니다.
작은 예시: [4, 2, 7, 3]
피벗 4 선택
4보다 작은: [2, 3], 같은: [4], 큰: [7]
[2, 3]과 [7]에 대해 다시(여긴 이미 정렬)
합치면 [2, 3, 4, 7]
왜 빠른가? 평균적으로 한 번 나눌 때 절반씩 비슷하게 갈리면 “높이(log n)”만큼만 재귀가 필요해서 n log n처럼 끝납니다.
왜 느려질 수 있나? 이미 정렬된 배열에서 맨 끝을 피벗으로 고르면 한쪽으로만 갈라져 “높이(n)”가 되어 O(n^2)가 나옵니다.
특징 한 줄 요약: 평균 매우 빠르고 메모리 거의 안 씀(제자리), 하지만 “최악”이 있을 수 있고 안정 정렬이 아님(같은 값의 순서가 바뀔 수 있음).
병합정렬(Merge Sort) 직관

비유: 카드 더미를 반으로 쪼개고 또 반… 아주 작은 더미(1~2장)가 되면, “각 더미는 이미 정렬된 것처럼” 취급하고, 두 더미를 합칠 때 앞장끼리 비교해 작은 것부터 새로운 더미에 차곡차곡 쌓습니다. 이 “합치기(merge)”가 핵심입니다.
작은 예시: [4, 2, 7, 3]
반으로 쪼개기: [4, 2] | [7, 3]
각자 또 쪼개고 정렬: [4]|[2] → 합치면 [2, 4], [7]|[3] → [3, 7]
[2, 4]와 [3, 7]을 머지: 2,3,4,7 순으로 꺼내 [2, 3, 4, 7]
왜 항상 일정한가? “쪼개기(log n)” 단계가 고정이고, 각 단계에서 전체 n개를 한 번씩만 합쳐 보므로 매번 n log n이 안정적으로 나옵니다.
메모리가 필요한 이유: 합칠 때 임시 더미(배열)가 필요해서 대략 n만큼의 추가 공간을 씁니다.
특징 한 줄 요약: 항상 일관되게 빠르고(항상 O(n log n)), 안정 정렬(같은 값 순서 보존), 대신 추가 메모리를 쓴다.
언제 무엇을 쓰면 좋나

메모리가 빠듯하다: 퀵정렬(제자리)
같은 값의 원래 순서를 지켜야 한다: 병합정렬(안정)
최악 상황도 일정한 속도가 중요하다: 병합정렬
데이터가 이미 어느 정도 정렬되어 있음: Timsort(파이썬 기본) 같은 병합+삽입 하이브리드가 최강. 퀵정렬도 피벗 잘 고르면 좋음.
중복 값이 매우 많다: 3-way 퀵정렬(같은 값 묶어 처리)
초간단 요약

퀵정렬: 피벗 기준 “좌우 갈라치기” 반복. 평균 빠름, 메모리 적음, 하지만 최악 O(n^2), 불안정.
병합정렬: “반으로 쪼개고 정렬된 두 묶음 합치기”. 항상 O(n log n), 안정, 메모리 O(n) 필요.
원하면, 아주 작은 배열로 손으로 따라 해보는 연습 예시(스텝별 비교/이동)를 만들어 드릴게요.

 

 

 

 

정렬 개요

목적: 데이터를 지정 기준(예: 오름차순)으로 재배열.
비교 기반 정렬의 하한: 평균적으로 O(n log n)보다 빠를 수 없음.
중요한 속성
시간 복잡도: 최선/평균/최악
공간 복잡도: 추가 메모리 필요 여부
안정성(stability): 같은 키의 상대적 순서 보존 여부
제자리(in-place): 추가 메모리 거의 없음
퀵정렬 (Quick Sort)

아이디어: 분할 정복. 피벗을 기준으로 작은 값/큰 값으로 파티션을 나눈 뒤 재귀 정렬.
절차
피벗 선택
파티셔닝(피벗보다 작은 요소를 왼쪽, 큰 요소를 오른쪽으로)
왼쪽/오른쪽 부분배열에 대해 재귀
복잡도
평균: O(n log n)
최악: O(n^2) (나쁜 피벗 선택 시, 예: 이미 정렬된 배열에서 끝 요소를 피벗으로 계속 선택)
공간: O(log n) (재귀 스택), 일반적으로 제자리 정렬
속성
안정성: 불안정
장점: 평균적으로 매우 빠름, 캐시 친화적, 추가 메모리 거의 없음
단점: 최악 성능 가능, 안정 정렬이 아님
실전 팁
피벗 선택: 무작위 선택, 삼중 선택(median-of-three)로 최악 케이스 완화
작은 구간(예: 길이 ≤ 16)은 삽입정렬로 전환해 성능 개선
중복이 매우 많다면 3-way 파티셔닝(네덜란드 국기 문제) 사용
꼬리 재귀 제거로 스택 깊이 감소
병합정렬 (Merge Sort)

아이디어: 분할 정복. 배열을 반으로 나누어 각각 정렬 후 두 정렬된 리스트를 병합.
절차
배열을 절반으로 분할
각 절반을 재귀 정렬
두 정렬 리스트를 병합(merge)
복잡도
최선/평균/최악: 항상 O(n log n)
공간: O(n) 추가 배열 필요(배열 기반). 연결 리스트에선 O(1) 추가 공간으로도 가능
속성
안정성: 안정 정렬
장점: 성능 변동이 적고 예측 가능, 안정성 보장, 외부정렬(디스크/스트리밍)과 병렬화에 유리
단점: 추가 메모리 사용, 일반적으론 제자리 아님
변형
하향식(재귀) vs 상향식(반복, run 길이 1부터 2, 4, 8…)
실전: Timsort(파이썬, 자바 일부 구현) — 실데이터 패턴(부분 정렬)에 매우 강함
언제 무엇을 쓸까?

메모리 제약이 크다: 퀵정렬 선호(제자리)
안정성이 필요하다(같은 키의 상대 순서 유지): 병합정렬
최악 시간 보장이 중요하다(일관된 성능): 병합정렬
데이터가 대부분 이미 정렬/부분 정렬: Timsort 같은 하이브리드, 또는 퀵정렬+작은 구간 삽입정렬
중복 원소가 매우 많다: 3-way 퀵정렬
외부정렬(메모리에 다 안 담기는 대용량): 병합정렬 계열(멀티웨이 머지)
간단 의사코드

퀵정렬(두 포인터 파티션)

partition(A, lo, hi):
pivot = A[mid 혹은 무작위]
i = lo, j = hi
while i ≤ j:
while A[i] < pivot: i++
while A[j] > pivot: j--
if i ≤ j: swap(A[i], A[j]); i++; j--
return i, j // 혹은 경계 인덱스
quicksort(A, lo, hi):
if lo >= hi: return
i, j = partition(A, lo, hi)
quicksort(A, lo, j)
quicksort(A, i, hi)
병합정렬(하향식)

mergesort(A):
if len(A) ≤ 1: return A
mid = n/2
L = mergesort(A[:mid]); R = mergesort(A[mid:])
return merge(L, R)
merge(L, R):
결과 배열에 L[0], R[0] 중 더 작은 것부터 차례로 넣기
남은 요소 이어붙이기(이 과정이 안정성 보장)
요약

퀵정렬: 평균 빠르고 메모리 절약, 하지만 최악 O(n^2), 불안정.
병합정렬: 항상 O(n log n)과 안정성, 하지만 O(n) 추가 메모리.
요구사항(안정성/일관성/메모리/데이터 특징)에 따라 선택하면 됩니다.