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