Ten classical sorting algorithms implemented by python

Ten classic sorting algorithms implemented in Python

The full version will be provided at the end of the code, or you can My Github fork, if you want to see the moving picture, you can go Here Have a look;

Summary:

  1. Operation mode: copy the last code and run it directly in python sort.py;
  2. The robustness of the code is not handled too much, and the students who use it directly need to check it;
  3. For Hill sorting, the choice of gap is very important, which needs to be changed according to the actual situation;
  4. In my test, because the array to be sorted is very small, the length is only 10, and the maximum value is 10, so the count sorting is the fastest, which is often not the case in reality;
  5. Heap sorting didn't happen. Yes, it was lazy;
  6. The key is to understand the idea of the algorithm, as for the realization, it is only to land the idea in a reasonable way;
  7. It's recommended that you go to the link above to see the dynamic diagram. It's really better to understand, but it's also good to read the code, isn't it;
  8. Divide and conquer method is used a lot. In fact, I don't know what the mathematical principle behind it is, and why divide and conquer method can reduce the time complexity. One of my classmates told me in the trouble comment area. Thanks a lot;

Operation diagram

Because the array is small and the range is between 1 and 10, it is actually more friendly for the non comparison algorithm of counting and sorting, because there is not much space pressure, so it is easy to understand the speed of counting and sorting first, and the main reason why the selection and insertion is faster than Hill merging is that the problem scale itself is too small, and my implementation of divide and conquer method is based on recursion, so We can't see the advantages of divide and conquer. In fact, if we sort large arrays, this difference will be reflected;

Complete code

It can be seen that the total code excluding the test code is only 170 lines, including blank lines and function names, etc., so the algorithm implementation is very simple, we still need to pay attention to the idea;

import sys,random,time

def bubble(list_):
    running = True
    while running:
        have_change = False
        for i in range(len(list_)-1):
            if list_[i]>list_[i+1]:
                list_[i],list_[i+1] = list_[i+1],list_[i]
                have_change = True
        if not have_change:
            break
    return list_

def select(list_):
    for i in range(len(list_)-1):
        min_idx = i
        for j in range(i,len(list_)):
            if list_[min_idx]>list_[j]:
                min_idx = j
        list_[i],list_[min_idx] = list_[min_idx],list_[i]
    return list_

def insert(list_):
    for i in range(1,len(list_)):
        idx = i
        for j in range(i):
            if list_[j]>list_[idx]:
                idx = j
                break
        if idx != i:
            tmp = list_[i]
            list_[idx+1:i+1] = list_[idx:i]
            list_[idx] = tmp
    return list_

def shell(list_,gap=None):
    '''
    gap It is a difficult problem that the choice of hill has a great influence on the result len/2
    //This gap is actually a gap, that is, how many elements are separated in a group
    //For example, for [1,2,3,4,5,6,7,8,9,10]
    //When gap is len/2, i.e. 5, each group of elements is composed of five elements separated, i.e. 1 and 6, 2 and 7, 3 and 8, etc
    '''
    len_ = len(list_)
    gap = int(len_/2) if not gap else gap
    while gap >= 1:
        for i in range(gap):
            list_[i:len_:gap] = insert(list_[i:len_:gap])
        gap = int(gap/2)
    return list_

def merge(list_):
    '''
    //Recursive implementation of merge sort
    //Idea: divide the data into two groups. Sort the two groups into one group with four elements,
    //Until it goes back to the whole sequence, it is actually composed of two ordered subsequences, a typical recursive problem
    '''
    if len(list_)<=1:
        return list_
    if len(list_)==2:
        return list_ if list_[0]<=list_[1] else list_[::-1]
    len_ = len(list_)
    left = merge(list_[:int(len_/2)])
    right = merge(list_[int(len_/2):])
    tmp = []
    left_idx,right_idx = 0,0
    while len(tmp)<len(list_):
        if left[left_idx]<=right[right_idx]:
            tmp.append(left[left_idx])
            left_idx+=1
            if left_idx==len(left):
                tmp += right[right_idx:]
                break
        else:
            tmp.append(right[right_idx])
            right_idx+=1
            if right_idx==len(right):
                tmp += left[left_idx:]
                break
    return tmp

def quick(list_):
    '''
    //Quick sorting: Based on the divide and conquer method, select an element as the benchmark, place the remaining elements to the left and right of the benchmark, and recurse this process
    '''
    if len(list_)<=1:
        return list_
    if len(list_)==2:
        return list_ if list_[0]<=list_[1] else list_[::-1]
    base_idx = int(len(list_)/2)
    base = list_[base_idx]
    left = []
    right = []
    for i in range(len(list_)):
        if i != base_idx:
            if list_[i] <= base:
                left.append(list_[i])
            else:
                right.append(list_[i])
    return quick(left)+[base]+quick(right)

def count(list_):
    '''
    //All elements are integral
    '''
    min_,max_ = list_[0],list_[0]
    for i in range(1,len(list_)):
        if list_[i]<min_:
            min_ = list_[i]
        if list_[i]>max_:
            max_ = list_[i]
    count_list = [0]*(max_-min_+1)
    for item in list_:
        count_list[item-min_] += 1

    list_ = []
    for i in range(len(count_list)):
        for j in range(count_list[i]):
            list_.append(i+min_)
    return list_

