2. 정렬 알고리즘(1)

2. 삽입정렬

삽입정렬은 적절한 위치에 삽입하는 방법으로 정렬한다. 버블정렬과 비슷하면서도 조금 다른데, 삽입정렬은 기준점을 주어서 그 값이 어디로 움직여야 하는지를 정하는것으로 이해하는 것이 편하다.

 

이렇게 나열된 숫자들이 있을때 순서대로 나열하려고 하면

이렇게 앞의 2를 1과 3 사이로 넣어주면 정렬이 끝난다. 이는 하나의 숫자를 모든 숫자들과 비교해서 적절한 위치에 배치하는 방법이다.

 

---

이전과 같이 C언어로  [1, 10, 5, 4, 3, 9, 6, 8, 7, 2] 을 삽입정렬을 통해 순서대로 배열하였다.

이 방법은 삽입정렬의 개념을 들었을때 스스로 작성해본 코드로 확실한지, 오류가 있을지는 확실하지 않다. 단지 위 배열을 정확하게 배열하고 개념에 맞는 프로그래밍을 했다고 생각해서 예시로 올린다. 

 

설명하자면, array[i]를 통해 한가지 숫자를 정한다. 이후 array[j]와 비교하여 array[i]가 더 크면 뒤로 옮겨준다. 

 

얼핏 보면 버블정렬과 별로 차이가 없어보이기도 한다. 그러나 만약 정렬해야 되는 숫자들이 이미 거의 정렬이 끝난 상태라면 말이 달라진다.

예를 들어 [1, 2, 3, 4, 5, 6, 7, 9, 8, 10] 이라는 숫자를 배열해야 한다면 삽입정렬은 어떤 정렬보다 빠른 속도를 보여줄 것이다.