Algorithms like Merge Sort perform operations to sort a given sequence of elements. Most of the built-in
sort()functions in different programming languages perform operations as well. A natural question arises - is there any way to perform sorting more quicker?
One basic algorithm that sorts a sequence of elements in linear time, meaning that it performs operations, is the Counting Sort algorithm. Counting sort is an efficient, linear-time sorting algorithm that is particularly well-suited for sorting a collection of items where the values are known to be small integers.
The basic idea behind counting sort is to use a histogram-like structure to count the number of items in the input collection that have a given value, and then use this information to reorder the items in the input into the desired sorted order.
So, to sort an array with values
[7, 3, 5, 5, 1, 1, 6, 3, 4, 4, 3, 3, 7, 7, 1, 2, 5, 7, 4, 1, 7, 2, 1, 5, 5, 3, 1, 4, 8, 7], we would create a histogram that would show that there are 6 ones, 2 twos, 5 threes, etc:
[6, 2, 5, 4, 5, 1, 6, 1](like presented in the picture).
a = ... bottom, top = min(a), max(a) + 1 # Determine the range hist =  * (top - bottom) # Fill the range with 0s => no counts for num in a: # Iterate through the array hist[num - bottom] += 1 # Increase the histogram value res =  # Initialize the result array for num in range(bottom, top): # Iterate over the range res += [num] * hist[num - bottom] # Add as many `num`s to result as the value in the histogram
In the end, the result will have the value
[1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8].
Note that this approach would work for only numbers, specifically small numbers, while other algorithms like Bubble sort or Merge sort work on arbitrary elements that can be compared to each other.
So, the algorithm performs operations in total, where
nis the number of elements in the initial array, while
ris the size of the range of the values in the given array. This can be especially fast compared to algorithms like Merge sort when working with numbers that have a relatively small range of values.
Are there other linear-time algorithms for sorting? Yes, you can have a look at Radix-sort. Yet, they only work for numbers. If we take only comparison-based algorithms, that can work on any type of sequence, and the only thing required is being able to compare the items in the given sequence, then the best algorithm can perform operations, not less.
The first line of the input contains a single integer
n(1 ≤ n ≤ ).
The next line contains
nspace-separated integers (-100 ≤ ≤ 100).
The program should print the given
nintegers separated by a space in increasing order.
5 -3 5 -1 2 10
-3 -1 2 5 10
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 5 MB