삽입정렬을 시작하기 전에 얼마나 다양한 정렬 방법과 각 정렬방법의 장단점을 알고 싶으면 아래 사이트를 확인해보자. 시각적으로 표현되어 흐름을 이해하기 쉽다.
https://www.toptal.com/developers/sorting-algorithms
삽입 정렬(Insertion Sort)
삽입정렬은 한 번에 하나의 항목을 올바른 위치에 삽입해서 배열의 정렬된 부분을 점진적으로 구축하는 방식이라 생각하면 된다.
처음에 5를 정렬된 배열이라 생각하고 3을 비교해 5앞에 위치시킨다.
이후 4를 비교하여 3과 5 사이에 삽입.
이런 방식으로 자기자신이 비교대상보다 작은지를 계속 비교하여 자기자리에 삽입하는 정렬방식이다.
아래는 실제 코드를 작성한 부분이다.
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let currentVal = arr[i]; // 정렬할 대상을 할당한다.
let j; // 반복문 외부에서 사용하기 위해 미리 선언한다.
for (j = i - 1; j >= 0 && currentVal < arr[j]; j--) {
// j는 정렬 대상 직전 값으로 시작한다.
// 0이상이고, 정렬대상이 비교대상보다 작을때 반복문이 실행한다.
arr[j + 1] = arr[j]; //
}
arr[j + 1] = currentVal;
}
return arr;
}
insertionSort([2, 1, 9, 76, 4]);
코드에 있는 배열에서 시작하게 됐을 때 순서도.
-
먼저 1을 2와 비교한다. => 정렬대상이 더 작아 반복문을 실행
-
2가 1에 자리에 들어오게 된다.
-
이제 j가 -1이기 때문에 반복문 종료 후 배열의 첫번째 자리에
currentVal을 할당한다. (현재 j가 -1이기 때문에 +1을 해줘야한다.) -
이후 위 내용을 반복한다.
위 출력에서 볼 수 있듯이 이미 정렬되어 있는 상태에서는 반복문을 실행하지 않기 때문에 매우 효율적인 방법이라 할 수 있다.
그러나 무작위인 배열일 경우 많은 시간을 들여야한다.
삽입정렬에서 최악의 경우는 반대로 정렬된 경우이다.
예) [4, 3, 2, 1] => 생각해보면 이유를 알 수 있다.
따라서 이미 정렬된 배열에 새로운 데이터를 집어 넣으려고 할 때
삽입정렬은 아주 좋은 방법이 된다. 정렬된 부분을 유지하기 때문.
여기서 삽입 정렬의 시간복잡도는 n²이다. 일단 이중 반복문을 실시하기 때문이다.
따라서 가능한 최고 경우는 이미 정렬된 배열은 O(n)이고 최악은 O(n²)이다.
다음은 버블, 선택, 삽입 정렬의 빅오 복잡도를 나타낸 표이다.
공간 복잡도는 새로운 변수를 거의 안쓰기 때문에 1이다
버블과 삽입 정렬의 경우 거의 정렬된 상태에서는 적은 교환으로 정렬이 가능하다.
그러나 선택정렬은 거의 정렬된 상태에서도 반복문을 통해 계속 작은 값을 비교하며 찾기 때문에 느리다. (이해하기 쉽다는 것은 장점이다.)
위 부분은 글 처음에 있는 정렬 시물레이션 사이트에서 확인할 수 있다.
위 정렬 방식들은 적은 데이터를 사용할 때에는 비교적 간단하게 구현할 수 있기 때문에 유용할 수 있다.
그러나 많은데이터를 정렬하고 싶을 때에는 그렇지 못하다.
그래서 이 방법들 말고도 더 좋은 방식들이 있다.
합병, 퀵, 기수 정렬 방식이다.
위 방법들은 순차적으로 알아보자.
