Implementation of common sorting algorithm in python

 

Sorting algorithm is a basic algorithm in computer science, and it is widely used at the same time. python functions also have built-in sorting interfaces, such as the sorted function. In actual production, the sorting algorithm we use in different scenarios will be slightly different. The selection of sorting algorithm mainly considers the following factors:

  • Algorithm execution efficiency

  • Stability of sorting

  • Number of sorting elements

  • Overhead of recursive calls

Diagram of sorting algorithm:

Next, nine common sorting algorithms and python implementation are introduced.

 

Bubble sorting

Basic idea: compare from left to right. If the left element is larger than the right, exchange the positions of the two elements. In each round of sorting, the largest element in the sequence floats to the far right. In other words, at least one element is in the correct position in each round of sorting. In this way, the next cycle does not need to consider the ordered elements, and the number of inner cycles will be reduced by one each time.

python implementation:

def bubble_sort(a):    
  n, swap_size = len(a), 1    
  while swap_size > 0:        
        swap_size = 0        
        for i in range(n-1):            
            if a[i] > a[i+1]:                
               a[i],a[i+1] = a[i+1],a[i]               
               swap_size += 1        
         n-=1    
   return a

                                                                                           

Quick sort

Basic idea: an improvement of bubble sorting. The data to be sorted is divided into two independent parts by one sorting, and all the data in one part is smaller than that in the other part. Then quickly sort some of the data according to this method, which is a recursive call. Then quickly sort another part of the data according to this method, which is also a recursive call.

Quick sorting evaluation: the worst time complexity is O(n^2), which is a degraded situation. In most cases, as long as the appropriate partition element is selected, the time complexity is nlog(n). Quick sorting is usually faster than other O(nlogn) algorithms, which belongs to a fast unstable sorting algorithm.

python implementation:

def quick_sort(a, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(a)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        part_index = part(a, left, right)
        quick_sort(a, left, part_index-1)
        quick_sort(a, part_index+1, right)
    return a

def part(a, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if a[i] < a[pivot]:
            a[i],a[index] = a[index],a[i]
            index+=1
        i+=1
    a[pivot],a[index-1] = a[index-1],a[pivot]
    return index-1

                                         

Simple insert sort

Basic idea: take out the first element from the unordered table every time and insert it into the appropriate position of the ordered table to make the ordered table still orderly until all elements in the unordered table are inserted. The worst time complexity is O(n^2), which belongs to stable sorting algorithm and is efficient for processing small batch data.

python implementation:

def insertion_sort(a):
    for i in range(len(a)):
        pre_index = i-1
        current = a[i]
        while pre_index >= 0 and a[pre_index] > current:
            a[pre_index+1] = a[pre_index]
            pre_index-=1
        a[pre_index+1] = current
    return a

                                                           

Hill sort

Basic idea: first take a positive integer d1 and group it at intervals of d1. First, use the insertion sort operation for the elements in each group, and repeat the above grouping and direct insertion sort operation; Until di = 1, that is, all records are sorted in one group.

python implementation:

import math
def shell_sort(a):
    gl=1
    while (gl < len(a)/3):
        gl = gl*3+1
    while gl > 0:
        for i in range(gl,len(a)):
            temp = a[i]
            j = i-gl
            while j >=0 and a[j] > temp:
                a[j+gl]=a[j]
                j-=gl
            a[j+gl] = temp
        gl = math.floor(gl/3)
    return a

   

Simple selection sort

Basic idea: it is a process of directly selecting the most value from the unordered sequence to the sorted sequence. Each time, the smallest (largest) element is selected from the data elements to be sorted, and the order is placed at the top of the sequence to be sorted until all the data elements to be sorted are finished.

python implementation:

def selection_sort(a):
    for i in range(len(a) - 1):
        min_index = i
        for j in range(i + 1, len(a)):
            if a[j] < a[min_index]:
                min_index = j
        if i != min_index:
            a[i], a[min_index] = a[min_index], a[i]
    return a

 

Heap sort

Basic idea: a sort algorithm designed by using binary tree (heap) data structure is an improved algorithm for direct selection sort. The logical structure is based on the binary tree storage structure, which optimizes the performance of selective sorting. In physical storage, it is a continuous array storage, which uses the characteristics of the array to quickly locate the elements of the specified index.

python implementation:

import math

def heap_sort(a):
    al = len(a)

    def heapify(a, i):
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i
        if left < al and a[left] > a[largest]:
            largest = left
        if right < al and a[right] > a[largest]:
            largest = right

        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            heapify(a, largest)

    # Build pile
    for i in range(math.floor(len(a) / 2), -1, -1):
        heapify(a, i)

    # Constantly adjust the heap: root and last element
    for i in range(len(a) - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        al -= 1
        heapify(a, 0)
    return a

 

Merge sort

Basic idea: it is an effective sorting algorithm based on merging operation. The algorithm adopts a very typical application of Divide and Conquer. Merge the ordered subsequences to obtain a completely ordered sequence; That is, each subsequence is ordered first, and then the subsequence segments are ordered.

python implementation:

import math
def merge_sort(a):
    if(len(a)<2):
        return a
    middle = math.floor(len(a)/2)
    left, right = a[0:middle], a[middle:]
    return merge(merge_sort(left), merge_sort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

 

Cardinality sort

Basic idea: cut the integer into different numbers according to the number of digits, and then compare them according to each number of digits. It can only be expressed in integer or floating-point format, for example, it can only be expressed in integer or floating-point format.

python implementation:

import math
def radix_sort(a):
    i = 0 # The record is currently taking one position, and the lowest position is 1
    max_num = max(a)  # Maximum value
    j = len(str(max_num))  # Number of digits to record the maximum value
    while i < j:
        bucket_list =[[] for _ in range(10)] #Initialize bucket array
        for x in a:
            bucket_list[int(x / (10**i)) % 10].append(x) # Find the position and put it into the bucket array
        a.clear()
        for x in bucket_list:   # Put back the original sequence
            for y in x:
                a.append(y)
        i += 1
    return a

 

Bucket sorting

Basic idea: in order to save space and time, we need to specify the value of the smallest and largest number in the data to be sorted. Divide the array into a limited number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or continue to use bucket sorting recursively).

python implementation:

def bucket_sort(a):
    all_list = [0 for i in range(100)]  # Array set to all 0
    last_list = []
    for v in a:
        all_list[v] = 1 if all_list[v]==0 else all_list[v]+1
    for i,t_v in enumerate(all_list):
        if t_v != 0:
            for j in range(t_v):
                 last_list.append(i)
    return last_list

Finally, call the above methods in sequence:

sort_funs = [bubble_sort,quick_sort,insertion_sort,shell_sort,selection_sort,heap_sort,merge_sort,radix_sort,bucket_sort]
a = [10, 7, 11, 7, 18, 17, 9, 17, 0, 7, 3, 20, 20, 15]
for fun in sort_funs:
    a_sorted = fun(a)
    print(a_sorted)

The output results are consistent (non descending sequence):

[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]
[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]
[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]
[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]
[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]
[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]
[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]
[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]
[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]

Summary:

Tags: Algorithm data structure

Posted by jamesp on Wed, 11 May 2022 22:16:52 +0300