모두를 위한 컴퓨터 과학 (CS50 2019) - 알고리즘
3) 선형 검색
선형 검색 : 원하는 자료를 찾을 때까지 처음부터 마지막 자료까지 차례대로 검색
- 반환 값의 관습적인 의미
| 0 | 성공 |
| 1 | 실패 |
💬 어떤 정적인 정보. 예를 들어 도서관 회원관리에 필요한 회원 정보. 이름, 회원번호가 들어가 있을 것이다.
4) 버블 정렬
버블 검색 : 정렬 알고리즘 중 하나. 두 개의 인접한 자료를 비교하면서 위치를 교환하는 방식의 정렬
💬 n값이 크거나 이미 정렬되어 있는 자료를 정렬할 때 비효율적이다. 반대로 n값이 작거나 정렬되지 않은 자료를 정렬할 때 효율적이다.
5) 선택 정렬
선택 정렬 : 자료들 중에서 가장 작은 자료를 찾아 첫번째 위치의 수와 교환해주는 정렬
💬 선택 정렬을 효율적으로 바꾸기 위한 방법은 생각이 나지 않는다.
댓글에 최솟값과 최댓값을 동시에 정렬하자고 하는데, 최고차항이 n^2가 되는 것은 똑같지 않은가?
6) 정렬 알고리즘의 실행시간
Comparison Sorting Visualization
www.cs.usfca.edu
버블 정렬의 최상의 경우의 의사 코드 ☞ 하한은 Ω(n)
Repeat until no swaps
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
선택 정렬의 의사 코드
For i from 0 to n–1
Find smallest item between i'th item and last item
Swap smallest item with i'th item
💬 선택 정렬은 교환이 일어나지 않을 때까지만 코드가 수행되도록 할 수가 없다.
정렬이 다 되어 있는 자료라고 하더라도 코드를 중단시킬 수가 없다. 그래서 버블 정렬처럼 시간을 단축시킬 수가 없다.
