Swift Coding Test Course, Sorting Numbers 2

In this post, we will discuss sorting problems that are frequently presented in coding tests using Swift. In particular, we will explore the basics of sorting algorithms through the “Sorting Numbers 2” problem and how it can be applied in actual coding tests.

Problem Description

Sort the given array of N numbers in ascending order and print the result. N is a natural number less than or equal to 1,000,000, and each number in the array is an integer that is less than or equal to 1,000,000 and greater than or equal to 0.

Input: 
    5
    5
    4
    3
    2
    1

    Output: 
    1
    2
    3
    4
    5

Problem-Solving Approach

This problem requires an understanding and implementation of basic sorting algorithms. However, considering the limited time and memory, we need to perform the sorting in the most efficient way. Generally, we can consider quick sort, merge sort, or heap sort, which have a time complexity of O(N log N), but since the range of numbers is limited in this problem, it is efficient to use counting sort.

Counting Sort

Counting sort is useful when the range of data to be sorted is limited. Given that the range of numbers is from 0 to 1,000,000 and duplicates may exist, we can count the occurrences of each number to generate the sorted result. Counting sort follows these steps:

1. Check the maximum value of the input numbers to determine the size of the array.
2. Initialize a counting array with indices from 0 to the maximum value.
3. Read the input numbers and increment the corresponding index in the counting array by 1.
4. Refer to the counting array to output the sorted result.

Swift Implementation

Now, let’s write the code in Swift based on the above approach.

import Foundation

let n = Int(readLine()!)!
var numbers = [Int](repeating: 0, count: 1000001)

// Store input values
for _ in 0..<n {="" if="" let="" number="Int(readLine()!)" numbers[number]="" +="1" }="" output="" the="" sorted="" result="" for="" i="" in="" 0..<numbers.count="" numbers[i]=""> 0 {
        for _ in 0..<numbers[i] {="" print(i)="" }="" }<="" code=""></numbers[i]></n>

<h2>Code Explanation</h2> <p>Let’s explain the above code:</p> <ol> <li>On the first line, `let n = Int(readLine()!)!` reads the number of inputs.</li> <li>`var numbers = [Int](repeating: 0, count: 1000001)` creates a counting array to store numbers from 0 to 1,000,000.</li> <li>Through the loop `for _ in 0..<n`, we="" read="" the="" input="" numbers="" and="" increment="" respective="" index="" in="" counting="" array.<="" li=""> </n`,></li><li>Finally, we traverse the counting array through a nested loop and output the results based on how many times each number appeared.</li> </ol> <h2>Complexity Analysis</h2> <p>The time complexity of this problem is O(N), and the space complexity is O(K) (where K is the range of input numbers, specifically 1,000,001). Therefore, it can handle a large number of inputs efficiently.</p> <h2>Conclusion</h2> <p>In this post, we explored how to solve the "Sorting Numbers 2" problem using counting sort. Counting sort is very useful when the range of data is limited, so keep this in mind. Increasing your understanding of various sorting algorithms can help reduce time and improve your coding quality. In the next post, we will cover another algorithm problem!</p>