Research on the time complexity of a test class to simplify the sorting algorithm

catalog

1, Background

In the process of learning algorithm, in addition to mastering the program logic of various algorithms, some test cases are often used to test the time complexity of the algorithm. In this paper, we will build a test class toolkit, so that we can more easily study the time complexity of sorting algorithm.

2, Concept

2.1 definition of time complexity

That is, the time measurement of the process from the initial state of the sequence to the final sorting state formed by the sorting algorithm

2.2 comparison of time complexity
Sorting algorithm Time complexity (average) Time complexity (best) Time complexity (worst)
Bubble sorting O(n2) O(n) O(n2)
Select sort O(n2) O(n2) O(n2)
Insert sort O(n2) O(n) O(n2)
Shell Sort O(n logn) O(n log2n) O(n log2n)
Merge sort O(n logn) O(n logn) O(n logn)
Quick sort O(n logn) O(n logn) O(n2)
Heap sort O(n logn) O(n logn) O(n logn)
  • Time complexity curve

3, Test class

3.1 program structure
  • For the convenience of writing, this test class only implements insertion sorting and fast sorting. Readers can add other sorting algorithms according to the interface definition.

3.2 test tools
  • Generate a disordered array
  • Generate a near sequential array of integers starting at 0
  • Make a full copy of an integer array
  • Determine whether an integer array has been arranged in ascending order
  • Traversal print array
  • Through the sorting interface, call various sorting algorithms for testing
/**
 * Integer sorting test tool class
 *
 * @author zhuhuix
 * @date 2020-06-06
 */
public class SortUtils {

    /**
     * Generate a disordered array
     *
     * @param count       Number of arrays
     * @param startRanger Number range start value
     * @param endRanger   Digital range end value
     * @return Disordered array of integers
     */
    public static int[] generateRandomArray(int count, int startRanger, int endRanger) {
        if (startRanger <= endRanger) {
            int[] arr = new int[count];
            Random random = new Random();
            for (int i = 0; i < count; i++) {
                arr[i] = startRanger + random.nextInt(endRanger - startRanger );
            }
            return arr;
        } else {
            return null;
        }

    }

    /**
     * Generate a near sequential array of integers starting at 0
     *
     * @param count     Number of arrays
     * @param swapCount Number range start value
     * @return Near sequential array of integers
     */
    public static int[] generateNearlyOrderedArray(int count, int swapCount) {

        int[] arr = new int[count];
        for (int i = 0; i < count; i++) {
            arr[i] = i;
        }
        Random random = new Random();
        for (int i = 0; i < swapCount; i++) {
            int x = random.nextInt(count);
            int y = random.nextInt(count);
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
        return arr;

    }

    /**
     * Make a full copy of an integer array
     *
     * @param source Source array
     * @return Array copy
     */
    public static int[] copyArray(int[] source) {
        if (source != null) {
            int dest[] = new int[source.length];
            for (int i = 0; i < source.length; i++) {
                dest[i] = source[i];
            }
            return dest;
        } else {
            return null;
        }
    }

    /**
     * Determine whether an integer array has been arranged in ascending order
     *
     * @param arr integer array 
     * @return Has been sorted in ascending order to true otherwise false
     */
    public static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }

    /**
     * Traversal print array
     * @param arr integer array 
     */
    public static void printArray(int[] arr) {
        if (arr!=null) {
            System.out.print("[");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]);
                if (i != arr.length - 1) {
                    System.out.print(",");
                } else {
                    System.out.println("]");
                }
            }
        }else{
            System.out.println("Array is empty!");
        }
    }

    /**
     * Through the sorting interface, call various sorting algorithms for testing
     * @param sortName Sort algorithm name
     * @param sort Sort unified interface
     * @param arr integer array 
     */
    public static void testSort(final String sortName,Sort sort,int[] arr){
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println(sortName+"Sorting start time:" + sdf.format(start));
        sort.sort(arr);
        Long end = System.currentTimeMillis();
        System.out.println(sortName+"Sorting end time:" + sdf.format(end));
        System.out.println(sortName+"Sort consumed" + (end - start) + "millisecond");
        //Assert to determine whether the array has implemented ascending sorting
        assert(isSorted(arr));
    }

}

3.3 definition of sorting algorithm interface
  • Call the interface definition in the test tool class SortUtils testSort method.
    --public static void testSort(final String sortName,Sort sort,int[] arr)
/**
 * Unified interface definition of integer array sorting
 *
 * @author zhuhuix
 * @date 2020-06-06
 */
public interface Sort {

    /**
     * Integer sort
     * @param arr Array to sort
     */
    void sort(int[] arr);
}

3.4 implementation of various sorting algorithms
  • We can add a variety of sorting algorithms through the implementation of sorting interface. This article only demonstrates insertion sorting and fast sorting
  1. Insert sort
/**
 * Insert sort
 *
 * @author zhuhuix
 * @date 2020-06-06
 */
public class InsertSort implements Sort {
    @Override
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j > 0 && (arr[j - 1] > temp); j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
}
  1. Quick sort
/**
 * Quick sort
 *
 * @author zhuhuix
 * @date 2020-06-06
 */
public class QuickSort implements Sort {
    @Override
    public void sort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int left, int right) {

        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quick(arr, left, partitionIndex - 1);
            quick(arr, partitionIndex + 1, right);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int arr[], int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}
  1. Other sort
public class othersSort implements Sort {
    @Override
    public void sort(int[] arr) {
       // Self implementation of other sorting algorithms
       ....
        }
    }
}
3.5 main test procedure
  • In this paper, we only compare the above two sorting algorithms, and the readers can expand themselves after implementing other sorting algorithms.
/**
 * Integer sort test class
 *  * @author zhuhuix
 * @date 2020-06-06
 */
public class SortTest {

    public static void main(String[] args) {
        int count=100000;

        // Generate a random array
        int[] arr1 = SortUtils.generateRandomArray(count, 0, count);
        // Make a copy of a random array
        int[] arr2 = SortUtils.copyArray(arr1);
        // Sort insert
        SortUtils.testSort("Insertion sort of random disorder order",new InsertSort(),arr1);
        // Make a quick sort
        SortUtils.testSort("Fast sorting of random disorder order",new QuickSort(),arr2);

        // Generate a random array
        int[] arr3 = SortUtils.generateNearlyOrderedArray(count, 100);
        // Make a copy of a random array
        int[] arr4 = SortUtils.copyArray(arr3);
        // Sort insert
        SortUtils.testSort("Insertion sort of relative order",new InsertSort(),arr3);
        // Make a quick sort
        SortUtils.testSort("Fast sorting of relative order",new QuickSort(),arr4);

    }
}
3.6 test analysis
  • Through the operation of the above test main program and test kit, we can see the following conclusions clearly:
    --When sorting large and disorderly arrays, the performance of fast sorting is better than insert sorting.
    --But even if the number is large, if the array is relatively ordered, the performance of insertion sorting is not worse than that of fast sorting.
    --We also find that when the number of sorting is the same, the more disorderly the array is, the better the performance of fast sorting is.

4, Write at the end

In daily learning, logical thinking is very important, especially in the process of data structure and algorithm learning, to establish the structural thinking of logic + routine, with structured thinking, can make the problem analysis more comprehensive and profound.

Tags: Java shell

Posted on Fri, 05 Jun 2020 22:47:00 -0700 by AliasXNeo