[c++] 삽입 정렬

삽입 정렬이란 숫자를 원하는 위치를 찾아가서 삽입하는 정렬이다. 필요한 만큼만 움직여서 시간 복잡도는 n의 제곱이라는 점에서 동일할지라도 연산수가 적으므로 버블 정렬이나 선택 정렬보다 빠르다.

 

 

2 6 4 9 8 1 3 5 7 라는 9개의 숫자를 한 배열에 담고 삽입 정렬을 활용해 오름차순으로 바꾸는 시뮬레이션을 해보자.

제일 앞 숫자를 0번째 인덱스, 마지막 숫자를 8번째 인덱스라 가정한다.

2 6 4 9 8 1 3 5 7              //2<6이므로 2와 6 패스

2 _ 6 '4' 9 8 1 3 5 7          //4를 6 앞에 넣으면 되겠다.(6과 자리바꿈)

2 4 6 9 8 1 3 5 7              //현재 상황(불완전하지만 정렬이 차츰 되고 있음)

2 4 6 _ 9 '8' 1 3 5 7          //6<9이므로 9패스 8을 9 앞에 넣자. (9와 자리바꿈)

2 4 6 8 9 1 3 5 7             //현재 상황(불완전하지만 정렬이 차츰 되고 있음)

_ 2 4 6 8 9 '1' 3 5 7          //1을 2 앞에 넣으면 되겠다.(9 -> 8 -> 6 -> 4->2 모두 반복문으로 비교하다가 맨 앞 정착 )

1 2 4 6 8 9 3 5 7             //현재 상황(불완전하지만 정렬이 차츰 되고 있음)

1 2 _ 4 6 8 9 '3' 5 7          //3을 4 앞에 넣자. (9-> 8-> 6-> 4 모두 반복문으로 비교하다가 4 앞 정착)

1 2 3 4 6 8 9 5 7             //현재 상황(불완전하지만 정렬이 차츰 되고 있음)

1 2 3 4 _ 6 8 9 '5' 7          //5를 6 앞에 넣자. (9 -> 8-> 6 모두 반복문으로 비교하다가 6 앞 정착)

1 2 3 4 5 6 8 9 7             //현재 상황(불완전하지만 정렬이 차츰 되고 있음)

1 2 3 4 5 6 _ 8 9 '7'          //7을 8 앞에 넣자. (9 -> 8 모두 반복문으로 비교하다가 8앞 정착)

1 2 3 4 5 6 7 8 9             //완료~~

 

#include <iostream>
#include <array>
using namespace std;

int main()
{
     int temp = INT_MAX;
     int j= INT_MAX;
     int arr[10] = { 14,2,37,4,56,6,567,568,93,102 };
     for (int i = 0; i < 9; i++)
     {
         j = i;
             while (arr[j] >= arr[j + 1])
             {
             temp = arr[j];
             arr[j] = arr[j + 1];
             arr[j + 1] = temp;
             j--;

            if (j < 0)
                break;
             }
     }

for (auto ele:arr)
{
     cout << ele << " ";
}
return 0;
}

---

필자가 즐겨쓰는 std::array로 계속 테스트 해보다가 "array subscript out of range" 경고문이 떠서 포기할까 했지만

            if (j < 0)
                break;

넣어주니 쓰레기값이 없어져서인지 정상 작동하였다. 예외처리의 힘!

마마 증감식 (이번 코드에 사용한 j-- 같이...)을 사용할 때는 예외처리를 꼼꼼하게 해주도록 하자!

---

#include <iostream>
#include <array>
using namespace std;

int main()
{
    int temp = INT_MAX;
    int j = INT_MAX;
    array<int,10>arr = { 14,2,37,4,56,6,567,568,93,102 };
    for (int i = 0; i < 9; i++)
    {
        j = i;
        while (arr[j] >= arr[j + 1])
        {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            j--;
            if (j < 0)
                break;
        }
    }

    for (auto ele : arr)
    {
        cout << ele << " ";
    }
    return 0;
}