정렬 알고리즘은 결국 "두 값을 비교하고, 필요하면 자리를 바꾸는 일"을 어떤 순서로 하느냐의 차이입니다. 같은 막대를 네 가지 방법으로 정렬하면서 비교 횟수가 얼마나 달라지는지 보세요.
막대 그래프로 정렬 과정을 보여 주고 알고리즘별 비교 횟수를 비교하는 시뮬레이터
1. 정렬 방법을 고르세요
2. 정렬을 실행하세요
비교0교환·쓰기0
비교 중자리 바꿈퀵 정렬 기준값제자리 확정
같은 배열에서 방법별 비교 횟수
[정렬 시작]을 누르면 자동으로 진행하고, [한 단계]를 누르면 비교나 교환 한 번씩 진행합니다. [새로 섞기]를 누르면 네 방법 모두 새 배열로 다시 비교합니다.
네 가지 방법
버블 정렬은 이웃한 두 값을 비교해 큰 값을 오른쪽으로 보내는 일을 반복합니다. 한 바퀴 돌 때마다 가장 큰 값이 맨 끝에 자리 잡습니다. 비교 횟수가 n²에 비례해서 늘어납니다.
삽입 정렬은 왼쪽부터 정렬된 구간을 넓혀 가며, 새 값을 왼쪽으로 옮겨 알맞은 자리에 끼웁니다. 거의 정렬된 배열에서는 매우 빠르지만, 최악의 경우는 버블 정렬과 같습니다.
퀵 정렬은 기준값 하나를 골라 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 뒤 양쪽을 다시 같은 방법으로 정렬합니다. 평균 n log n번 비교하지만, 기준값이 계속 한쪽 끝으로 치우치면 n²까지 느려집니다.
병합 정렬은 배열을 반으로 계속 쪼갠 뒤, 정렬된 두 조각을 앞에서부터 비교하며 합칩니다. 항상 n log n번 정도 비교하지만, 합치는 동안 쓸 임시 공간이 필요합니다.