Sorting Algorithm :: Insertion Sort(삽입 정렬)

1. Principle of the Insertion Sort

It is pretty similar to sorting Cards in your hands in order.

https://www.youtube.com/watch?v=OGzPmgsI-pQ

2. Algorithm of the Insertion Sort

2.1 Method 1 (Using While loop)

void insert(int arr[])
{
    int n = sizeof(arr) / sizeof(int); //To find out the size of the array
    int key;
    int j
    
    for (int i=1; i<n; i++)
    {
        key = a[i]; //This is like picking the card you'll move
        for (j=i; j>0; j--)
        {
            if (a[j-1] > key)
            {
                a[j] = a[j-1];
            }
            else 
                break;
        }
        a[j] = key;
    }
}

* else

If you don't write 'else' statement, You cannot insert a key value in an appropriate location.

2.2 Method 2 (Using for loop)

void insert(int arr[])
{
	int n = sizeof(arr) / sizeof(int);
	int key;
	int j;

	for (int i = 1; i < n; i++)
	{
		key = a[i];
		j = i - 1;

		while (j >= 0 && a[j] > key)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = key;
	}
}