对小整数数组进行排序的最佳算法是什么

1. Overview

In this tutorial, we’ll talk about the best sorting algorithm to sort an array of small integers. First, we’ll define the problem. Then, we’ll give an example to explain it.

Finally, we’ll present two different situations to use that algorithm. The first one will be for an array of small integer numbers, and the other will be about an array with a small absolute difference between any pair of its numbers.

2. Defining the Problem

Suppose we have an array consisting of small integer values. We were asked to sort this array as fast as possible.

Let’s take a look at the following example for a better understanding. Given an integer array , let’s sort it.

We want to rearrange the numbers of the array so the following condition is met: where .

As we can see, the only arrangement that meets the previous condition is , and we call this the sorted array.

Note that this problem is a special case of the general sorting problem. In this version, we should use the fact that the values inside the array are small. Also, we don’t care whether the array size is small or not.

3. Counting Sort Approach

3.1. Main Idea

The main idea in this approach is to count the occurrences of each number of the array . Then, iterate over all the possible values in increasing order and append the current value times to the sorted array, where is the number of occurrences of the current value.

First, for each number in the given array , we increase the count of its value by one. Once we finish the iteration, we’ll have the count of each number of occurrences.

Second, we iterate over all the possible values presented in the array . Since the array consists of small integer numbers, this iteration should be affordable. Then, for each value, we append it to the sorted array by the number of its occurrences.

Finally, the sorted array will have all the numbers of the array sorted in non-decreasing order because we append numbers to it in increasing order.

3.2. Algorithm

Let’s take a look at the implementation of the algorithm:

algorithm countingSort(A):
    // INPUT
    //    A = the array to be sorted
    // OUTPUT
    //    sorted_A = the sorted array
    
    // Initialize the count array
    MAX_VALUE <- the max value of an element in an array
    count <- initialize an array of size MAX_VALUE with all elements as 0
    
    // Count each element in A
    for i <- 0 to length(A) - 1:
        count[A[i]] <- count[A[i]] + 1
    
    // Create sorted array
    sorted_A <- empty list
    for value <- 0 to MAX_VALUE:
        while count[value] > 0:
            append value to sorted_A
            count[value] <- count[value] - 1
    
    return sorted_A

Initially, we declare the function that will return the sorted array. The function will have one parameter , representing the given array that we want to sort.

First, we declare the array that will store the number of occurrences of each number in the given array . Then, we iterate over each element in the array and increase its by one.

Second, we declare that the array will be the sorted version of the given array . Next, we iterate over all the possible values in the given array in increasing order. For each value , we append it to the sorted array by times.

Finally, we return the , the sorted version of the given array .

3.3. Complexity

The time complexity of this algorithm is , where is the length of the given array and is the maximum value that could exist in the given array . The reason behind this complexity is that we iterate over each value in the array once, and the sum of occurrences of all possible values will be exactly .

4. Small Absolute Difference Approach

4.1. Main Idea

The main idea in this approach is to shift all the numbers in the given array by a specific offset to decrease the value of the given array numbers and keep the numbers non-negative. Then, sorting the shifted array is equivalent to sorting the initial array.

The optimal offset is the maximum value we could use to shift the array numbers and keep them non-negative. Thus, it’s equal to the minimum value in the given array . Then, for each number in , we increase the number shifted by the offset by one.

Next, we iterate over all possible shifted values. These values will range from zero until the maximum value in minus the minimum value. We’ll append the original value to the sorted array by the number of its shifted value occurrences for each of them.

Finally, the sorted array will have all the numbers of the array sorted in non-decreasing order.

4.2. Algorithm

Let’s take a look at the implementation of the algorithm:

algorithm countingSortWithSmallAbsoluteDifference(A):
    // INPUT
    //    A = the array to be sorted
    // OUTPUT
    //    sorted_A = the sorted array adjusted for small absolute differences
    
    // Initialize count array and offset
    count <- initialize an array with 0s
    offset <- the minimum of A
    
    // Adjust the count for the offset to handle negative values or small differences
    for i <- 0 to length(A) - 1:
        count[A[i] - offset] <- count[A[i] - offset] + 1
    
    // Create sorted array considering the offset
    sorted_A <- empty list
    max_difference <- the maximum of A - the minimum of A
    for difference <- 0 to max_difference:
        while count[difference] > 0:
            append (difference + offset) to sorted_A
            count[difference] <- count[difference] - 1

    return sorted_A

We declare the same function as in the previous approach.

First, we declare the array that will store the number of occurrences of each shifted number in the given array . Also, we declare the , which represents the maximum value that we could subtract from the numbers of the array and keep all the numbers non-negative.

Then, we iterate over each element in the array and increase the of the current number minus the by one.

Second, we declare that the array will be the sorted version of the given array . We also declare , which will store the bandwidth of all possible differences in the given array.

Next, we iterate over all the possible differences in the given array in increasing order. For each difference , we append it to the sorted array after adding the initial by times.

Finally, we return the , the sorted version of the given array .

4.3. Complexity

The time complexity of this algorithm is , where is the length of the given array and is the maximum absolute difference between any pair of the given array . The reason behind this complexity is the same as in the previous approach.

5. Conclusion

In this article, we presented the best sorting algorithm to sort an array of small integer numbers.

First, we provided an example to explain the problem. Then, we explored two different situations where we could use that algorithm.

Finally, we walked through their implementations and explained the idea behind each of them.