선형 검색
- 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지 검사
이진 검색
- 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 고보다 작은 인덱스 또는 큰 인덱스로 이동을 반복
알고리즘 표기법
- Big O : 실행 시간의 상한
-
Big Ω : 실행 시간의 하한
- 상한이 낮은 알고리즘이 더 좋다.
버블 정렬
- 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬
의사코드
Repeat n-1 times
For i from 0 to n-2
If i'th and i+1'th elements out of order
Swap them
-
중첩 루프를 돌아야하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1, n-2번 반복되므로 (n-1)*(n-2) = n^2 -3n +2번의 교환이 필요하다.
- 상한 : O(n^2)
- 하한 : Ω(n^2)
버블 정렬 개선 - 안쪽 푸르에서 교환이 하나도 일어나지 않는 다면 정렬이 잘 되어 있는 상황, 따라서 바깥쪽 루프를 교환이 일어나지 않을때까지만 수행하도록
실행 시간의 하한 : Ω(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
- 상한 : O(n^2)
- 하한 : Ω(n^2)
정렬 알고리즘의 실행시간
실행시간의 상한
- O(n^2): 선택 정렬, 버블 정렬
- O(n log n)
- O(n): 선형 검색
- O(log n): 이진 검색
- O(1)
실행시간의 하한
- Ω(n^2): 선택 정렬, 버블 정렬
- Ω(n log n)
- Ω(n)
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
병합 정렬
- 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식
상한 : O(n log n) - 숫자를 나누는 데는 O(log n)의 시간이 들고, 다시 정렬ㄹ해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문이다. 하한 : Ω(n log n)
출처