one ️⃣ Overview of contestants

The first four groups of contestants:

👉First group: insert sort, Hill sort
👉Group 2: select sort, heap sort
👉Group 3: bubble sort, quick sort (highlight)
👉Group 4: merge sort

The previous blogs focused on the following sorting content, as well as the optimization process and performance analysis.

Here, four contestants finally entered the finals. They are Hill sort, heap sort, quick sort, merge sort. The following analysis summarizes their characteristics and compares their performance.

two ️⃣ Characteristic summary

Time complexity and space complexity

Classification summary

three ️⃣ performance comparison

The best versions of corresponding sorting are compared here to show the best performance.

Classes used in the test:

/**
 * Sort auxiliary class
 * Generate a test array and test the sorting algorithm
 **/
public class SortHelper {
    // Gets the object of the random number
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();
    
    //Generate n random numbers on [left...right]
    public static int[] generateRandomArray(int n,int left,int right) {
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(left,right);
        }
        return arr;
    }

    /**
     * Generates a near ordered array of size n
     * @param n
     * @param times The number of exchanges, the smaller the number, the more orderly, the greater the number, the more disorderly
     * @return
     */
    public static int[] generateSoredArray(int n,int times) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        // Exchange some elements. The smaller the number of exchanges, the more orderly
        for (int i = 0; i < times; i++) {
            // Generate a random number on [0..n]
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
        return arr;
    }
    // With the name of the method passed in, you can call the method according to your needs
    // Call the corresponding sorting method according to the method name to sort the arr array
    public static void testSort(String sortName,int[] arr) {
        Class<SevenSort> cls = SevenSort.class;
        try {
            Method method = cls.getDeclaredMethod(sortName,int[].class);
            long start = System.nanoTime();
            method.invoke(null,arr);
            long end = System.nanoTime();
            if (isSorted(arr)) {
                // Correct algorithm
                System.out.println(sortName + "End of sorting,Total time:" + (end - start) / 1000000.0 + "ms");
            }
        } catch (NoSuchMethodException | InvocationTargetException | IllegalAccessException e) {
            e.printStackTrace();
        }
    }

    // Generate a deep copy array of arr
    // In order to test the performance of different sorting algorithms, it needs to be tested on the same data set
    public static int[] arrCopy(int[] arr) {
        return Arrays.copyOf(arr,arr.length);
    }

    public static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                System.err.println("sort error");
                return false;
            }
        }
        return true;
    }
}

Ten million random data

public static void main(String[] args) {
    int n = 10000000;
    int[] arr = SortHelper.generateRandomArray(n, 0, Integer.MAX_VALUE);
    int[] arrCopy4 = SortHelper.arrCopy(arr);
    int[] arrCopy6 = SortHelper.arrCopy(arr);
    int[] arrCopy7 = SortHelper.arrCopy(arr);
    int[] arrCopy10 = SortHelper.arrCopy(arr);
    
    SortHelper.testSort("shellSort", arrCopy4);
    SortHelper.testSort("mergeSortVersion2", arrCopy6);
    SortHelper.testSort("quickSort", arrCopy7);
    SortHelper.testSort("heapSort", arrCopy10);

}

The second way to write merge sort is to define a space as large as the original data at the beginning.
Quick sorting uses one-way quick sorting, which has good performance when sorting a large number of random data.
Moreover, insertion sorting is used between cells to improve the performance as much as possible.
As for Hill sort and heap sort, there is not much optimization space due to the algorithm.

Operation results:

It can be seen that the performance of merge sort and quick sort is very good at this time.

10 million massive duplicate data

int n = 10000000;
int[] arr = SortHelper.generateRandomArray(n,0, 1000);

Because there are a large number of duplicate elements, one-way fast scheduling cannot be used, and the performance is degraded. Here, three-way fast scheduling is the most favorable for sorting a large number of duplicate data. It can arrange the elements with the same reference value once and put them in the final position.

Operation results:

Because fast scheduling uses the most favorable algorithm, its performance is still the best.

Ten million near ordered data

int[] arr = SortHelper.generateSoredArray(n,1000);

For this kind of data, the pit digging method of fast row has special advantages, because many data are already in order. It only needs to sort the disturbed data. Moreover, the pit digging method does not exchange elements frequently, but only assigns values to the data, which is more a process of pit filling.

Operation results:

Therefore, for some data, the performance of fast scheduling will decline, but there are corresponding algorithms to solve it. Therefore, in terms of speed, fast scheduling is well deserved.

As for the other three sorts, the performance is relatively stable. If the data is changeable, it is a good choice to use them. Moreover, merge sorting is close to the performance of fast sorting at any time, and it can also realize external sorting.

In all the sorting algorithms of partition design, the stability of data cannot be guaranteed. If you want data stability, you have to rely on other sorting algorithms.
Therefore, the pursuit of performance may bring some disadvantages. For different scenarios, choosing the appropriate sorting algorithm is the positive solution.

Compared with the first sorting competition written in c code, the java version provides more methods and optimization ideas, and the quality of the code is also improved.

Finally, congratulations to the fast volleyball team for winning the championship again

🌸 Sprinkle flowers at the end 🌸

four ️⃣ All source code

If you need the source code, click the portal below
👇
🌀 Sorting source code full version 🌀