C# Coding Test Course, Queueing

Hello, blog readers! Today, as part of the C# coding test course, we will address the line-up problem. This problem may seem simple, but without the right algorithm, it can become quite complex. Additionally, it is one of the types of problems frequently encountered in actual job coding tests.

Problem Description

This problem involves lining up students based on their height information. Students should be sorted in ascending order by height, and those with the same height must maintain their original order. In other words, stability must be maintained during sorting.

Problem Definition

    Given an array of students' heights, the task is to sort the array in ascending order.

    Input
    - Integer N: The number of students (1 ≤ N ≤ 100,000)
    - Integer array heights: Heights of the students (1 ≤ heights[i] ≤ 200 cm)

    Output
    - The sorted heights of the students should be returned.
    

Sample Input and Output

    Input: [160, 155, 170, 160, 175]
    Output: [155, 160, 160, 170, 175]
    

Problem-Solving Strategy

It’s important to devise a strategy for solving the problem. Since we need to sort the students’ heights, we should apply an efficient sorting algorithm. Among various sorting algorithms, we can use Merge Sort or Quick Sort, which both have a time complexity of O(N log N).

1. Merge Sort Explanation

Merge sort is a divide-and-conquer algorithm that splits an array into two sub-arrays, sorts each, and then merges the sorted sub-arrays to produce a final sorted array. This method is stable and useful when a sorted array is required.

2. Quick Sort Explanation

Quick sort is also a divide-and-conquer algorithm. It splits the array into two parts based on a pivot and sorts them recursively. The average time complexity is O(N log N), but in the worst case, it can be O(N^2). However, performance can be improved with an appropriate pivot selection.

C# Code Implementation

In this section, we will write code to solve the problem using the C# language. Below is the code that sorts students’ heights using merge sort.

using System;

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

    public static void Merge(int[] heights, 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] = heights[left + i];
        for (int j = 0; j < n2; j++)
            rightArray[j] = heights[mid + 1 + j];

        int k = left;
        int iIndex = 0, jIndex = 0;

        while (iIndex < n1 && jIndex < n2)
        {
            if (leftArray[iIndex] <= rightArray[jIndex])
            {
                heights[k] = leftArray[iIndex];
                iIndex++;
            }
            else
            {
                heights[k] = rightArray[jIndex];
                jIndex++;
            }
            k++;
        }

        while (iIndex < n1)
        {
            heights[k] = leftArray[iIndex];
            iIndex++;
            k++;
        }

        while (jIndex < n2)
        {
            heights[k] = rightArray[jIndex];
            jIndex++;
            k++;
        }
    }

    static void Main(string[] args)
    {
        int[] heights = { 160, 155, 170, 160, 175 };
        MergeSort(heights, 0, heights.Length - 1);

        Console.WriteLine("Sorted heights: " + string.Join(", ", heights));
    }
}
    

Code Explanation

The code above is an example of sorting a given array using the merge sort algorithm. The MergeSort method recursively divides the array, and the Merge method merges the two sub-arrays to achieve sorted order.

Code Flow

• MergeSort Method: Recursively divides the array into halves to sort it.
• Merge Method: Merges two sorted sub-arrays into one sorted array.
• Main Method: The starting point of the program, defining a sample array, sorting it, and outputting the result.

Performance Analysis

The time complexity of merge sort is O(N log N) and remains the same in the worst case. The space complexity is O(N). This is advantageous when processing large datasets. Because sorting is stable, for example, in cases where heights are the same, the original order can be guaranteed.

Applications of This Problem

The line-up problem can be applied in many fields. For example, it can be useful in queue management, student performance analysis, and various other scenarios. While solving this problem, it's good to consider the potential for expanding to other data sorting problems.

Conclusion

In this post, we explored how to solve the line-up problem using C#. Through defining the problem and implementing algorithms and code to solve it, we can develop algorithmic thinking. It is important to enhance algorithmic thinking through various problems.

Next time, we will address another type of algorithm problem. Please leave any questions or feedback in the comments. Thank you!