[C/알고리즘] 삽입정렬 Insertion Sort

// 삽입정렬 insertionsort.c

#include <stdio.h>
#include <stdlib.h>

// int형 두개를 맞바꿔주는 함수.
void int_swap(int *x, int *y) {
   int tmp = *x;
   *x = *y;
   *y = tmp;
}

// long int형 두개를 맞바꿔주는 함수.
void long_swap(long *x, long *y) {
   long tmp = *x;
   *x = *y;
   *y = tmp;
}

// 배열의 내용을 출력한다.
void printArray(int *array, int length) {
    for (int i = 0; i < length; i++) {
        printf("%ld\n", array[i]);
    }
    printf("\n");
}

// 삽입정렬 함수: int *array: 배열, int length: 배열의 길이

void insertionSort(int *array, int length) {

    //배열의 길이 -1 만큼 순회하면 된다.
    for (int i = 1; i < length ; i++) {
		// 새로운 원소가, 정렬된 것들 뒤에서부터 차근차근 앞으로 오며 자신의 값보다 큰 값이 있으면 교체하고
		// 작은 값을 만나면 멈춘다. 이미 그 부분 앞으로는 정렬이 되어 있기 때문에.
        for (int j = i; j > 0; j--) { 
            if (array[j-1] > array[j]) //앞의 값과 비교하여 앞의 값이 크면 
                int_swap(&array[j-1], &array[j]); //그것과 자신을 교체한다.
            else 
                break;
        }
    }
}

int main (){
    //int array[] = {5, 7, 4, 3, 2};
    //int array[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; // 10개
    //int length = sizeof(array) / sizeof(int);
    const int length = 1000;

	//메모리를 할당하여 난수를 넣어서 정렬을 해본다.
    int *array = calloc(length, sizeof(int));
    for (int i = 0; i < length; i++)
        array[i] = rand();

    insertionSort(array, length);
    // 정렬한 내용을 출력한다.
    printArray(array, length);
    
    free(array);
    return 0;
}
-------- 실행 결과 -----------
2416949
6072641
6939507
7684930
8936987
10901063
11614769
11671338
12260289
12895151
..........
2118421993
2130794395
2135019593
2137100237
2137390358
2142757034
2143124030
2145174067
2147469841