삽입정렬 알고리즘

삽입정렬 알고리즘(insertion sort)

삽입정렬 알고리즘은 데이터를 하나씩 확인하며 각, 데이터를 적절한 위치에 삽입하자는 아이디어에서 나온 정렬 알고리즘이다.

 

삽입정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 "삽입정렬"이라고 부른다.

 

삽입정렬은 특정한 데이터를 적절한 위치에 들어가지 이전에 그 전(앞)까지의 데이터는 이미 정렬되어 있다고 생각하고 정렬을 시작한다.

 

앞전에 정렬되어 있는 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다. 예를 들어 보자.

 

step 0

첫번 째 숫자 '7'은 정렬되어 있다고 생각하고 '5'부터 시작해보자.

숫자 '5'가 어디에 들어가면 좋을지 판단하면 결국, 그 앞전 숫자 '7'의 오른쪽인지 왼쪽인지만 생각하면 된다.

그럼으로 오름차순으로 정렬함으로 '5'를 '7'의 왼쪽에 삽입해야 한다.

7 5 9 0 3 1 6 2 4 8 --> 5 7 9 0 3 1 6 2 4 8

 

 

step 1

이어서 9차례다.

9는 이 전 '7', '5'를 훑어보고 적절한 위치가 어디인지 판단해야 한다. 하지만 '9'는 '7' 과 '5'보다 크므로 원래 위치를 유지한다.

 

step 2

이어서 '0'차례다.

'0'은 앞의 7, 5 ,9를 살펴보고 적절한 위치를 찾아본다. 0이 가장 작은 수 임으로 첫번째 즉, 5의 왼쪽에 들어간다.

 

5 7 9 0 3 1 6 2 4 8 --> 0 5 7 9 3 1 6 2 4 8

 

중간을 생략하고

 

step 7

결국 이런식으로 정렬을 하다보면 

0 1 2 3 5 6 7 9 4 8 --> 0 1 2 3 4 5 6 7 9 8

 

step 8

0 1 2 3 4 5 6 7 9 8 --> 0 1 2 3 4 5 6 7 8 9

가 될 것이다. 

 

 

파이썬으로 한번 코드를 살펴보자.

 

array = [7, 5, 9, 0, 3, 1 , 6, 2, 4, 8]

for i in range(1, len(array)):
  for j in range(i, 0, -1):#i 에서 시작해서 0 전까지 -1씩 뒤로나아간다.정리하면 지난간것을 싹 훑기
    if array[j] < array[j - 1]:
      array[j], array[j - 1] = array[j - 1], array[j]
    else :
      break;

print(array)