def heap(list_):
    '''

    '''
    pass

def bucket(list_):
    '''
    //Each bucket is sorted by selection. The bucket is divided by the maximum value divided by 5, that is, it is divided into 5 buckets
    //The speed at which buckets are sorted depends on how they are divided
    '''
    bucket = [[],[],[],[],[]] # Note the length is 5
    max_ = list_[0]
    for item in list_[1:]:
        if item > max_:
            max_ = item
    gap = max_/5 # Corresponding bucket length
    for item in list_:
        bucket[int((item-1)/gap)].append(item)
    for i in range(len(bucket)):
        bucket[i] = select(bucket[i])
    list_ = []
    for item in bucket:
        list_ += item
    return list_

def radix(list_):
    '''
    //Cardinality sorting: sort the different digits of a value respectively, such as starting from a single digit, then tens, hundreds, and so on;
    //Note that the code here assumes that the values to be sorted are all integers
    '''
    max_ = list_[0]
    for item in list_[1:]:
        if item > max_:
            max_ = item
    max_radix = len(str(max_))
    radix_list = [[],[],[],[],[],[],[],[],[],[]] # Corresponding to 9 possible numbers on each bit
    cur_radix = 0 
    while cur_radix<max_radix:
        base = 10**cur_radix
        for item in list_:
            radix_list[int(item/base)%10].append(item)
        list_ = []
        for item in radix_list:
            list_ += item

        radix_list = [[],[],[],[],[],[],[],[],[]] # Corresponding to 9 possible numbers on each bit
        cur_radix += 1
    return list_


def test(name,sort_func,times,info,idea,*param):
    list_ = [1,2,3,4,5,6,7,8,9,10]
    print(name+' Sort:')
    print('\t'+info)
    print('\t'+idea)
    print('\tTimes: '+str(times))
    start_time = time.time()
    for i in range(times):
        random.shuffle(list_)
        #print('\tInput: '+str(list_))
        list_ = sort_func(list_) if len(param)<=0 else sort_func(list_,param[0])
        #print('\tOutput: '+str(list_))
    #print('\t'+str(list_))
    print('\tCost time: '+str(time.time()-start_time))


if __name__ == "__main__":
    test('Bubble',bubble,100000,'O(n^2), O(1), Stable, Comparison sort','thinking: Loop back and forth until there are no two elements that need to be swapped')
    test('Select',select,100000,'O(n^2), O(1), Instable, Comparison sort','thinking: Place the smallest number in the subsequent sequence in the current position from beginning to end')
    test('Insert',insert,100000,'O(n^2), O(1), Stable, Comparison sort','thinking: Insert each element from the beginning to the end into the appropriate position in the previous sorted sequence, after which the elements move backward')
    test('Shell(gap=len/2)',shell,100000,'O(nlogn), O(1), Instable, Comparison sort','thinking: Sequence according to gap Group, and continue to subdivide until only 1. Each group uses direct insertion sorting, which means a little bit of divide and conquer, gap The choice of is a problem, usually default to len/2')
    test('Shell(gap=3)',shell,100000,'O(nlogn), O(1), Instable, Comparison sort','thinking: Sequence according to gap Group and subdivide until there is only 1, gap The choice of is a problem, usually default to len/2',3)
    test('Shell(gap=2)',shell,100000,'O(nlogn), O(1), Instable, Comparison sort','thinking: Sequence according to gap Group, and continue to subdivide until only 1. Each group uses direct insertion sorting, which means a little bit of divide and conquer, gap The choice of is a problem, usually default to len/2',2)
    test('Merge',merge,100000,'O(nlogn), O(n), Stable, Comparison sort','thinking: Merge operation based on divide and conquer method. Since it is divide and conquer method, recursive solution is the simplest implementation')
    test('Quick',quick,100000,'O(nlogn), O(logn), Instable, Comparison sort','thinking: Also based on the divide and conquer method, by specifying an element as the benchmark, the less than benchmark is placed on the left sequence, the greater one is placed on the right sequence, and the recursive one is placed on the left sequence')
    # test('Heap',heap,100000,'O(nlogn), O(1), unstable, comparative sorting ','idea: building a complete binary tree by using the nature of heap')
    test('Count',count,100000,'O(n+k), O(k), Stable, Non comparison sort','thinking: The construction array is used to store the number of elements in the array to be sorted, and the element value is used as the subscript of the new array')
    test('Bucket',bucket,100000,'O(n+k), O(n+k), Stable, Non comparison sort','thinking: Map elements to N Of the buckets, after sorting each bucket, read out the elements in each bucket in turn')
    test('Radix',radix,100000,'O(n*k), O(n+k), Stable, Non comparison sort','thinking: Sort one bit of each element in turn until the highest bit')

    # print(heap([4,6,8,3,5,10,9,2,1,7]))

Last

You can go to Github to see if there is anything else you need. At present, it's mainly machine learning projects, Python scripting tools, interesting small projects, Follow's big guy, Fork's projects, etc
https://github.com/NemoHoHaloAi

Tags: shell Python github less

Posted on Sun, 05 Apr 2020 22:02:46 -0700 by hwmetzger