정렬은 키와 맵 구조를 가졌을 때 안정성을 고려해야 합니다.
가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘 입니다. 가장 작은 원소를 맨 앞에 위치한 원소와 바꾸고, 맨 앞을 제외한 원소 중 가장 작은 원소를 두번째 원소와 바꾸는 식으로 정렬이 완료될때까지 반복합니다. 시간 복잡도는 O(n^2) 입니다.
버블 정렬은 이웃하는 두 원소를 비교하여 정렬하는 정렬 방법입니다.
가장 맨 앞의 두 원소부터 시작해서 마지막 원소까지 비교하는 과정을 패스라고 합니다.
첫 번째 패스에서는 (n-1)번의 비교가 수행되며, 패스가 끝나면 가장 마지막 원소는 정렬된 상태가 됩니다. 두 번째 패스에서는 (n-2)번(마지막 원소는 비교X)의 비교가 수행됩니다.
버블 정렬은 최악, 평균, 최상의 경우 모두 같은 O(n^2)의 시간 복잡도를 갖습니다.
[ 비교: 무조건 n(n-1)/2, 교환(파이썬): 최악일 때 n(n-1)/2, 최상일 때 0, 평균: n(n-1)/4 ]
삽입 정렬은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘 입니다. 프로그래밍 코드로 삽입을 구현하기 어렵기 때문에, 값을 교환하는 형식으로 구현 가능합니다. 키가 중복될 경우 순서가 유지되는 안정적인 정렬입니다.
먼저 세가지 모두 주어진 배열 안에서 교환을 통해 정렬이 수행되기 때문에 공간복잡도는 O(n)입니다. 버블정렬과 선택정렬은 최악, 최선, 평균 모두 O(n^2)의 시간복잡도를 가지고, 삽입정렬은 평균과 최악의 시간복잡도가 O(n^2), 최선의 경우는 O(n)의 시간복잡도를 가집니다.