Python Coding Test Course, Sorting Numbers 2

1. Problem Description

You need to sort the given numbers in ascending order. This problem focuses on understanding and applying sorting algorithms using Python. The input consists of a list of N numbers, and the output should be the sorted list.

2. Problem Conditions

  • Input: The first line contains the number of elements N. (1 ≤ N ≤ 1,000,000)
  • The second line contains N integers A. (A is an integer between -1,000,000,000 and 1,000,000,000.)
  • Output: The numbers should be printed in ascending order, one per line.

3. Input Example

5
3
1
2
5
4

4. Output Example

1
2
3
4
5

5. Problem Approach

There are various sorting algorithms available to solve this problem, but using Python’s built-in sorted() function is the most efficient and straightforward method. However, we will also explore other sorting algorithms for learning purposes.

5.1. Bubble Sort

Bubble Sort is one of the simplest sorting algorithms that compares two adjacent elements and moves the larger value to the back. The average complexity is O(N^2). It is intuitive but inefficient in terms of performance.

5.2. Selection Sort

Selection Sort works by selecting the smallest value in the list and placing it in the sorted position, then repeating this process with the remaining list. The average complexity of this algorithm is also O(N^2).

5.3. Insertion Sort

Insertion Sort is a method that expands the sorted list one element at a time. It has an average complexity of O(N^2) and is very efficient for sorted data.

5.4. Python’s Sort Function

Python’s sorted() function uses an algorithm called Timsort, which provides an average performance of O(N log N). This is an optimized sort that performs excellently on large datasets.

6. Code Implementation

The code below shows how to receive input and sort the numbers. 

import sys

input = sys.stdin.read
data = input().splitlines()

N = int(data[0])  # Read the number of elements N from the first line.
numbers = []

for i in range(1, N + 1):  # Read the numbers from the second line onwards.
    numbers.append(int(data[i]))

numbers.sort()  # Sort using the default sort function.

for number in numbers:  # Print the sorted numbers.
    print(number)

7. Advanced Sorting Algorithm: Merge Sort

Merge Sort is a type of divide and conquer algorithm that recursively breaks down the list and merges sorted sublists to sort the whole. The average complexity is O(N log N), making it very efficient.

7.1. Merge Sort Implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Example Usage
if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = list(map(int, input().split()))
    
    sorted_data = merge_sort(data)
    for number in sorted_data:
        print(number)

8. Conclusion

Through this problem, we learned not only the basic sorting capabilities of Python but also various sorting algorithms. Understanding the characteristics, complexities, and usage of each algorithm is important. This knowledge will be helpful in solving algorithm problems in the future. It is essential to improve your skills by tackling various problems.

© 2023 Algorithm Education Institution