삽입 정렬

삽입 정렬은 주어진 원소들을 하나씩 뽑은 후, 정렬된 형태를 가지도록 뽑은 원소를 바른 위치에 삽입하여 나열하는 정렬 방식이다.

arr [] = { 30, 50, 20, 10, 40 }의 배열로 삽입 정렬을 이용하여 정렬해보자.

초기의 배열 상태

① 먼저 두 번째 원소부터 시작을 한다. 두 번째 원소 50과 첫 번째 원소인 30을 비교한다. 더 큰 값이 뒤에 있다면 연산을 진행하지 않는다. 30보다 50이 크기 때문에 세 번째 원소로 넘어간다.

50의 값이 크기 때문에 원소 이동은 없음

② 현재까지 나열된 원소는 30과 50이다. 세 번째 원소인 20과 두 번째 원소인 50을 비교할 경우 더 큰 값이 앞에 있기 때문에 배열을 뒤로 밀어줘야 하는데 먼저 해야 할 것은 삽입해야 할 원소를 temp 변수에 저장해둔다.

 

세 번째 원소를 temp 변수에 저장

③ 이후 원소를 삽입하기 위해 빈 공간이 필요한데 배열의 크기는 5개로 고정이 되어있기 때문에 삽입을 위한 빈 공간을 만들어야 한다. 세 번째 원소 20을 현재까지 나열된 원소들과 비교를 시작하며 원소 교환이 아닌 삽입 정렬이기 때문에 자리에 맞는 곳으로 삽입을 해줘야 한다. 삽입해야 할 원소인 temp가 두 번째 원소보다 더 작은 값이라면 앞의 원소들을 한 칸씩 뒤로 밀어줘야 한다. 20과 50을 비교하였을 때 20이 더 작으므로 50을 세 번째 원소로 밀어줘야 하고 20과 30을 비교하였을 때 20이 더 작으므로 두 번째 원소로 밀어줘야 한다. 아래의 그림을 참고해보자.

20과 50을 비교한 후 50이 크므로 뒤의 배열에 50을 대입

20과 30을 비교한 후 30이 크므로 뒤의 배열에 30을 대입

세 번째 원소의 배열 밀기 완료된 결과

④ 20이라는 값을 가진 원소가 삽입해야할 위치를 찾았다. 30보다 앞이며 인덱스 위치로는 영 번째 위치이다. 여기에 20이라는 값을 덮어 씌어주면서 삽입이 완료가 된다. 현재까지 정렬된 결과는 20, 30, 50이 된다.

2-3. temp에 저장해두었던 값을 배열 위치에 삽입

⑤ 위의 과정을 계속 진행하다 보면 최종적으로 아래와 같은 정렬된 결과를 얻을 수 있다.

삽입 정렬 결과

이제 코드로 삽입 정렬을 구현해보자.

#include <iostream>
 
using namespace std;
 
// 원소 개수
#define MAX_LENGTH 5
 
int main()
{
    // 정렬할 배열 선언
    int arr[MAX_LENGTH] = { 30, 50, 20, 10, 40 };
    int temp = 0;
    int index = 0;
 
    // 두 번째 원소부터 원소 개수만큼 순회
    for (int i = 1; i < MAX_LENGTH; ++i)
    {
        // 임시 변수에 삽입할 원소를 저장
        temp = arr[i];
 
        // 원소간 비교 및 한 칸씩 밀어줄 값 저장
        index = i - 1;
 
        while (true)
        {
            // 인덱스가 0보다 작을 경우 검사하지 않음
            if (index < 0)
                break;
 
            // 삽입해야할 원소가 앞의 원소보다 클 경우 검사하지 않음
            if (arr[index] < temp)
                break;
 
            // 한 칸씩 뒤로 밀며 삽입
            arr[index + 1] = arr[index];
            index--;
        }
 
        // 비교 연산을 통해 삽입해야할 위치에 원소 삽입
        arr[index + 1] = temp;
    }
 
    // 출력 결과 확인
    for (int i = 0; i < MAX_LENGTH; ++i)
    {
        cout << arr[i] << endl;
    }
}