[알고리즘] 선형 시간 선택 알고리즘
10개의 원소를 갖는 아래와 같은 배열이 있다. 이 배열에서 i번째의 값을 찾는다고 해보자. arr[10] = { 10, 2, 5, 7, 6, 4, 8, 1, 9, 3 } 우선 배열을 한 번씩은 다 훑어봐야 하므로 적어도 n에 비례하는 시간이, 즉 \(\Omega(n)\)이 될것이다. 정렬을 한다면 \(O(nlogn)\)일 것이다. 어떤 시간에서든 선형 시간에 가능하도록 보장해줄 수 있도록 하는 알고리즘이 없을까? 이를 가능하도록 하는 알고리즘이 바로 선형 시간 선택 알고리즘이다. 평균 선형 시간 선택 알고리즘 선택 알고리즘은 퀵 정렬에서 사용했던 분할 알고리즘을 사용한다. 위의 경우에서 분할 알고리즘을 사용한다면 i번째 값을 찾을 수 있다. 기준원소를 5로 하고, 3번째로 작은 원소를 찾는다고 해보자...
[알고리즘] 정렬(1) - 선택 정렬, 버블 정렬, 삽입 정렬
정렬은 정해진 순서대로 나열하는 것이다. 학교에 처음 갔을 때 키 순서대로 자리를 배치하는 것이 좋은 예이다. 컴퓨터에서 정렬 알고리즘은 시간 복잡도가 Θ(\(n^2\))인 것 부터, Θ(\(nlogn\)), Θ(\(n\))등 여러가지 알고리즘이 있다. 각각의 알고리즘들을 알아보면서 직접 구현하는 시간을 가져보겠다. 모든 예시코드에는 공통적으로 아래의 배열을 예시로 정렬 알고리즘을 구현할 것이다. const int SIZE = 10; int arr[SIZE] = { 6, 2, 9, 7, 3, 10, 4, 1, 8, 5 }; 선택 정렬(Selection Sort) 가장 큰 원소를 찾은 후, 맨 뒷자리에 있는 원소와 자리를 바꾸는 정렬 알고리즘이다. 가장 큰 원소의 이동이 끝나면, 다음으로 큰 원소를 마지막..