소트(Sort)란
- 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 혹은 그 반대 순서로 재배열하는 것. (오름차순 정렬 / 내림차순 정렬)
아래에 제시한 소팅들의 정렬 과정은 모두 오름차순 기준입니다.
버블정렬(bubble sort) (O(n^2))
인접한 두 개의 원소를 비교해서 자리를 교환하는 방식. 한 단계가 끝나면, 가장 큰 원소 혹은 가장 작은 원소가 마지막 자리로 위치합니다.
아래 예시는 7 3 2 5 6 8 을 오름차순 정렬할 때 버블소트를 사용하는 과정입니다. (파란색 배경색은 비교를 진행한 두 원소, 파란색 글씨는 SWAP을 했다는 의미)
과정에서 볼 수 있듯이, 아주 단순한 대신 정렬이 되어 있어도 계속 인접한 두 개의 원소를 비교하게 되므로 최선, 평균, 최악의 경우 모두 시간복잡도는 O(n^2) 입니다.
교환(swap) 연산이 많이 일어나는 소팅입니다.
중복된 값이 있을 때, 정렬 과정을 거쳐도 그 순서가 유지되는 stable sort 입니다.
선택정렬(selection sort) (O(n^2))
- (1) 주어진 배열에서
최솟값을 찾는다. - (2) 그 최솟값을
맨 앞에 위치한 것과 바꾼다.(swap) - (3) 맨 앞의 것을 제외하고, 나머지 것들을 대상으로 다시 위 (1)~(2) 과정을 반복한다.
아래 예시는 2 2 1 7 3 을 선택정렬로 오름차순 정렬하는 과정입니다. (2는 2개가 있는데, 순서를 살펴보기 위해 아래첨자 1, 2로 표시해 두었습니다.)
선택정렬은 버블소트보다는 swap 횟수가 적지만 시간복잡도는 O(n^2) 입니다.
정렬 과정에서 같은 숫자 2의 순서가 바뀌었습니다. 따라서 unstable sort 입니다.
삽입정렬(insertion sort) (O(n^2))
선택한 요소의 앞부분을 보면서 들어갈 자리를 찾아가는 정렬방법입니다.
2번째 인덱스부터 시작해서 그 앞과 자신을 비교하고, 내가 더 크면 더 이상 비교하지 않고 다음 인덱스로 넘어갑니다.
만약 내가 더 작았다면 그 앞에 있던 원소를 한 칸 뒤로 밀고, 자신은 그보다 한칸 더 앞에 있던 원소와 비교를 진행합니다.
앞보다 내가 더 커서 더 이상 비교를 진행하지 않아도 되면, 비어 있는 칸에 자신을 위치시킵니다.
- 삽입정렬은 모두 정렬되어 있는 최선의 경우에는, 단 한 번씩만 비교를 하기 때문에 시간복잡도가 O(n)이 됩니다. 즉 어느 정도 정렬이 된 배열일수록 삽입정렬의 효율이 높아지게 됩니다.