다섯 살도 알 수 있게 · 시스템SW
정렬 알고리즘이 뭐예요?
정렬 알고리즘을, 정비공장 손님 차들을 크기 순서로 줄 세우는 여러 방법 이야기로 풀어봤어요.
차 크기 순서로 줄을 세워야 해요.뒤죽박죽이라 어디부터 손대야 할지 모르겠어요.
아무렇게나 바꾸면 끝이 없어요.정해진 규칙 없이는 언제 끝날지 알 수 없어요.
정렬 알고리즘은 비교·교환 규칙을 정해두는 것이에요.규칙대로만 하면 저절로 순서가 맞아져요.
거품정렬옆 차끼리 비교해 큰 차를 뒤로
선택정렬제일 작은 차를 찾아 앞에 두기
삽입정렬새 차를 맞는 자리에 끼워넣기
병합/퀵정렬둘로 나눠 따로 정리하기
차가 많아질수록 방법 간 속도 차이가 커져요.차가 많을 땐 둘로 쪼개서 푸는 방법이 대부분 더 빨라요.
차가 적을 땐 간단한 방법이 나눠 풀기보다 오히려 빨라요.언제나 제일 빠른 정렬은 없어요, 상황에 맞게 골라요.
한 줄로
정렬 알고리즘은 자동차들을 비교하고 자리를 바꾸는 규칙을 정해 크기 순서로 줄 세우는 여러 방법이에요.
정렬 알고리즘은 데이터를 특정 순서로 재배열하는 절차예요. 거품·선택·삽입정렬은 구현이 쉽지만 데이터가 n개일 때 대략 n² 번 비교하고, 병합·퀵정렬은 '분할정복'으로 문제를 작게 나눠 풀어 대략 n log n 번만 비교해요(퀵정렬은 평균 기준). 데이터가 적으면 오버헤드가 적은 단순 정렬이, 많으면 분할정복 정렬이 유리해요.
어른들은 이렇게 불러요
- 거품정렬(버블정렬)
Bubble Sort - 이웃 차끼리 비교해 큰 차를 뒤로 보내기. 구현이 가장 쉽지만 차가 많으면 느려요.
- 선택정렬
Selection Sort - 가장 작은 차를 찾아 맨 앞에 두기. 차 순서와 상관없이 비교 횟수가 항상 비슷해요.
- 삽입정렬
Insertion Sort - 새 차를 이미 선 줄의 맞는 자리에 끼우기. 거의 다 정렬된 데이터엔 아주 빨라요.
- 병합정렬
Merge Sort - 줄을 반으로 나눠 각각 세우고 합치기. 차 순서와 상관없이 항상 대략 n log n이에요.
- 퀵정렬
Quick Sort - 기준 차를 골라 작은 쪽/큰 쪽으로 나누기. 평균은 빠르지만 기준 차를 나쁘게 뽑으면 느려요.
- 시간복잡도
Time Complexity - 차가 늘어날 때 시간이 느는 정도. n² 과 n log n 의 차이가 핵심이에요.
- 안정 정렬
Stable Sort - 같은 크기 차의 원래 순서를 지켜주는 것. 병합정렬·삽입정렬이 안정 정렬이에요.
- 분할정복
Divide and Conquer - 문제를 작게 쪼개 따로 풀고 합치는 전략. 병합/퀵정렬이 이 전략을 써요.
다음 이야기
전원이 꺼져도 기억하는 부품 창고 →