insertion sort(삽입정렬)

삽입정렬
- 사람들이 카드놀이를 할 때 손에 쥔 카드를 정렬하는 방식을 생각해보면 되겠습니다.  일단 왼손에 아무것도 쥐지 않고, 카드는 탁자위에 있다고 해봅시다. 탁자에 카드를 한장씩 가져와 왼손의 적절한 위치에 넣습니다. 카드를 삽입할 적절한 위치를 찾기 위해 왼손의 카드들을 찾아보겠죠. 참고로 왼손의 카드들은 다 정렬된 상태가 되겠습니다. 밑의 그림을 확인해보세요...

각각 a,b,c의 첫번째 테이블에서 각각 가리키는 화살표를 기준으로 위의 값들은 왼손에 있는카드(정렬된 상태)라고 보면 되겠고, 화살표 밑의 값들을 오른손에서 왼손의 적절한 위치에 삽입할 카드라고 보면 되겠네요. 

/* insertion.cpp */

#include <iostream>

using namespace std;

int main()

{

        const int arraySize = 10;

        int data[arraySize];

        int insert;

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

               cin >> data[i];

        for(int next=1; next < arraySize; next++)

        {

               insert = data[next];

               int moveItem = next;

               while((moveItem > 0) && (data[moveItem - 1] > insert))

               {

                       data[moveItem] = data[moveItem - 1];

                       moveItem--;

               } 

               data[moveItem] = insert;

        }

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

        cout << data[i] << " " ;

} // insertion sort