C# Coding Test Course, Sorting Numbers 1

Hello! In this post, we will discuss one of the problems frequently encountered in coding tests using C#: “Sorting Numbers”. This tutorial will explain the understanding of algorithm problems, the resolution process in detail, and finally how to implement C# code.

Problem Description

This problem requires you to input numbers equal to the given quantity and output those numbers sorted in ascending order. We will solve the problem using various methods along with a basic understanding of sorting algorithms.

Problem Input

• The first line contains the quantity of numbers N (1 ≤ N ≤ 100,000).
• From the second line onward, N lines will contain the numbers. Each number is an integer whose absolute value is less than or equal to 1,000,000.

Problem Output

Output the sorted results in ascending order from the first line to the Nth line.

Example

Input
5
5
2
3
1
4

Output
1
2
3
4
5

Problem Solving Process

This problem is simply about sorting the given numbers, and we can use various sorting algorithms. In this article, I will explain how to solve the problem using one of the basic sorting algorithms, “Merge Sort”, and “C#’s built-in sorting methods”.

1. Merge Sort

Merge Sort is a type of divide and conquer algorithm, which divides the given array into halves, sorts both halves, and then merges them back together. It has a time complexity of O(N log N) in both average and worst-case scenarios, and it is a stable sorting method.

Merge Sort Procedure

1. Recursively divide the array until it is split into single elements.
2. Sort and merge the split arrays.

Implementing Merge Sort

Now, let’s implement Merge Sort in C#.

public class MergeSort
{
    public static void Sort(int[] array, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;

            // Divide the array elements
            Sort(array, left, mid);
            Sort(array, mid + 1, right);

            // Merge the sorted halves
            Merge(array, left, mid, right);
        }
    }

    public static void Merge(int[] array, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++)
            leftArray[i] = array[left + i];

        for (int j = 0; j < n2; j++)
            rightArray[j] = array[mid + 1 + j];

        int k = left, l = 0, m = 0;

        while (l < n1 && m < n2)
        {
            if (leftArray[l] <= rightArray[m])
            {
                array[k] = leftArray[l];
                l++;
            }
            else
            {
                array[k] = rightArray[m];
                m++;
            }
            k++;
        }

        while (l < n1)
        {
            array[k] = leftArray[l];
            l++;
            k++;
        }

        while (m < n2)
        {
            array[k] = rightArray[m];
            m++;
            k++;
        }
    }
}

2. Using C# Built-in Sorting Method

In C#, using the built-in sorting methods allows for a simpler way to solve the problem.

using System;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] numbers = new int[n];

        for (int i = 0; i < n; i++)
        {
            numbers[i] = int.Parse(Console.ReadLine());
        }

        Array.Sort(numbers);

        foreach (var num in numbers)
        {
            Console.WriteLine(num);
        }
    }
}

Analysis and Conclusion

This problem is a great opportunity to learn the basics of sorting. We learned how sorting occurs through Merge Sort and C#’s built-in methods, and which method is more efficient. Since this type of problem is frequently encountered in coding tests, it is advisable to practice often.

In the next post, we will cover more complex sorting problems or algorithms. I hope you continue to study and improve your abilities as a coding tester!