python coding test course, 022 sorting numbers 3

Problem Overview

This problem requires writing an algorithm to sort N given numbers in ascending order. The range of the given numbers is from 1 to 10000, and each number is an integer greater than 0 and less than or equal to 10000. Therefore, we need to implement an efficient sorting algorithm considering this aspect.

Problem Description

Please write a program that sorts the given N numbers and prints one number per line. The maximum number of inputs can be 1,000,000. Thus, since we need to sort a large quantity of numbers, we must consider the time complexity.

Input

The first line of the input contains the number of elements N (1 ≤ N ≤ 1,000,000), followed by N lines each containing a number.

Output

Print the sorted numbers one per line.

Example Input

    5
    5
    4
    3
    2
    1

Example Output

    1
    2
    3
    4
    5

Problem Analysis

Given the constraints, we can use a sorting algorithm that is efficient in terms of time and space. Python’s built-in sorting functionality utilizes Timsort, which has a time complexity of O(N log N) in the average and worst-case scenarios. However, considering the range of numbers is limited (from 1 to 10000), we can also explore counting sort or bucket sort for this specific task.

Proposed Solution

We will use Counting Sort to solve this problem. Counting Sort works as follows:

  • Create a counting array to count the number of input numbers. The size of the array is set to 10001 (including 0~10000).
  • Store the occurrence count of each number in the counting array.
  • Iterate through the counting array to print each number in sorted order.

Code Implementation

import sys

def counting_sort(n, numbers):
    count = [0] * 10001  # Create size 10001 for numbers range from 0 to 10000

    for num in numbers:
        count[num] += 1  # Count occurrences of the numbers

    result = []
    for i in range(10001):
        while count[i] > 0:
            result.append(i)  # Add to result array based on count array values
            count[i] -= 1

    return result

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    numbers = [int(sys.stdin.readline()) for _ in range(n)]
    
    sorted_numbers = counting_sort(n, numbers)
    print("\n".join(map(str, sorted_numbers)))

Main Points

  • Counting Sort is a stable sorting algorithm. This means that the relative position of elements with the same value is preserved.
  • This algorithm has a time complexity of O(N + K), where N is the size of the input and K is the range of the numbers.
  • The memory usage is also efficient as long as K is not too large.

Conclusion

By practicing the Counting Sort algorithm through this problem, we learned how to maximize sorting performance. Additionally, we acquired knowledge about basic input/output handling and array usage in Python. Understanding various sorting algorithms is a critical aspect of programming tests, and approaching problems in this way will be very helpful.

Additional Problems: Variations and Applications

Furthermore, you can try the following variations of the problem:

  • If you need to sort numbers that include negative values, how would you expand the input range and adjust the counting array indices?
  • Utilize various sorting algorithms to analyze the differences in time complexity when sorting the same set of numbers.
  • When the range of numbers (K) is very large, what algorithms can be used as alternatives to Counting Sort?