“This is the 17th day of my participation in the August More Text Challenge.

A sorting algorithm auxiliary method code example

public class SortUtil {
    // Compare elements
    public static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    // Swap elements
    public static void exch(Comparable[] arr, int i, int j) {
        Comparable t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Display the array
    public static void show(Comparable[] arr) {
        for (Comparable comparable : arr) {
            System.out.println(comparable + ""); }}// Check whether the array is in order
    public static boolean isSorted(Comparable[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (less(arr[i], arr[i - 1]) {return false; }}return true; }}Copy the code

Second, select the sorting algorithm

(1) the concept of selection sorting algorithm

Selective sorting is repeatedly “looking for the minimum from the data to be sorted and swapping it with the leftmost number in the sequence.” The algorithm for this operation. Linear lookup is used to find the minimum value in the sequence.

The inner loop knowledge of selecting sort then compares the current element to the smallest known element (as well as incrementing the current index and checking if the code is out of bounds). The code that swaps elements is written outside the inner loop, and each swap can schedule one element, so the total number of swaps is N.

So the time efficiency of the algorithm depends on the number of comparisons.

Selection sort has two distinct features:

1. Running time is independent of input. Scanning an array to find the smallest element does not provide scan information for the next scan. This property is a disadvantage in some cases, because a user of selective sort might be surprised to find that an already ordered array or an array with all equal primary keys takes just as long to sort as an array with randomly arranged elements. Other algorithms are better at exploiting the initial state of the input.

2. Data movement is minimal. Each swap changes the values of two array elements, so the selection sort takes N swaps — the number of swaps is linear with the size of the array. (Most of the other increases are linear logarithms or squares.)

(two), the selection of sorting algorithm flow chart

This flow chart is from my First Algorithm book.

(three), the selection of sorting algorithm code example

public class Selection {

    public static void sort(Comparable[] arr) {
        // Array length
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // Index of the smallest element
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if(SortUtil.less(arr[j], arr[min])) { min = j; } SortUtil.exch(arr, i, min); }}}}Copy the code

(4) Select test cases of sorting algorithm

public class SelectionTest {

    public static void main(String[] args) {
        // Empty array test
        emptyTest();
        // Unordered array test
        disorderTest();
        // Ordered array test
        orderTest();
    }

    / / an empty array
    private static void emptyTest(a) {
        String[] arr = new String[0];
        Selection.sort(arr);
    }

    // Unordered array
    private static void disorderTest(a) {
        String[] arr = new String[]{
                "S"."O"."R"."T"."E"."X"."A"."M"."P"."L"."E"
        };
        Selection.sort(arr);
    }

    // Ordered array
    private static void orderTest(a) {
        String[] arr = new String[]{
                "A"."B"."C"."D"."E"."F"."G"."H"."I"."J"."K"}; Selection.sort(arr); }}Copy the code

(5) The basic properties of the selection sorting algorithm

For an array of length N, selection sort requires approximately N^2/2 comparisons and N swaps in the N by N table below to represent the sort track, where each non-gray character represents a comparison. About half of the elements in the table are not gray — that is, the diagonal and the elements above it. Each element on the diagonal corresponds to an exchange. From the above code, we can see that any I of 0 — n-1 is swapped once and compared n-1-i, so there are N swaps and (n-1) + (n-1) +… +2+1~N^2 times.

The picture is quoted from Algorithm (4th edition)

Insert sort algorithm

(1) The concept of insertion sort algorithm

Insertion sort is an algorithm that sorts data sequentially from the left end of a sequence. In the sorting process, the data on the left side is continuously resorted, while the data on the right side is left unsorted. The idea of insert sort is to take a piece of data from the unsorted region on the right and insert it into the appropriate position in the sorted region.

As with selection sort, all elements to the left of the current index are ordered, but their final position is uncertain and they may be moved to make room for smaller elements. But when the index reaches the right end of the array, array sorting is done.

Unlike selection sort, the time required for insertion sort depends on the initial order of the elements in the input. For example, sorting a large array whose elements are already ordered (or nearly ordered) will be much faster than sorting a randomly ordered or reversed array.

(2) Insert the flow chart of sorting algorithm

This flow chart is from my First Algorithm book.

(three), insert sort algorithm code example

public class Insertion {

    public static void sort(Comparable[] arr) {
        // Arrange arr[] in ascending order
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            // Insert arr[I] into arr[i-1], arr[i-2], arr[i-3]... Among the
            for (int j = i; j > 0 && SortUtil.less(arr[j], arr[j - 1]); j--) {
                SortUtil.exch(arr, j, j - 1); }}}}Copy the code

