[Algorithm][2] 삽입 정렬(Insertion sort)

알고리즘 공부 몰아서 하지 말고

매일마다 뇌를 자극하도록 하는 차원에서 시작하는.

삽입 정렬 

말로 표현 (오름차순인 경우)

"i번 선수는 자신의 왼쪽만 보고, 자신이 가장 크면 가만히 있는다. 자신이 가장 크지 않다면 자신이 있어야 할 자리로 이동하게 된다. 이때 i번 선수가 자신의 자리를 찾아간다기 보다는 다른 선수들이 한 칸씩 이동하면서 최종적으로 생기는 자리에 들어가기만 하면 된다"

#include <iostream>
 
// 190313 sort_insertion
using namespace std;
 
class Sort {
public :
 
    static void insert(int* src, int count) {
 
        int temp;
        int j; 
        for (int i = 1; i < count; i++) {
            temp = src[i]; // 일단 임시 장소로 이동시키고 src[i]를 비워두는 느낌.
            // src[i]가 빈자리라고 생각할 수 있습니다.
            j = i;
            while (j > 0  &&  src[j - 1] > temp ) {  
                // while 처음 시작하면 빈자리의 바로 앞부터 확인해보는 것입니다.
                // 조건문에서 j > 0이 src[j-1] > temp보다 앞에 있어야 한다.
                // array outofrange(-1) error 발생가능하기 때문
                src[j] = src[j - 1];
                j--;
                // while문을 돌면서 한 칸씩 앞으로 이동하며 크기 검사를 하겠죠.
            }
            src[j] = temp; // 빈자리에 삽입
        }
        printArray(src, count);
    }
 
    static void printArray(int *src, int count) {
        for (int i = 0; i < count; i++) {
            cout << src[i] << " ";
        }   cout << endl;
    }
 
};
 
int main() {
 
    int src[] = { 3, 4, 7, 9, 2, 1, 10, 300, 200, 90 };
    Sort::insert(src, sizeof(src)/sizeof(int));
 
}