1. Iterative sort 개요

• Array, 혹은 List의 순서를 알 수 있는 데이터를 특정 순서대로 위치를 바꾸는 알고리즘들은 많다.

• 각각의 특징으론 시간복잡도, stability, adaptivity, 메모리 사용도를 들 수 있다.

• 주어진 array의 중복 값을 원래 순서대로 정렬한다면 stable하다고하며, 이를 반드시 지키지 않는 경우 unstable하다고 평가한다.

• 주어진 array에 이미 순서대로 정렬되어 있는 값을 인지하여 이용한다면, adaptive하다고 평가한다. 이런 경우, 알고리즘이 좀 더 일찍 끝날 수 있다. 만약 adaptive하지 않다면, 항상 모든 값에 대해 정렬을 실행한다.

• 알고리즘을 실행 중에 주어진 array가 점유하는 것 이상으로 메모리를 사용하지 않는다면, in-place하다고 평가한다. 만약, 다른 메모리를 필요로한다면 out-of-place하다고 평가한다.

• 우선, 단순 반복 비교를 이용한 가장 단순한 형태의 정렬 알고리즘들을 먼저 다룰 것이다.

2. Bubble sort

• 정렬 알고리즘 가운데 가장 단순한 알고리즘으로, 첫번째 index부터 마지막 index에 이르기까지 값을 차례대로 비교하여 정렬하는 알고리즘이다. Pseudo code는 다음과 같다.

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

• Stable하고, adaptive하면서 in-place 알고리즘이지만, 시간복잡도가 평균 O(n^2)이다. 물론 단순 반복 비교를 통한 알고리즘 대부분이 시간복잡도는 공유한다.

3. Insertion sort

• Array의 두번째 값부터 시작하여, 그 이전의 값과 차례대로 비교하여 정렬하는 알고리즘이다. 예를 들어, 2번째 값이 1번째보다 작다면 바꾼다. 그 다음, 3번째 값과 2번째 값을 비교하고, 그 이후 1번째 값과 다시 비교하여 정렬한다.

insertionSort(array):
	for n = 1 ~ array.length - 1
    	innerloop = 1
        while i != 0 && array[i] < array[i-1]:
        	swap value
            decrement i
    	

• Bubble sort와 마찬가지로 stable, adaptive, inplace하면서 O(n^2)의 시간복잡도를 가진다.

4. Selection sort

• 주어진 array를 탐색하며 가장 큰 값을 찾은 후, 최후미와 바꾼다. 이후 array의 최후미를 제외하고 탐색하며 가장 큰 값을 찾은 후, 다시 탐색 범위의 마지막에 위치시킨다.

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 알고리즘들이 존재한다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xII+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.