정렬별 시간복잡도를 생각해보자(Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort, Time Complexity)

Q. 정렬의 종류는 무엇이 있을까?

 

종류들을 나열하고, 간단하게 알고리즘에 대해서 설명하겠다. 오름 차순 정렬 기준으로 설명하겠다.

 

 

버블정렬 : 순차적으로 근접한 두 값을 비교하면서, 마지막에 거품(Bubble)처럼 하나의 값을 얻게 된다. 같은 과정으로 하나의 값들을 얻어보면 정렬할 수 있다.

 

 

선택정렬 : 선택정렬은 전체의 원소에서 가장 작은 값을 순차적으로 찾아가면서 정렬한다.

 

 

삽입정렬 : K번째 원소의 위치를 찾을 때, 1부터 K-1까지는 모두 정렬이 되어 있으므로, K -1번째부터 값을 비교하며 위치를 찾으면서 정렬한다.

 

 

퀵정렬 : 피벗을 선택하고, 피벗을 기준으로 왼쪽에는 피벗보다 작은 값이 오른쪽에는 피벗보다 큰 값이 오도록 한다. 재귀적으로 호출하며 모든 원소들을 정렬한다.

 

 

합병정렬 : 재귀적으로 반으로 나누고, 원소가 1개가 됐을때 다시 거꾸로 합병하기 시작하여 최종적으로 모든 원소들을 정렬한다.

 

 

힙정렬 : 힙 트리를 이용한 정렬이다, 부모 노드가 가장 작다는 것을 이용해서 값을 순차적으로 추출하여 정렬된 결과를 얻는다.

 

 

Q. 정렬의 시간복잡도에 대해서 알아볼까?

 

<출처> 구글 이미지 검색

 

직관적으로 이해가 되지 않는 부분의 시간 복잡도만 설명하도록 하자.

 

 

버블 소트의 베스트 케이스를 보자, O(N)이다. 

 

 

버블 소트는 매 라운드를 거치면서, 더 이상 정렬한 값이 없다면 마지막 라운드가 되고 값이 종료된다. 따라서, 첫번째 라운드에서 모든 값이 정렬되어 있다면, O(N)만에 정렬을 완성할 수 있다.

 

 

 

다음으론, 삽입 정렬의 베스트 케이스를 보자.

 

 

 

삽입 정렬은, K번째 원소가 1 ~ K - 1번째 원소 사이에 삽입하는 것을 의미한다. 1 ~ K - 1은 이미 정렬된 상태를 의미한다. 따라서, K - 1번째 원소와 K번째 원소를 비교했을 때, K번째 원소 값이 더 크다면 더 이상 탐색할 필요가 없다. 따라서 Best Case는 O(N)이 되는 것이다.

 

 

 

마지막으로, 퀵 소트의 워스트 케이스를 보자.

 

 

첫번째 요소를 피벗으로 선택했을때, 피벗의 위치에 따라서 값이 분할된다. 분할되는 정도가 고르지 못하고, 편향되게 분할되면 O(N^2)이 발생할 수 있다.