💭 이분 탐색 / 이진 탐색 (Binary Search)
이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
이진 탐색의 단점이라고 하면은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 하지만 검색이 반복될 때마다 목표값을 찾을 확률을 두 배가 되므로 속도가 빠르다.
💡 이진탐색의 성능
이진 탐색은 한번 비교가 이루어질때마다, 범위가 1/2로 줄어든다. 데이터의 집합의 크기를 n으로 두고, 반복 횟수를 k로 둔다면 아래와 같은 수식이 만들어진다. 데이터 집합의 크기인 n을 2로 몇번을 나누어야 1이 되는지 말해주는 식, 예를 들면 데이터 집합의 크기가 1024라면 10번의 탐색으로 데이터를 찾아낼 수 있다. (1024는 2의 10이기 때문에)
➡ 수행해야 하는 일의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가 한다.
💡 선형탐색 vs 이진탐색
선형 탐색은 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행을 하고
이진 탐색은 정렬된 리스트에서 중간값이랑 비교해보고 반씩 제외하면서 탐색을 하는 알고리즘 이다.
➡ 배열의 길이가 증가할수록 선형 탐색과 이진 탐색의 속도 격차는 더더욱 벌어진다.
알고리즘 평가는 최악의 경우 (제일 긴 시간이 드는 경우)로 따지는데
선형 탐색의 최악의 경우는 n개 전체를 봐야하는 경우 O(n)
이진 탐색의 최악의 경우는 log2 n개를 봐야 하는 경우 O(lg n)
💭 선택 정렬
배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 방법이다. 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하는 정렬방법이다.
다른 정렬들과 다르게 매우 비효율적이다. 최선의 경우(이미 정렬되어 있는 경우)조차도 모두 비교하기 때문이다.
💭 퀵 정렬
기준(pivot)을 설정하여 큰 숫자와 작은 숫자를 교환하고 리스트를 분할 한다.
(1) 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
(2) pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.
- left는 오른쪽으로, right는 왼쪽으로 이동
- left는 pivot보다 큰 수를 만나거나 pivot을 만나면 멈추고,
- right는 pivot보다 작은 수를 만나거나 pivot을 만나면 멈춘다.
- left와 right가 멈췄을 때, left가 right보다 왼쪽에 있다면 left와 right 값을 교환해준다.
- 이후 left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동하고 이 과정을 left가 right 보다 오른쪽으로 올 때까지 반복한다.
- 6이 3보다 크므로 6에서 left가 멈춘다.
- right는 pivot을 만나서 멈춘다.
- 이 때 left가 right보다 왼쪽에 있으므로 left와 right 값을 교환한다.
- left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
- left 가 right 보다 오른쪽에 있으므로 종료한다
(3) pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
- 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다.
- 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다.
- right가 L보다 크다면 L부터 right까지 다시 위 과정을 재귀적으로 반복한다.
- left가 R보다 작다면 left부터 R까지 다시 위 과정을 재귀적으로 반복한다.
- 왼쪽 부분 배열 정렬 과정
- left는 2에서 멈춘다.
- right는 pivot에서 멈춘다.
- left가 right보다 왼쪽에 있으므로 둘을 교환한다.
- left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
- left가 right보다 오른쪽에 있으므로 종료한다.
- 이때 right가 L보다 크지 않으므로 왼쪽배열(L부터 right)은 다시 재귀적으로 정렬할 필요가 없다.
- left는 R보다 작으므로 left부터 R까지 다시 재귀적으로 정렬을 수행한다.
- 오른쪽 부분 배열 정렬 과정
- left는 6에서 멈춘다.
- right는 pivot에서 멈춘다.
- left가 right보다 왼쪽에 있으므로 둘을 교환한다.
- left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
- left가 right보다 오른쪽에 있으므로 종료한다.
- 이때 right가 L보다 크지 않으므로 왼쪽배열(L부터 right)은 다시 재귀적으로 정렬할 필요가 없다.
- left는 R보다 작으므로 left부터 R까지 다시 재귀적으로 정렬을 수행한다.
➡ 배열이 위와 같이 오름차순으로 정렬된다.
💡 퀵 정렬(quick sort)의 시간복잡도
➕ 각 정렬 알고리즘 별 시간 복잡도와 평균 정렬 속도
