노트

정렬 알고리즘

Sorting Algorithms

CS#algorithm · 연결된 개념 5개

쉽게 말하면

정렬 알고리즘은 뒤죽박죽 꽂힌 책을 번호순으로 다시 꽂는 여러 방법이에요. 이웃끼리 바꾸기, 가장 작은 걸 골라 앞으로 빼기, 한 권씩 알맞은 자리에 끼우기처럼 방법마다 잘 맞는 상황이 달라요.

비유가 깨지는 곳 책은 번호만 보면 되지만 JS의 기본 sort()는 숫자도 문자열로 비교해서 [10, 9, 1]이 [1, 10, 9]가 돼요. 숫자는 비교 함수를 넘겨야 하고, sort()는 원본을 바꿔요.

컬렉션의 원소를 어떤 순서(크기, 사전순, 날짜…)로 다시 배치하는 알고리즘. 같은 일을 하는 방법이 여럿이고 각자 강점이 달라, 트레이드오프를 익히기 좋은 주제다.

기본 세 가지 (평균 O(n²), 추가 공간 O(1))

  • 버블 정렬(Bubble Sort): 이웃한 둘을 비교해 큰 값을 뒤로 보낸다. 한 바퀴 동안 교환이 없으면 멈추게 하면 거의 정렬된 입력에서 빠르다
  • 선택 정렬(Selection Sort): 남은 것 중 최솟값을 찾아 앞으로 보낸다. 교환 횟수가 적다
  • 삽입 정렬(Insertion Sort): 앞쪽을 정렬된 상태로 유지하며 다음 원소를 알맞은 자리에 끼운다. 거의 정렬된 데이터와 작은 배열에 강해서, 실제 언어의 정렬 구현도 작은 구간에는 이것을 쓴다

더 빠른 정렬 (O(n log n))

  • 병합 정렬: 항상 O(n log n)이고 안정적이지만 추가 메모리가 든다
  • 퀵 정렬: 평균적으로 가장 빠른 편이지만 최악은 O(n²)
  • 비교 기반 정렬(Comparison Sort)은 최악·평균의 경우 O(n log n)보다 빠를 수 없다(거의 정렬된 입력처럼 유리한 경우는 예외)

기수 정렬

기수 정렬(Radix Sort)은 비교하지 않고 숫자의 자릿수별로 버킷에 나눴다 모으기를 반복한다. O(n·k)(k는 자릿수)로, 자릿수가 작은 정수 정렬에 빠르다.

JavaScript의 sort

[10, 9, 1].sort()는 [1, 10, 9]다. 기본이 문자열 비교이기 때문이다. 숫자는 비교 함수를 넘긴다: arr.sort((a, b) => a - b). 원본을 바꾸므로 복사본이 필요하면 toSorted()를 쓴다. 엔진의 sort는 안정 정렬(Stable Sort)이 보장된다(ES2019부터).

복잡도 비교는 빅오 표기법, 무작위로 섞는 반대 작업은 피셔-예이츠 셔플.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 우선순위 큐

    원소마다 우선순위가 있고, 들어온 순서와 상관없이 우선순위가 가장 높은 것부터 꺼내는 추상 자료형(Abstract Data Type, ADT). 같은 우선순위끼리의 순서는 보장하지 않는다. 응급실 대기 순서가 좋은 비유다.

  • 이진 탐색

    정렬된 배열에서 가운데 값과 찾는 값을 비교해 매번 절반을 버리며 찾는 방법. 원소가 100만 개여도 20번 남짓이면 끝난다(O(log n)). 처음부터 하나씩 확인하는 선형 탐색(Linear Search)은 O(n)이다.

  • 재귀

    함수가 자기 자신을 다시 호출해 문제를 푸는 방식. 같은 함수를 점점 작은 입력으로 부르다가 더 나눌 필요가 없는 지점(기저 조건, Base Case)에서 멈춘다.

  • 분할 정복

    문제를 같은 모양의 더 작은 문제로 나누고(분할, Divide), 각각을 풀고(정복, Conquer), 그 결과를 합쳐(결합, Combine) 원래 문제를 푸는 방식. 대개 재귀로 표현하고, 나눌 때마다 크기가 절반으로 줄면 log n 단계 만에 바닥에 닿는다.

  • 투 포인터

    배열이나 문자열에서 위치를 가리키는 포인터 두 개를 두고, 조건에 따라 움직여 가며 답을 찾는 패턴. 추가 메모리 없이(O(1) 공간) 중첩 반복을 한 번의 순회로 줄인다. 보통 정렬된 입력에서 쓴다.

보기 옵션