Sort(2)
알고리즘 문제를 풀 때 사용하는 내장 sort 함수의 시간 복잡도는 O(NlogN)이다.
어떤 것이 있고, 어떻게 응용되어 사용되는지 알아보자.
O(NlogN)인 정렬
병합 정렬
분할 정복을 이용한 정렬 방법으로 원소가 1개 또는 0개 남을 때까지 둘로 쪼갠 다음
선택 정렬
모든 데이터를 쭉 돌면서 가장 작은 값을 선택해서 그걸 1번째에 넣고, 다시 2번째부터 끝까지 돌면서 가장 작은 값을 찾고..
를 반복한다. 역시 n(n-1)/2번 정도의 연산을 하게 된다.
조금 더 개선을 시켜보면 일단 모든 데이터를 돌며 최솟값을 찾는 것이기에, 이 때 최솟값과 최댓값을 둘 다 찾은 다음
최솟값은 맨 앞으로, 최댓값은 맨 끝으로 보내면 연산 횟수를 반으로 줄일 수는 있다.