C# Coding Test Course, Insertion Sort

Introduction

Hello. In this lecture, we will take a deep dive into one of the useful sorting algorithms for preparing coding tests, called ‘Insertion Sort’. Sorting algorithms are an important topic that forms the foundation for data structures and algorithm problem-solving. In particular, we aim to help readers understand by presenting theoretical background, code implementation, and specific examples of problem-solving.

What is Insertion Sort?

Insertion Sort is a sorting algorithm that works by inserting new data into an already sorted state. It selects one element at a time from the given data and inserts it into the appropriate position by comparing it with the already sorted portion. This algorithm is very intuitive and easy to implement.

How Insertion Sort Works

Insertion Sort works in the following way:

1. Select the first element from the unsorted list. This element is considered to be already sorted.
2. Select the next element and compare it with the sorted elements.
3. If the currently selected element is smaller than the sorted element, insert it into the appropriate position in the sorted list.
4. Repeat this process until the end of the list.

Time Complexity of Insertion Sort

The time complexity of Insertion Sort is O(n²) in the worst case. However, if the data is nearly sorted, it shows an average performance of O(n). This can be an advantage of Insertion Sort compared to other algorithms. In special cases, it operates in O(n), making it frequently used in real problems.

C# Implementation of Insertion Sort

Now, let’s implement the Insertion Sort algorithm using C#:

using System;

class Program
{
    static void InsertionSort(int[] arr)
    {
        for (int i = 1; i < arr.Length; i++)
        {
            int key = arr[i];
            int j = i - 1;

            // Move elements that are greater than the current key one position back
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // Insert the key in the appropriate position
        }
    }

    static void Main()
    {
        int[] array = { 12, 11, 13, 5, 6 };
        InsertionSort(array);

        Console.WriteLine("Sorted array: ");
        foreach (int num in array)
        {
            Console.Write(num + " ");
        }
    }
}

Problem Solving: Sorting Given Array

Here is an example of a problem that may be given in a coding test:

Problem: Given an integer array, use insertion sort to sort the array in ascending order.

Input Example: [64, 34, 25, 12, 22, 11, 90]

Output Example: [11, 12, 22, 25, 34, 64, 90]

To solve the above problem, we can implement the Insertion Sort algorithm as previously described. Let’s sort the given array using insertion sort.

using System;

class InsertionSortExample
{
    static void InsertSort(int[] array)
    {
        for (int i = 1; i < array.Length; i++)
        {
            int key = array[i];
            int j = i - 1;

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

    static void Main()
    {
        int[] nums = { 64, 34, 25, 12, 22, 11, 90 };
        InsertSort(nums);

        Console.WriteLine("Sorted array: ");
        foreach (var num in nums)
        {
            Console.Write(num + " ");
        }
    }
}

Conclusion

In this lecture, we have deeply understood the Insertion Sort algorithm, how to implement it in C#, and the process of solving actual problems. Due to its relatively easy understanding and implementation, Insertion Sort is often used as the basis for many coding test problems. Now that you have mastered Insertion Sort, try solving various problems to further improve your skills!