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

1. Principle of the Insertion Sort

It is pretty similar to sorting Cards in your hands in order. (You could also see the contents about Bubble Sort)

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;
    }
}

   2.1.1 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;
	}
}

More information: Insertion Sort