[C코드] :: INSERTION SORT code (삽입 정렬 코드)

INSERTION SORT (삽입정렬)

What is it?

• Insertion sort (삽입정렬), 많은 정렬 중 널리 쓰이는 정렬기법이다.
• 정렬된 하위배열에 원소를 채워넣는 기법이다.
• Worst Case, 'O( n² )'
• 간단한 코드지만, 부연 설명을 하자면
• 값이 이미 채워져 있는 데이터 기반이 아닌, 값을 채울 때마다 바로바로 정렬되는 방식이다.
• 리스트로 구현하는 원리와 비슷하다.

CODE

/*************************************************
 * INSERTION SORT ******************************
 * **************************** insertionsort.c ****
 * ***********************************************/

#include <stdio.h>


/* Length of Array */
#define MAX_BUFF 10


/* Declaring for functions */
void Initiation(int arr[]);                                                // Initiation for Array
void PrintArray(int arr[]);                                              // Print Array
void InsertionSort(int arr[], int InputValue);        // Insertion Sort


/* Global variable for counting */
int CountValues = 0;


/* **************** *
 * MAIN FUNCTION *
 * **************** */
int main()
{
    
    /* Variables */
    int mInputValue = 0;                                // Input Value
    int mCountValue = 0;                              // Count
    int SortedArray[MAX_BUFF + 1];        // Array


    /* Initiation */
    Initiation(SortedArray);


    printf("\n");
    /* Enter the Input for the number of array's size */
    while(mCountValue < MAX_BUFF)
    {
        printf("Enter the number which you wanna into an Arrary : ");
        scanf("%d", &mInputValue);
        CountValues++;
        mCountValue++;
        /* SORT */
        InsertionSort(SortedArray, mInputValue);
        PrintArray(SortedArray);	
    }
    printf("\n");

    return 0;  
}


/* Initiation function */
void Initiation(int arr[])
{
    int Index = 0;
    for ( Index = 0; Index < MAX_BUFF; Index++)
    {
        arr[Index] = '\0';
    }
}


/* Print function */
void PrintArray(int arr[])
{
    int Index = 0;
    printf("\n[ ");
    for( Index = 0; Index < MAX_BUFF; Index++ )
    {
        printf("%d ", arr[Index]);
    }
    printf("]\nThe number of Values : %d\n\n", CountValues);
}


/* ******************
 * INSERTION SORT *
 * ***************** */
void InsertionSort(int arr[], int aInputValue)
{
    
    /* Variables for FOR clauses */
    int Seeing = 0;
    int Index = 0;
	
    for ( Seeing = 0; Seeing < CountValues; Seeing++ )
    {
        /* If an Array is empty, */
        if ( arr[Seeing] == '\0' )
        {
            arr[Seeing] = aInputValue;
        }

        /* If Array[INDEX] > Input, */
        if ( arr[Seeing] > aInputValue )
        {
            /* Move 1 index on right all values which bigger than Input */
            for ( Index = CountValues; Index > Seeing; Index-- )
            {
                arr[Index] = arr[Index-1];
            }
            arr[Seeing] = aInputValue;
            break;
        } // IF
    } // FOR
	
}