정렬 알고리즘 #2 - 퀵 정렬(quick sort), 병합 정렬(merge sort), 이진탐색(binary search)
1. 퀵 정렬(quick sort) 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. - 시간 복잡성 best-case : O(n lg n) [lg(n)은 log₂(n)의 줄인 표현] average-case : O(n lg n) worst-case: O(n²) - Java 코드 2. 병합 정렬(merge sort) 분할 정복 알고리즘의 하나로, 나뉘어지지 않을 때까지 리스트를 분할한 뒤 하위 리스트를 정렬한 후 각가을 하나로 합친다. - 시작 복잡성 best-case : O(n lg n) [lg(n)은 log₂(n)의 줄인 표현] average-case : O(n lg n) worst-case: O( n lg n ) - Java 코드 3. 이진 탐색(binary search) 리스트가 정렬되어 있지 않으면 검색 시 주어진 값에 맞는 원소를 찾기 위해 리스트를 모두 찾아봐야 한다. 하지만 정렬된 리스트가 있거나 검색하기 전에 정렬을 수행한 상황이라면 리스트에서 값을 찾을 때 이진 검색을 사용하는 것이 매우 효율적인 방법이다. 43억개의 원소가 있는 리스트에서 특정 값을 찾아낼 때 최악의 탐색 깊이는 32회이다. - 시간 복잡성 best-case : O(lg n) [lg(n)은 log₂(n)의 줄인 표현] average-case : O(lg n) worst-case : O(lg n) - Java 코드
