알고리즘 삽입정렬(Insertion sort) 그림으로 쉽게 이해하기

알고리즘 삽입정렬(Insertion sort) 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 알고리즘 정렬 중에서

삽입정렬(Insertion sort)에 대한 포스팅을 진행하겠습니다.

정말 어렵지 않으니 잘 따라와주세요.

 

 

지난 포스팅에서 다룬 버블정렬(Bubble sort)는

굉장히 직관적이고 단순해서 이해하기는 쉽지만 느리기 때문에

실제로 사용하기에는 어렵다는 단점이 있다고 했습니다.

 

 자료구조 - 버블정렬(Bubble sort)이란? (ft. 그림으로 쉽게 설명)

자료구조 - 버블정렬(Bubble sort)이란? (ft. 그림으로 쉽게 설명)

그래서 사람들이 다른 정렬 방식을 생각하고 만들어냈습니다. 

 

어떤 정렬 방식이 있을까요?

 

이번 포스팅에서는 삽입 정렬(Insertion sort)에 대해서 알아보겠습니다.

 

 

삽입정렬(Insertion sort)이란?

삽입 정렬의 알고리즘은

리스트의 앞에서 부터 이미 정렬된 서브 리스트의 값 비교를 통해서 자신의 위치에 값을 삽입하는 방식으로 진행이 됩니다.

이때 서브리스트는 이미 정렬이 되어 있다고 했으니까

서브 리스트 안에서도 자신이 삽입되어야 할 위치가 정해져 있겠죠.
그래서 그 위치에 자신을 삽입을 하게 되는 것입니다.
그런데 우리는 정렬되어 있지 않은 리스트를 정렬하려고 하는건데,

이미 정렬된 서브리스트는 도대체 어디서 나오는 것인지부터 생각을 해봐야겠죠.

 

사이즈가 1인 배열의 모습

 

만약에 사이즈가 1인 배열이 있다면 이 배열에는 어떤 값이 들어있어도 정렬된 상태라고 볼 수 있을 것입니다.
배열이 1칸이라면 그 안에 5든 1이든 100이든 어떤 값이 들어있든 이 리스트는 정렬이 되어 있는 상태인거죠.
그래서 삽입 정렬은 여기에서 출발하게 됩니다.

 

리스트의 가장 앞에 있는 하난의 원소를 서브리스트로 본다

 

리스트에서 가장 앞에 있는 하나의 원소를 이미 정렬된 서브리스트로 보고 정렬을 시작하게 됩니다.

그렇기 때문에 실질적인 정렬 로직은 리스트의 두 번째, 인덱스로는 1번째가 되겠죠.
이 위치에 있는 값부터 정렬을 시작하게 됩니다.

 

0번째 인덱스에 숫자 4가 삽입 된 모습

이미 정렬되어 있는 서브 리스트 내에서 값 비교를 통해서 자신이 삽입되어야 할 위치,

여기서는 0번째 인덱스의 숫자 4가 삽입된 모습이죠.
4는 5보다 작기 때문에 5의 앞에 삽입 된거라고 볼 수 있습니다.

그러면은 이제 사이즈가 2인 정렬된 서브리스트가 생기게 되는거죠.
그렇다면 이제는 2번 인덱스에 위치한 세번째 값 1을 정렬할 차례입니다.

 

2번재 인덱스까지 정렬된 모습

1을 앞에 정렬된 서브리스트 내의 원소들과 값을 비교해서 위치를 찾아보면

1의 위치는 서브리스트에 가장 앞이 되겠죠.
이제 정렬된 서브리스트의 크기는 총 3개가 되었습니다.

그다음 값은 9의 위치를 찾을 차례에요.
마찬가지로 서브리스트들과 값 비교를 했을 때 9의 위치를 탐색해보면 

9는 현재 위치에 그대로 있게 됩니다.
그래서 총 4칸의 정렬된 서브리스트를 얻게 되었습니다.

 

3번째 인덱스까지 정렬된 모습

 

이런식으로 리스트의 끝까지 순환하면서 자신의 위치를 찾아가게 되고 리스트 전체를 순환하게 되면 

모든 원소들이 정렬된 제자리를 찾아가게 되는게 삽입 정렬의 기본 매커니즘 입니다.

 

 

 

- 삽입정렬의 특징

그래서 삽입정렬의 특징을 보자면 우선 안정정렬입니다.
알고리즘 또한 bubble sort와 마찬가지로 굉장히 단순하다는 특징이 있습니다.

대신 삽입정렬은 데이터의 이동이 많다는 단점이 있습니다.
하지만 삽입정렬의 알고리즘 특성상 리스트 내의 데이터가 어느 정도 정렬이 되어있는 상태일 경우 

데이터의 이동이 적어진다는 특징도 함께 가지고 있습니다.

 

 

- 삽입정렬의 시간복잡도

그래서 평균적으로 삽입정렬의 시간복잡도는 O(N제곱)입니다.
하지만 데이터가 모두 정렬되어 있는 리스트에서 삽입 정렬을 수행하게 되면 

데이터를 이동시키는 로직을 실행하지 않기 때문에 시간복잡도는 O(N)까지 줄어들게 되고 (최선의 경우)
최악의 경우 데이터가 모두 역으로 정렬되어 있는 상태에서 삽입정렬을 실행하게 되면

모든 데이터의 순서마다 데이터의 이동이 이루어지면서 시간복잡도는 O(N제곱)이 됩니다.

 

여기까지 삽입정렬에 대한 포스팅을 마치겠습니다.

삽입정렬 알고리즘 관련해서 백준사이트에서 문제를 많이 풀어보면

여러분에게 도움이 조금 더 많이 될 것 같습니다.

감사합니다.

 

로스윗의 코딩캠프는

미래의 개발자 여러분을 응원합니다.

모두 화이팅!!

 

알고리즘 이진탐색(Binary Search) 그림으로 쉽게 이해하기

자료구조 이진탐색(Binary Search) 그림으로 쉽게 이해하기

 

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)