한 번에 한 번씩 확인
선형 검색: 하나씩 확인
10장의 카드가.face-down로 섞인 무작위 순서로 놓여 있다고 상상해보세요. 번호 1부터 10까지 적혀 있습니다.
7이라는 번호가 적힌 카드를 찾고 싶습니다.
왼쪽에서 오른쪽으로 카드를 한 번 한 번씩 뒤집어 놓은 카드를 확인하다가 찾을 때까지 합니다.
| 상황 | 뒤집는 횟수 |
|----------|-------------|
| 최고 사례 | 1 번 뒤집기(운이 좋게 첫 번째 시도 성공!) |
| 최악의 사례 | 10 번 뒤집기(마지막 카드에 있었습니다) |
| 평균 | 약 5 번 뒤집기 |
100장의 카드라고 가정하면 평균적으로 약 50 번 뒤집기가 필요합니다.
1000장의 카드라고 가정하면 평균적으로 약 500 번 뒤집기가 필요합니다.
패턴을 보세요? 카드를 두 배로 늘리면 작업량도 두 배로 늘어납니다. 작업량은 직선으로 증가합니다.
컴퓨터 과학자들은 이 선형 검색이라고 합니다. 직선이란 것이 작업량이 직선처럼 일정하게 증가한다는 것을 의미합니다.
선형 검색은 정렬된 목록이나 무작위 목록 모두에 적용할 수 있습니다. 이것이 선형 검색이 간단한 이유입니다. 그러나 시간이 오래 걸릴 수 있습니다.
이름의 개수?
20개의 이름이 적힌 클래스 목록이 있습니다.
찾아야 할 이름은 Zoe입니다.
이름을 한 번 한 번씩 확인하며 목록의 상단에서 하단으로 내려가며 확인합니다.
반으로 나누기
이진 검색: 중간으로 건너뛰기
이진 검색의 규칙은 하나만 있다: 리스트를 먼저 정렬해야 한다.
20개의 이름 목록이 A에서 Z로 갈 때, 이진 검색을 사용할 수 있다.
작동 방식: 중간 이름으로 열려있는 상태(이름 #10). '조이(Zoe)는 이 이름의 앞이나 뒤에 있습니까?'라고 물어본다.
Z는 알파벳의 끝쪽에 있다, 그래서 조이는 중간보다 뒤에 있다. 첫 번째 반은 버리고 이제 11-20번 이름만 남았다.
남은 10개의 이름 중간을 확인(이름 #15). Z는 M보다 뒤에 있다, 그래서 조이는 이름 #15보다 뒤에 있다. 11-14번 이름을 버리고 이제 16-20번 이름만 남았다.
반으로 계속 나누다. 각 확인은 남은 이름의 절반을 제거한다.
| 리스트 크기 | 이진 검색으로 최대 확인 횟수 |
|-----------|-------------------------------|
| 20명의 이름 | 최대 5번 확인 |
| 1,000명의 이름 | 최대 10번 확인 |
| 1,000,000명의 이름 | 최대 20번 확인 |
선형 검색으로 1,000,000명의 이름을 평균 500,000번 확인한다.
이진 검색은 반씩 나누어 반복한다. 반으로 나누어지는 것이 매우 빠르게 1에 도달하는 것이 그 이유이다.
정렬된 리스트에서 'fig' 찾기
여기 정렬된 8개의 단어가 있는 리스트이다:
1. 사과 2. 바나나 3. 체리 4. 복숭아 5. 엘더베리 6. 포도 7. 감 8. 허니듀
이진 검색을 사용하여 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]
각 패스마다 목록을 보여주고, 정렬을 완료하기 위해 필요한 패스 수를 세세요.