삽입정렬(insertion sort) C++소스

삽입정렬 C++소스입니다. 

하나하나 어떻게 돌아가는지 알아볼게요.

삽입정렬(Insertion Sort)

---

#include<iostream>

#include<algorithm>

using namespace std;

int arr[8]={8,6,5,3,1,2,7,4};

int main()

{

    int key=0;

    for(int i=1;i<8;i++)//1부터 시작하는 이유 : 삽입정렬은 정렬된 크기를 하나씩 늘려나가는 정렬 알고리즘으로, 하나의 원소는 정렬된 상태이기 때문에 두번째 원소부터 시작합니다.

    {

        key=arr[i];//현재 배열의 i번째 원소를 key라고 해줍니다. 

        int index= i;//현재 인덱스를 기준으로 현재 인덱스 이전에 있는 원소들과 비교하며 삽입을 진행하므로 현재 i를 index에 저장해줍니다. 위 key에 저장되어있는건 "배열의 i번째 원소, 즉 i번째에 있는 값"이며, index는 말 그대로 "i번째 위치"를 저장한다는 것. 헷갈리지 마세요.

        while(index> 0 && (arr[index-1]>key))//while문을 돌게 되는데, 삽입정렬은 현재 위치 "이전"에 있는 값들을 보며 비교를 해나갑니다. 계속 이전으로 가다보면 배열의 첫번째 위치가 나올테고, 그 전으로 가면 안되겠죠? 그래서 먼저 index가 0보다 큰지 확인해줍니다. 또한, 현재 위치 바로 이전에 있는 값이 기준이 되는 key값 보다 "크다면" => 모든 조건이 만족하므로 while문의 조건이 true이게 됩니다. 이 while문이 true가 되면, 

        {

            arr[index]=arr[index-1];//arr[index]. 즉 현재 위치에 있는 원소에 내 이전에 있던 값을 넣어줍니다. 그냥 덮어쓴다고 생각하시면 됩니다. 자리를 만들어주기위해 이런 작업을 하는 것입니다. 왜 이런작업을 해주냐고 궁금증이 생기실 수 있는데, 위 while 조건에서 arr[index-1]>key를 검사해주죠? 현재 key보다 큰 값을 만난것입니다. 그럼 현재 key가 들어갈 자리는 무조건 현재 자리 "이전"에 있겠죠? 이 key가 들어갈 자리를 만들어놓는 것입니다. 

            index--;//하지만, 자리를 만들어놨다고 들어가는것이 아니죠. 또 들어갈 자리가 있는지 비교해주어야 합니다. index를 하나 줄이고, 다시 while문으로 돌아가게 됩니다.

만약, while문에서 하나의 조건이라도 만족하지 못하게 되면, false가 되므로 while문을 실행하지 않게 됩니다. 예를 들어 arr[index-1]>key를 만족하지 못했다면, 이 말인 즉슨 key보다 "작은 값"을 발견했다는 뜻이 됩니다. 삽입정렬은 현재 정렬을 시작할 인덱스의 위치까지(현재 i)는 정렬이 완료된 상태입니다. 전체 배열로 보는 것 보다 하나하나 사이즈를 늘려가면서 정렬된 크기를 늘려간다고 생각하시면 이해가 빠르게 되실겁니다. 즉, 나보다 작은 값을 발견했다는 것은 그 앞은 볼 필요도 없다는 것이죠. 왜냐하면 내가 발견한 작은값보다 더 작은값들이 앞에 있을테니까요.

        }

        arr[index]=key;//while문의 조건이 false로 종료되게 되면, 내가 발견한 자리에 이 key값을 넣어줍니다. 그냥 arr[index]에 넣어도 되나요? --> while문이 종료되기 직전 arr[index]=arr[index-1]로 현재 위치에 있는 값을 뒤로 한칸 밀고, index를 하나 감소시켜 주었습니다. 이 현재 감소된 index가 최종적으로 key가 들어갈 자리이게 되는 것입니다.(다음 while문 조건에서 false가 되었으므로.)

    }

    for(int i=0;i<8;i++)

        cout<<arr[i]<<" ";

}

주석(설명)이 없는 코드입니다. 

#include<iostream>

#include<algorithm>

using namespace std;

int arr[8]={100,6,5,3,1,2,7,4};

int main()

{

    int key=0;

    for(int i=1;i<8;i++)

    {

        key=arr[i];

        int index= i;

        while(index> 0 && (arr[index-1]>key))

        {

            arr[index]=arr[index-1];

            index--;

        }

        arr[index]=key;

    }

    for(int i=0;i<8;i++)

        cout<<arr[i]<<" ";

}