This article is participating in Python Theme Month. See the link for details

Sorting algorithm

Hill sorting

Shell Sort is a type of insertion Sort. Also known as reduced incremental sort, it is a more efficient and improved version of the direct insert sort algorithm. Hill sort is an unstable sort algorithm. This method gets its name from the fact that DL. Shell proposed it in 1959. Hill sort is to group the records by a certain increment of the index and sort each group by direct insertion sort algorithm. As the increments decrease, each group contains more and more keywords, and when the increments decrease to 1, the entire file is exactly grouped and the algorithm terminates.

Hill sorting process

The basic idea of Hill sort is to place array columns in a table and insert sort the columns separately, repeating the process with longer columns (with longer steps and fewer columns) each time. You end up with just one column. The reason for converting an array to a table is to better understand the algorithm, which itself uses arrays for sorting.

Suppose the list is [54, 26, 93, 17, 77, 31, 44, 55, 20]

When gap equals 4, the whole list is sorted

When gap equals 2, the whole list is sorted

When gap equals 1, the whole list is in insertion sort

Hill sort does not order some elements with each trip, but makes the whole data closer and closer to being ordered, and the last trip makes all the data in order

Hill sort code implementation

Def shell_sort(li): n = len(li) gap = n // 2 while gap > 0: i = j while i > 0: if li[i] < li[i-gap]: li[i], li[i-gap] = li[i-gap], li[i] i -= gap else: Gap = gap // 2Copy the code

Quick sort

Quicksort (English: Quicksort, also known as partition-exchange sort, divides the sorted data into two separate parts with all the data in one part smaller than all the data in the other part, and then Quicksort the two parts separately. The whole sorting process can be done recursively, so that the whole data becomes an ordered sequence.

Steps as follows:

  • If you want the two halves to have the same number of items, you should find the table’s “median.” But finding the median requires computing overhead. To have no overhead, you can only find any number that acts as the “median,” such as the first number
  • Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition ends, the benchmark is in the middle of the array. This is called a partition operation. By setting the left and right Pointers, the left pointer moves to the right and the right pointer moves to the left
  • Recursively sorts subsequences of elements less than a reference and subsequences of elements greater than a reference.

The bottom case of recursion is if the sequence is of size zero or one, so it’s always sorted. The algorithm always ends up recursively, because in each iteration it puts at least one element in its final position.

Analysis of quicksort

The initial state

Move elements with two Pointers, Low and hight

Quick sort code implementation

Def quick_sort(li, start, end): """ "" Mid = li[start] # low low = start # 0 # high High = end # While low < high and li[high] >= mid: len(li)-1 while low < high: Li [low] = li[high] # if low and high do not overlap, low is smaller than the base element, While low < high and li[low] < mid: Li [high] = li[low] # [20, 26, 44, 17, 31, 54, 77, 55, 93] Li [low] = mid # Quick_sort (li, start, li) Quick_sort (li, low + 1, end)Copy the code

Merge sort

Merge sort is a very typical application of divide-and-conquer. The idea of merge sort is to recursively decompose arrays and then merge arrays.

After the array is decomposed to a minimum, and then merge two ordered arrays, the basic idea is to compare the first number of the two arrays, which is the smallest one is taken first, after taking the corresponding pointer to move back one. Then compare until one array is empty, and then copy the rest of the other array.

Merge sort analysis

Split the list to a point where the list cannot be split again

In the process of merging

The implementation of merge sort

Def merge_sort(li): if len(li) <= 1: // 2 left = merge_sort(li[:mid_index]) right = merge_sort(li[:mid_index :]) # To combine two ordered subsequences into a new whole: L_index, r_index = 0, 0 result = [] while l_index < len(left) and r_index < len(right): if left[l_index] < right[r_index]: result.append(left[l_index]) l_index += 1 else: Result += left[l_index:] result += right[r_index:] result += left[l_index:] result += right[r_index:] return resultCopy the code