한 번에 하나씩 확인하기
선형 검색: 하나씩 확인하기
10장의 카드가 1부터 10까지 번호가 매겨져 있고 뒤집혀 있으며 무작위 순서로 섞여 있다고 상상해봅시다.
7번 카드를 찾고 싶습니다.
왼쪽에서 오른쪽으로 카드를 하나씩 뒤집어서 찾을 때까지 진행합니다.
| 시나리오 | 필요한 뒤집기 |
|---|---|
| 최고의 경우 | 1번 뒤집기 (운 좋게 첫 번째!) |
| 최악의 경우 | 10번 뒤집기 (마지막 카드였다면) |
| 평균 | 약 5번 뒤집기 |
이제 100장의 카드가 있다고 생각해봅시다. 평균: 약 50번 뒤집기.
1,000장의 카드? 평균: 약 500번 뒤집기.
패턴이 보이나요? 카드가 두 배 많으면 작업도 두 배가 됩니다. 작업량은 직선 형태로 증가합니다.
컴퓨터 과학자들은 이것을 선형 검색이라고 부릅니다 — 선형이란 작업이 직선처럼 증가한다는 뜻입니다: 꾸준하고 예측 가능하게.
선형 검색은 정렬된 목록이든 아니든 모든 목록에 적용됩니다. 그래서 간단합니다. 하지만 느릴 수 있습니다.
몇 개의 이름?
수업의 명단에 20개의 이름이 무작위 순서로 적혀 있습니다.
Zoe라는 이름을 찾아야 합니다.
목록 맨 위에서 아래로 한 번에 하나씩 이름을 확인합니다.
목록을 반으로 자르기
이진 검색: 중간으로 건너뛰기
이진 검색에는 한 가지 규칙이 있습니다: 목록을 먼저 정렬해야 합니다.
20개의 이름 목록이 A부터 Z까지 순서대로 되어 있다면 이진 검색을 사용할 수 있습니다.
작동 방식: 중간 이름(10번 이름)을 엽니다. 물어봅니다: Zoe가 이 이름보다 앞인가요 아니면 뒤인가요?
Z는 알파벳 끝 근처에 있으므로 Zoe는 중간보다 뒤에 있습니다. 첫 번째 절반을 버립니다. 이제 11~20번 이름만 남았습니다.
그 10개 이름의 중간(15번 이름)을 확인합니다. Z는 M보다 뒤에 있으므로 Zoe는 15번 이름보다 뒤에 있습니다. 11~14번 이름을 버립니다. 이제 16~20번 이름만 있습니다.
반으로 자르기를 계속합니다. 각 확인마다 남은 이름의 절반을 제거합니다.
| 목록 크기 | 이진 검색의 최대 확인 횟수 |
|---|---|
| 20개 이름 | 최대 5번 확인 |
| 1,000개 이름 | 최대 10번 확인 |
| 1,000,000개 이름 | 최대 20번 확인 |
이것을 선형 검색과 비교하면 1,000,000개 이름에서: 평균 500,000번 확인.
이진 검색은 매번 목록을 반으로 자릅니다. 반복적으로 반으로 자르면 1에 매우 빨리 도달합니다 — 이것이 이진 검색이 매우 빠른 이유입니다.
정렬된 목록에서 'fig' 찾기
정렬된 8개 단어의 목록이 있습니다:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
이진 검색을 사용하여 fig를 찾고 싶습니다.
기억하세요: 중간을 확인하고, 목표가 앞인지 뒤인지 물어본 다음, 목록을 반으로 자릅니다.
이웃하는 항목들을 순서대로 교환하기
버블 정렬: 이웃하는 항목 비교 & 교환
버블 정렬은 한 번에 두 개의 이웃하는 항목을 비교하여 목록을 순서대로 정렬합니다.
두 이웃하는 항목의 순서가 잘못되었으면 교환합니다.
아무것도 교환할 필요가 없을 때까지 목록을 계속 패스합니다.
예제: [5, 3, 8, 1] 정렬
패스 1:
- 5와 3을 비교합니다. 5 > 3이므로 교환 → [3, 5, 8, 1]
- 5와 8을 비교합니다. 5 < 8이므로 교환 안 함 → [3, 5, 8, 1]
- 8과 1을 비교합니다. 8 > 1이므로 교환 → [3, 5, 1, 8]
패스 2:
- 3과 5를 비교합니다. 괜찮습니다 → [3, 5, 1, 8]
- 5와 1을 비교합니다. 5 > 1이므로 교환 → [3, 1, 5, 8]
- 5와 8을 비교합니다. 괜찮습니다 → [3, 1, 5, 8]
패스 3:
- 3과 1을 비교합니다. 3 > 1이므로 교환 → [1, 3, 5, 8]
- 3과 5를 비교합니다. 괜찮습니다. 5와 8을 비교합니다. 괜찮습니다.
완료! [1, 3, 5, 8] ✓
주목하세요: 가장 큰 숫자가 각 패스마다 목록 끝으로 버블링됩니다. 이것이 버블 정렬이라는 이름의 유래입니다.
버블 정렬은 작동합니다. 큰 목록에서는 가장 빠르지는 않지만 이해하기 쉽습니다 — 배우기에 완벽합니다.
버블 정렬로 [4, 2, 7, 1] 정렬하기
버블 정렬을 사용하여 이 목록을 정렬하세요: [4, 2, 7, 1]
각 패스 후의 목록을 보여주세요. 완료하는 데 몇 패스가 걸리는지 세어주세요.