Array, 혹은 List의 순서를 알 수 있는 데이터를 특정 순서대로 위치를 바꾸는 알고리즘들은 많다.
각각의 특징으론 시간복잡도, stability, adaptivity, 메모리 사용도를 들 수 있다.
주어진 array의 중복 값을 원래 순서대로 정렬한다면 stable하다고하며, 이를 반드시 지키지 않는 경우 unstable하다고 평가한다.
주어진 array에 이미 순서대로 정렬되어 있는 값을 인지하여 이용한다면, adaptive하다고 평가한다. 이런 경우, 알고리즘이 좀 더 일찍 끝날 수 있다. 만약 adaptive하지 않다면, 항상 모든 값에 대해 정렬을 실행한다.
알고리즘을 실행 중에 주어진 array가 점유하는 것 이상으로 메모리를 사용하지 않는다면, in-place하다고 평가한다. 만약, 다른 메모리를 필요로한다면 out-of-place하다고 평가한다.
우선, 단순 반복 비교를 이용한 가장 단순한 형태의 정렬 알고리즘들을 먼저 다룰 것이다.
bubbleSort(array):
stopIndex = array.length - 1
whild stopIndex not zero
inner index = 0
while inner index < stopIndex
if array[inner] > array(inner + 1)
swap value
increment inner
decrement stopIndex
insertionSort(array):
for n = 1 ~ array.length - 1
innerloop = 1
while i != 0 && array[i] < array[i-1]:
swap value
decrement i
selectionSort(array):
for array.length-1 ~ 1:
maxvalueindex = 0
for 0 ~ n
if array[i] > array[maxvalueindex]
maxvalueindex = i
swapvalue n and maxvalueindex
오직 in-place일 뿐, unstable, not adaptive하며 시간복잡도 또한 O(n^2)이다. 대신, 값의 교체가 가장 적게이루어진다는 특징이 있다.
이외에도 cocktail shaker sort 등 다른 형태의 iterative sort 알고리즘들이 존재한다.
이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.