(4) Test case of insertion sort algorithm

public class InsertionTest {

    public static void main(String[] args) {
        // Empty array test
        emptyTest();
        // Unordered array test
        disorderTest();
        // Ordered array test
        orderTest();
        // Partially ordered array test
        partiallyOrderedTest();
    }

    / / an empty array
    private static void emptyTest(a) {
        String[] arr = new String[0];
        Insertion.sort(arr);
    }

    // Unordered array
    private static void disorderTest(a) {
        String[] arr = new String[]{
                "S"."O"."R"."T"."E"."X"."A"."M"."P"."L"."E"
        };
        Insertion.sort(arr);
    }

    // Ordered array
    private static void orderTest(a) {
        String[] arr = new String[]{
                "A"."B"."C"."D"."E"."F"."G"."H"."I"."J"."K"
        };
        Insertion.sort(arr);
    }

    // Partially ordered array
    private static void partiallyOrderedTest(a){
        String[] arr = new String[]{
                "E"."X"."A"."M"."P"."L"."E"}; Insertion.sort(arr); }}Copy the code

(5) Basic properties of insertion sort algorithm

1. Analysis of randomly sorted arrays

For randomly arranged arrays of length N with non-repeating primary keys, insertion sort on average requires N^2/4 comparisons and N^2/4 swaps. The worst case requires N^2 over 2 comparisons and N^2 over 2 swaps, and the best case requires N minus 1 comparisons and 0 swaps.

The number of swaps and comparisons can be easily found in the N by N trace table below. At worst everything below the diagonal needs to be moved, at best nothing at all. For a randomly arranged array, on average each element can be moved back half the length of the array, so the total number of swaps is half the number of elements below the diagonal.

The total number of comparisons is the number of swaps plus an extra term, which is N minus the number of times that the element being inserted is exactly the smallest known element. In the worst case (reverse array). This term is negligible for the total, and in the best case (the array is already ordered) this term is equal to N minus 1.

The picture is quoted from Algorithm (4th edition)

2. Partially ordered arrays

(1) A typical partially ordered array

1. Each element in the array is not far from its final position.

2. An ordered array of large numbers followed by a small array.

Only a few elements in the array are in the wrong position.

(2) Analysis of partially ordered arrays

Insert sort requires the same number of swaps as the number of inversions in the array, and the number of comparisons required is greater than or equal to the number of inversions, and less than or equal to the number of inversions plus the size of the array minus one. Each swap changes the position of the two inverted elements, reducing a pair of inversions, and when the number of inversions reaches zero, the sorting is complete. Each swap corresponds to a comparison, and each I between 1 and n-1 may require an additional comparison (if a[I] does not reach the left end of the array)

Hill sorting algorithm

(1) The concept of Hill sorting algorithm

Hill sort: A quicksort algorithm based on insertion sort. Insertion sort is slow for large arrays of random numbers because it swaps only adjacent elements, so elements can only be moved from one section of the array to the other, bit by bit. For example, if the element with the smallest primary key is right at the end of the array, it takes n-1 moves to move it to the correct position. Hill sort simply improves insertion sort to speed things up, swapping non-contiguous elements to sort parts of the array, and eventually using insertion sort to conduct an ordered array sort.

​

(2) code examples of Hill sorting algorithm

public class Shell {

    public static void sort(Comparable[] arr) {
        // Arrange a[] in ascending order
        int n = arr.length;
        int h = 1;
        while (h < n / 3) {
            h = 3 * h + 1;
        }
        while (h >= 1) {
            for (int i = h; i < n; i++) {
                // Insert a[I] into a[i-h],a[i-2*h],a[i-3*h]... Among the
                for (int j = i; j >= h && SortUtil.less(arr[j], arr[j - h]); j -= h) {
                    SortUtil.exch(arr, j, j - h);
                }
            }
            h = h / 3; }}}Copy the code

(3) Test cases of Hill sorting algorithm

public class ShellTest {

    public static void main(String[] args) {
        // Empty array test
        emptyTest();
        // Non-empty array test
        test();
    }

    / / an empty array
    private static void emptyTest(a) {
        String[] arr = new String[0];
        Shell.sort(arr);
    }

    // A non-empty array
    private static void test(a) {
        String[] arr = new String[]{
                "S"."H"."E"."L"."L"."S"."O"."R"."T"."E"."X"."A"."M"."P"."L"."E"}; Selection.sort(arr); }}Copy the code

(4) The basic properties of Hill sorting algorithm

Using increasing sequences 1,4,13,40,121,364… The number of comparisons required for hill sort of is no more than a number of times N times the length of the increasing sequence.