Hill sort of insertion sort (Java)

Posted Jun 27, 20203 min read

Hill sort of insertion sort(Java)

Blog description

The information involved in the article comes from the Internet collation and personal summary, which means personal learning and experience summary. If there is any infringement, please contact me to delete, thank you!

Introduction to Hill Sorting

Hill sorting is a sorting algorithm proposed by Hill(Donald Shell) in 1959. Hill sorting is also an insertion sort. It is a more efficient version of simple insertion sorting, which is also called reduced incremental sorting.

Basic Ideas of Hill Sorting

Hill sorting is to group records by a certain increment of the index, and use the direct insertion sort algorithm to sort each group; as the increment gradually decreases, each group contains more and more keywords. When the increment decreases to 1, The entire file is just divided into a group, the algorithm is terminated

Code(Exchangeable)

package cn.guizimo.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[]args) {
        int[]arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("Before sorting");
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
        System.out.println("After sorting");
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[]arr) {
        int count = 0;
        for(int gap = arr.length/2; gap> 0; gap /= 2) {
            count++;
            int temp = 0;
            for(int i = gap; i <arr.length; i++) {
                for(int j = i-gap; j >= 0; j -= gap) {
                    if(arr[j]> arr[j + gap]) {
                        temp = arr[j];
                        arr[j]= arr[j + gap];
                        arr[j + gap]= temp;
                    }
                }
            }
            System.out.println("No."+count+"round order");
            System.out.println(Arrays.toString(arr));
        }

    }
}
Test

image-20200627112239838

Test speed

package cn.guizimo.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[]args) {
        int max = 80000;
        int[]arr = new int[max];
        for(int i = 0; i <max; i++) {
            arr[i]=(int)(Math.random() * 8000000);
        }
        long date1 = System.currentTimeMillis();
        shellSort(arr);
        long date2 = System.currentTimeMillis();
        System.out.println("Exchange Hill Sort" +max+" array time is:"+(date2-date1));
    }

    public static void shellSort(int[]arr) {
        for(int gap = arr.length/2; gap> 0; gap /= 2) {
            int temp = 0;
            for(int i = gap; i <arr.length; i++) {
                for(int j = i-gap; j >= 0; j -= gap) {
                    if(arr[j]> arr[j + gap]) {
                        temp = arr[j];
                        arr[j]= arr[j + gap];
                        arr[j + gap]= temp;
                    }
                }
            }
        }

    }
}

image-20200627112432454

Code(displacement type)

package cn.guizimo.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[]args) {
        int[]arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("Before sorting");
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
        System.out.println("After sorting");
        System.out.println(Arrays.toString(arr));
    }


    public static void shellSort(int[]arr) {
        int count = 0;
        for(int gap = arr.length/2; gap> 0; gap /= 2) {
            count++;
            for(int i = gap; i <arr.length; i++) {
                int j = i;
                int temp = arr[i];
                if(arr[j]<arr[j-gap]){
                    while(j-gap >= 0 && temp <arr[j-gap]){
                        arr[j]= arr[j-gap];
                        j -= gap;
                    }
                    arr[j]= temp;
                }
            }
            System.out.println("No."+count+"round order");
            System.out.println(Arrays.toString(arr));
        }

    }
}
Test

image-20200627113534689

Speed test

package cn.guizimo.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[]args) {
        int max = 80000;
        int[]arr = new int[max];
        for(int i = 0; i <max; i++) {
            arr[i]=(int)(Math.random() * 8000000);
        }
        long date1 = System.currentTimeMillis();
        shellSort(arr);
        long date2 = System.currentTimeMillis();
        System.out.println("Displacement Hill Sort" +max+" array time is:"+(date2-date1));

    }

    public static void shellSort(int[]arr) {
        for(int gap = arr.length/2; gap> 0; gap /= 2) {
            for(int i = gap; i <arr.length; i++) {
                int j = i;
                int temp = arr[i];
                if(arr[j]<arr[j-gap]){
                    while(j-gap >= 0 && temp <arr[j-gap]){
                        arr[j]= arr[j-gap];
                        j -= gap;
                    }
                    arr[j]= temp;
                }
            }
        }
    }
}

image-20200627113830366

thank

Shang Silicon Valley

Universal Network

And hardworking self