# Sorting algorithm -- hill and fast sorting

### 1. Hill sorting

#### 1.1 problems in simple insertion sorting

Let's look at the possible problems with simple insertion sorting
Array arr = {2,3,4,5,6,1} at this time, the number 1 to be inserted (minimum) is as follows:
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
Conclusion: when the number to be inserted is small, the number of backward shifts increases obviously, which has an effect on the efficiency

#### 1.2 introduction to Hill sorting

Hill sorting is a sort algorithm put forward by Donald Shell in 1959. Hill sort is also a sort of insertion sort, which is a more efficient version of simple insertion sort after improvement, also known as reduced incremental sort.

#### 1.3 basic idea of Hill's sorting method

Hill sorting is to group records by a certain increment of subscript, and use the direct insertion sorting algorithm to sort each group. As the increment gradually decreases, each group contains more and more keywords. When the increment is reduced to 1, the whole file is just divided into a group, and the algorithm is terminated.

#### 1.5 the displacement Fisher sorting code is implemented as follows:

```public static void shellSort(int[] arr){
//Increment gap, and gradually reduce the increment
for(int gap = arr.length/2; gap > 0 ; gap /= 2){
//From the gap element, insert and sort the groups one by one
for(int i = gap; i < arr.length; i++){
int j = i;
int temp = arr[j];
//if(arr[j] < arr[j -gap]){
while(j -gap >= 0 && temp < arr[j - gap]){
//move
arr[j] = arr[j - gap];
j -= gap;
}
//When you exit while, you find the insertion position for arr[j]
arr[j] = temp;
//}
}
}
}
```

#### Performance test of displacement Fisher sorting

```public static void main(String[] args) {
// TODO Auto-generated method stub

//int[] arr = {8,9,1,7,2,3,5,4,6,0};
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 80000);// Generate a number between [080000]
}
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(date1);
//System.out.println("array before sorting is" + Arrays.toString(arr));
System.out.println("The time before sorting is:" + date1Str);
shellSort(arr);//Displacement method
//	System.out.println("sorted array is" + Arrays.toString(arr));
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("The time after sorting is:"+date2Str);
}
```

The test results are as follows:

#### 2. Quick sorting

##### 2.1 introduction to quick sorting method

Quicksort is an improvement of bubble sort. The basic idea is: divide the data to be sorted into two independent parts by a single sorting, all the data in one part is smaller than all the data in the other part, and then sort the two parts of data rapidly according to this method. The whole sorting process can be carried out recursively, so as to make the whole data into an ordered sequence.

#### 3.3 code implementation of fast sorting

```public static void quickSort(int[] arr,int left,int right){
int l = left;//Left subscript
int r = right;//Right subscript
int pivot =  arr[(left + right) / 2];
int temp = 0; //Temporary variable
//The purpose of the while loop is to place values smaller than pivot on the left and values larger than pivot on the right
while(l < r){
//Find a value greater than or equal to pivot on the left side of pivot before exiting
while(arr[l] < pivot){
l += 1;
}
//Find all the way to the right of pivot, find the value less than or equal to pivot, and then exit
while(arr[r] > pivot){
r -= 1;
}
//If l > = R, it means that the left and right values of pivot are all values less than or equal to pivot according to the left, and the right values are all values greater than or equal to pivot
if(l >= r){
break;
}
//exchange
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//If the arr[l] == pivot value r moves forward after the exchange
if(arr[l] == pivot){
r -= 1;
}
//After the exchange, it is found that the arr[r] == pivot value moves backward in l + +
if(arr[r] == pivot){
l += 1;
}
}
//If l ==r, l++,r -- is required, otherwise stack overflow occurs
if(l == r){
l += 1;
r -= 1;
}
//Left recursion
if(left < r){
quickSort(arr, left, r);
}
//Recursion to the right
if(right > l){
quickSort(arr,l,right);
}

}
```

#### 3.4 performance test of quick sorting:

```public static void main(String[] args) {
// TODO Auto-generated method stub

// int[] arr = {-9,78,23,-567,70,0,-1};
int[] arr = new int[80000];
for(int i = 0 ; i < 80000; i++){
arr[i] = (int)(Math.random() * 80000);//Generate a number between [0800000]
}
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(date1);
System.out.println("The time before sorting is:"+date1Str);
quickSort(arr, 0, arr.length - 1);
//System.out.println("arr="+Arrays.toString(arr));
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("The time after sorting is:"+date2Str);
}
```

The test results are as follows:

Published 31 original articles, won praise 17, visited 1939

Keywords: less shell

Added by acirilo on Fri, 21 Feb 2020 08:08:54 +0200