current position:Home>Python implements Hill sorting (reduced incremental sorting) algorithm

Python implements Hill sorting (reduced incremental sorting) algorithm

2022-09-09 06:49:01Fairies don't make trouble

Concept

Hill sorting, also known as shrinking incremental sorting, is a kind of insertion sorting, which is an improvement on the direct insertion sorting algorithm.It is performed by comparing elements at a certain interval. First, the entire record sequence to be sorted is divided into several sub-sequences for direct insertion sorting, and when the records in the entire sequence are "basically ordered", the entire record sequence is directly sequenced.Insertion sort until the last pass that compares only adjacent elements.

Applicable Instructions

Hill sort time complexity is O(n^{(1.3-2)}) , the space complexity is of constant order O(1).Hill sort is not as fast as O(n(logn))The sorting algorithm is fast, so it performs well for medium-sized scales, but it is not optimal for sorting very large-scale data, in general O(n^2) The algorithm of complexity is much faster.

Process Diagram

The purpose of Hill sort is to improve insertion sort in order to speed up, swap non-adjacent elements to sort parts of the array, and finally use insertion sort to sort the partially sorted array.Here we select the increment gap=length/2, reduce the increment to gap = gap/2 , use the sequence {n/2,(n/2)/2...1} to represent.

First pass, initial increment gap = length/2 = 4

Second pass, increment reduced to 2

The third pass, the increment is reduced to 1, and the final sorting result is obtained

Algorithm Analysis

Time complexity

When it is sequential at the beginning, the efficiency is the highest and the time complexity is the best, which is O(nlog2n) ; When the sequence is reversed at the beginning, the efficiency is the lowest and the time complexity is the worst, which is O(n^2).The time complexity of Hill sorting depends on the selection of increments. With different sequences, the time complexity may be different. The average time complexity of faster sorting is O(n^{1.3}).

Space Complexity

The space complexity is the memory space occupied by the temporary variable when exchanging elements, so the space complexity is O(1).

Stability

Hill sorting requires multiple insertion sorting. During different insertion sorting processes, the same elements may move in their respective insertion sorting, and finally their stability will be disrupted, so Hill sorting is unstable..

Example code

def shellSort(arr):n = len(arr)gap = int(n/2)while gap > 0:for i in range(gap,n):temp = arr[i]j = iwhile j >= gap and arr[j-gap] >temp:arr[j] = arr[j-gap]j -= gaparr[j] = tempgap = int(gap/2)arr = [ 12, 34, 54, 2, 3]n = len(arr)print("Before sorting:")for i in range(n):print(arr[i])shellSort(arr)print ("\nAfter sorting:")for i in range(n):print(arr[i])

copyright notice
author[Fairies don't make trouble],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/252/202209090633309881.html

Random recommended