체육시간에 30명의 학생을 키 순서로 줄 세우는 건 금방 할 수 있습니다.
하지만 여름 해수욕장에 모인 1만 명을 이름순으로 정렬한다면? 단순한 방법으로는 하루 종일 걸릴 수도 있습니다!
그래서 데이터가 많을수록 더 빠른 정렬 알고리즘이 필요합니다.
| 알고리즘 | 방식 | 성능 |
|---|---|---|
| 선택 정렬 | 최솟값 찾아 앞으로 | O(n²) — 느림 |
| 삽입 정렬 | 알맞은 자리에 삽입 | O(n²) — 느림 |
| 알고리즘 | 방식 | 성능 |
|---|---|---|
| 버블 정렬 | 앞뒤 비교, 교환 | O(n²) |
| 퀵 정렬 | 기준으로 분할 정복 | O(n log n) — 빠름! |
Lining up 30 students by height in PE class is quick and easy.
But sorting 10,000 people at a summer beach by name? Simple methods could take all day!
That's why we need faster sorting algorithms as data grows.
| Algorithm | Method | Performance |
|---|---|---|
| Selection Sort | Find min, move to front | O(n²) — Slow |
| Insertion Sort | Insert at right position | O(n²) — Slow |
| Algorithm | Method | Performance |
|---|---|---|
| Bubble Sort | Compare neighbors, swap | O(n²) |
| Quick Sort | Divide & conquer by pivot | O(n log n) — Fast! |
버블 정렬(Bubble Sort)은 바로 옆에 있는 데이터끼리 비교해서, 큰 것을 뒤로 보내는 정렬입니다.
탄산음료 속 거품(Bubble)이 아래에서 위로 올라가는 모습을 상상해보세요.
버블 정렬도 마찬가지! 큰 값이 거품처럼 배열의 끝(위)으로 떠올라갑니다.
한 사이클이 끝나면 가장 큰 값이 맨 뒤에 확정됩니다.
Bubble Sort compares adjacent data and sends the larger one backward.
Imagine bubbles in a soda drink rising from bottom to top.
Bubble Sort works the same way! Large values "bubble up" to the end of the array.
After one cycle, the largest value is fixed at the end.
배열 [90, 50, 70, 20]을 오름차순으로 정렬해봅시다.
옆 사람과 키를 비교해서, 큰 사람이 뒤로 가는 방식입니다. 한 줄 끝까지 가면 가장 키 큰 사람이 맨 뒤에 서게 됩니다!
Let's sort [90, 50, 70, 20] in ascending order.
Compare heights with the person next to you — the taller one moves back. By the end, the tallest person stands at the very back!
After Cycle 1, the last position is fixed (90 is confirmed). So Cycle 2 only needs to sort the remaining 3 items [50, 70, 20].
가장 기본적인 버블 정렬 함수입니다. 키(신장) 데이터 8개를 정렬합니다.
range(n-1, 0, -1): end가 7→6→5→...→1 (범위가 점점 줄어듦)range(0, end): cur이 0부터 end 직전까지 (앞에서 뒤로 비교)The most basic bubble sort function. Sorts 8 height data items.
range(n-1, 0, -1): end goes 7→6→5→...→1 (range shrinks)range(0, end): cur from 0 to just before end만약 데이터가 [10, 20, 30, 40]처럼 이미 정렬되어 있다면?
기본 버블 정렬은 교환이 한 번도 없는데도 끝까지 비교를 반복합니다. 시간 낭비!
개선 아이디어: 한 사이클에서 교환이 한 번도 없으면 → 이미 정렬 완료 → 바로 종료!
What if data is already sorted like [10, 20, 30, 40]?
Basic Bubble Sort keeps comparing even when no swaps happen. Waste of time!
Improvement: If zero swaps in a cycle → already sorted → stop immediately!
changeYN = False at start of each cyclechangeYN = True whenever a swap occursbreak → Exit early!
총 비교 횟수 = n(n-1)/2
데이터가 2배 → 비교 횟수 4배 증가!
| 데이터 수 (n) | 비교 횟수 | 체감 시간 |
|---|---|---|
| 10개 | 45번 | 눈 깜짝할 사이 |
| 100개 | 4,950번 | 거의 즉시 |
| 1,000개 | 499,500번 | 조금 걸림 |
| 10,000개 | 49,995,000번 | 꽤 오래 걸림 |
| 100,000개 | ~50억 번 | 매우 오래! |
| 정렬 | 최선 | 평균 | 최악 | 특징 |
|---|---|---|---|---|
| 선택 정렬 | O(n²) | O(n²) | O(n²) | 항상 같음 |
| 삽입 정렬 | O(n) | O(n²) | O(n²) | 거의 정렬시 빠름 |
| 버블 정렬 | O(n) | O(n²) | O(n²) | 개선 시 빠름 |
Total comparisons = n(n-1)/2
Double the data → 4x more comparisons!
| Data Size (n) | Comparisons | Feel |
|---|---|---|
| 10 | 45 | Instant |
| 100 | 4,950 | Nearly instant |
| 1,000 | 499,500 | Slight delay |
| 10,000 | 49,995,000 | Noticeable |
| 100,000 | ~5 billion | Very slow! |
| Sort | Best | Average | Worst | Feature |
|---|---|---|---|---|
| Selection | O(n²) | O(n²) | O(n²) | Always same |
| Insertion | O(n) | O(n²) | O(n²) | Fast if sorted |
| Bubble | O(n) | O(n²) | O(n²) | Fast if improved |
Code12-01의 데이터 [188, 162, 168, 120, 50, 150, 177, 105]
Code12-01 data: [188, 162, 168, 120, 50, 150, 177, 105]
랜덤 데이터 10개를 버블 정렬하면서 비교한 총 횟수를 출력하세요.
힌트: 전역 변수 count를 만들고, 비교할 때마다 count += 1을 추가하세요. global count 잊지 마세요!
Code12-01을 수정하여 내림차순(큰 값 → 작은 값)으로 정렬하세요.
힌트: 비교 조건의 부등호 방향만 바꾸면 됩니다! >를 <로
Sort 10 random items with Bubble Sort and print the total comparison count.
Hint: Create a global variable count, add count += 1 at each comparison. Don't forget global count!
Modify Code12-01 to sort in descending order (large → small).
Hint: Just reverse the comparison operator! > to <
퀵 정렬(Quick Sort)은 기준값(Pivot)을 하나 정한 후, 그보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 나누어 각각 다시 정렬하는 방법입니다.
큰 피자를 한 번에 먹기 어렵죠? 반으로 나누고, 또 반으로 나누면 한 조각씩 쉽게 먹을 수 있습니다!
퀵 정렬도 마찬가지! 큰 문제를 "나누어 정복(Divide & Conquer)"합니다.
Quick Sort picks a pivot value, then divides data into "smaller than pivot" (left) and "larger than pivot" (right), sorting each group recursively.
A whole pizza is hard to eat at once. Cut it in half, then half again — now each slice is easy!
Quick Sort works the same: "Divide & Conquer" the big problem!
가족 8명을 키 순으로 정렬합니다: [188, 150, 168, 162, 105, 120, 177, 50]
아빠(188), 엄마(150), 누나(168), 할머니(162), 아기(105), 동생(120), 형(177), 해피🐕(50)
Sort 8 family members by height: [188, 150, 168, 162, 105, 120, 177, 50]
가장 이해하기 쉬운 퀵 정렬 구현입니다. 매번 새로운 왼쪽/오른쪽 배열을 만듭니다.
The easiest-to-understand Quick Sort. Creates new left/right arrays each time.
Code12-03의 문제: 기준값과 같은 값이 사라짐! → midAry를 추가하여 해결합니다.
[120, 120, 50, 50, 120, 50]에서 기준값=50이면?
Code12-03: 50과 같은 값들이 left에도 right에도 안 들어감 → 50이 하나만 남음!
해결: 같은 값을 모으는 midAry를 추가!
Code12-03 problem: values equal to pivot get lost! → Add midAry to fix this.
[120, 120, 50, 50, 120, 50] with pivot=50?
Code12-03: values equal to 50 go nowhere → only one 50 survives!
Fix: Add midAry to collect equal values!
midAry = [] for equal valueselse: midAry.append(num) — catches duplicates매번 새 배열(leftAry, rightAry)을 만드니까 메모리를 많이 사용합니다.
개선: 새 배열 없이 원래 배열 안에서 low와 high 포인터로 교환하며 정렬!
Creating new arrays (leftAry, rightAry) every time uses lots of memory.
Improvement: No new arrays — sort directly within the original array using low/high pointers!
[188, 150, 168, 162, 105, 120, 177, 50] — pivot = arr[3] = 162
[188, 150, 168, 162, 105, 120, 177, 50] — pivot = 162
사전에서 "Python"을 찾을 때, 첫 페이지부터 한 장씩 넘기나요?
아닙니다! 중간을 펴서 P보다 앞인지 뒤인지 판단하고, 반씩 좁혀가며 찾습니다.
퀵 정렬도 이처럼 반으로 나누니까 빠릅니다!
Do you flip from page 1? No! Open to the middle, check if "Python" is before or after, then halve the remaining pages.
Quick Sort divides in half too — that's why it's fast!
.sort() uses a variant of this!
| 구분 | Code12-03 간단 퀵 정렬 | Code12-04 중복 처리 | Code12-05 일반(In-place) |
|---|---|---|---|
| 방식 | 새 배열 생성 | 새 배열 생성 (+midAry) | 원본 배열에서 직접 교환 |
| 중복 값 | 처리 불가! | 처리 가능 | 처리 가능 |
| 메모리 | O(n) 추가 | O(n) 추가 | O(log n) |
| 이해도 | 매우 쉬움 | 쉬움 | 어려움 |
| 실무 사용 | 학습용 | 학습용 | 실무 표준 |
처음 배울 때: Code12-03으로 원리 이해하기
중복 데이터가 있을 때: Code12-04 사용
실제 프로그램: Code12-05 (In-place) 사용
가장 쉬운 방법: Python의 ary.sort() 또는 sorted(ary) — 내부에서 최적화된 정렬 자동 수행!
if n <= 1)이 반드시 있어야 무한 호출을 방지합니다.
| Feature | Code12-03 Simple | Code12-04 With Duplicates | Code12-05 In-place |
|---|---|---|---|
| Method | New arrays | New arrays (+midAry) | Swap within original array |
| Duplicates | Lost! | Safe | Safe |
| Memory | O(n) extra | O(n) extra | O(log n) |
| Difficulty | Very Easy | Easy | Hard |
| Production | Learning | Learning | Standard |
Learning: Code12-03 for understanding the principle
With duplicates: Code12-04
Real programs: Code12-05 (In-place)
Easiest: Python's ary.sort() or sorted(ary) — optimized sorting built in!
if n <= 1) to prevent infinite calls!
배열 [30, 80, 10, 60, 40, 20, 70, 50]을 Code12-03(간단 퀵 정렬)으로 정렬할 때, 각 재귀 단계에서 leftAry, pivot, rightAry를 적어보세요.
힌트: pivot = ary[n//2]. 첫 호출에서 pivot = ary[4] = 40
Code12-03을 수정하여 내림차순으로 정렬하세요.
힌트: 비교 조건의 <와 >를 바꾸면 됩니다!
Sort [30, 80, 10, 60, 40, 20, 70, 50] using Code12-03. Write out leftAry, pivot, rightAry at each recursion level.
Hint: pivot = ary[n//2]. First call: pivot = ary[4] = 40
Modify Code12-03 for descending order.
Hint: Swap the < and > comparison operators!
빨강, 초록, 파랑 물감을 섞으면 다양한 색이 만들어지듯, 컴퓨터도 Red, Green, Blue(RGB) 세 가지 빛을 섞어서 모든 색상을 표현합니다!
Just like mixing red, green, blue paints creates various colors, computers use Red, Green, Blue (RGB) light to represent all colors!
Uses tkinter to load and display a GIF image file in a window.
고정값 127 대신 실제 이미지의 밝기 중앙값(Median)을 기준으로 사용!
어두운 이미지 → 중앙값이 낮아짐 → 더 많은 디테일 보존
밝은 이미지 → 중앙값이 높아짐 → 자연스러운 흑백
Instead of fixed 127, use the actual median brightness of the image!
Dark image → lower median → preserves more detail
Bright image → higher median → natural B&W
같은 랜덤 데이터를 선택 정렬과 퀵 정렬로 각각 정렬하고 소요 시간을 측정합니다.
## 데이터 수: 1,000개 선택 정렬 → 0.020초 퀵 정렬 → 0.002초 (10배 빠름!)## 데이터 수: 15,000개 선택 정렬 → 4.500초 퀵 정렬 → 0.030초 (150배 빠름!)
Sort the same random data with Selection Sort and Quick Sort, measure time.
time.time() before and after each sort## Data: 1,000 items Selection → 0.020 sec Quick Sort → 0.002 sec (10x faster!)## Data: 15,000 items Selection → 4.500 sec Quick Sort → 0.030 sec (150x faster!)
100만 명이 키 순서로 줄 서 있는데, 한 사람이 임의의 위치에 끼어들었습니다.
다시 정렬해야 할 때, 버블 정렬 vs 퀵 정렬 중 뭐가 빠를까?
1 million people standing in height order. One person cuts in at a random position.
Which is faster to re-sort: Bubble Sort vs Quick Sort?
Bubble Sort → ~0.5 secQuick Sort → ~3.0 sec| 구분 | 선택 정렬 | 삽입 정렬 | 버블 정렬 | 퀵 정렬 |
|---|---|---|---|---|
| 장(Chapter) | 11장 | 11장 | 12장 | 12장 |
| 방식 | 최솟값 찾아 앞으로 | 알맞은 자리에 끼워넣기 | 옆끼리 비교 교환 | 기준으로 분할 정복 |
| 비유 | 눈으로 쭉 훑어 제일 작은 것 선택 | 카드를 받아 적절한 자리에 | 탄산의 거품 위로 떠오름 | 피자를 반으로 나누기 |
| 최선 | O(n²) | O(n) | O(n) | O(n log n) |
| 평균 | O(n²) | O(n²) | O(n²) | O(n log n) |
| 최악 | O(n²) | O(n²) | O(n²) | O(n²) |
| 추가 메모리 | O(1) | O(1) | O(1) | O(log n) |
| 안정성 | 불안정 | 안정 | 안정 | 불안정 |
데이터가 적을 때 (100개 이하): 아무거나 OK! 차이 없음
거의 정렬된 데이터: 삽입 정렬 또는 개선 버블 정렬
대용량 데이터: 퀵 정렬 (실무 표준)
가장 쉬운 방법: Python의 .sort() 또는 sorted()
| Feature | Selection | Insertion | Bubble | Quick |
|---|---|---|---|---|
| Chapter | 11 | 11 | 12 | 12 |
| Method | Find min, move front | Insert at right spot | Compare neighbors | Divide & Conquer |
| Best | O(n²) | O(n) | O(n) | O(n log n) |
| Average | O(n²) | O(n²) | O(n²) | O(n log n) |
| Worst | O(n²) | O(n²) | O(n²) | O(n²) |
| Stable | No | Yes | Yes | No |
Small data (≤100): Any sort is fine!
Nearly sorted: Insertion or improved Bubble
Large data: Quick Sort (industry standard)
Easiest: Python's .sort() or sorted()
랜덤 데이터 5,000개를 생성하여 선택 정렬과 퀵 정렬의 소요 시간을 비교하세요. time 모듈을 사용합니다.
힌트: time.time()으로 시작/끝 시간을 측정합니다. 같은 데이터를 사용하기 위해 tempAry[:]로 복사!
다음 상황에서 어떤 정렬을 사용하면 좋을지 골라보세요:
① 학생 30명의 시험 점수 정렬
② 인터넷 쇼핑몰의 상품 100만 개 가격 정렬
③ 이미 정렬된 전화번호부에 새 번호 1개 추가 후 재정렬
Generate 5,000 random items. Compare execution time of Selection Sort vs Quick Sort using the time module.
Hint: Use time.time() for start/end. Copy data with tempAry[:] for fair comparison!
Which sort is best for each scenario?
① Sort 30 students' exam scores
② Sort 1 million product prices
③ Re-sort a phone book after adding 1 entry