Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.1 kB
1
Indexable
Never
import random

# Generate a list filled with random numbers
def get_random_list(_list_size, _number_scale):
    randomlist = []
    for i in range(0,_list_size):
        randomlist.append(random.randint(1,_number_scale))
    return randomlist

def insertion_sort(_list):
    print("Begin the insertion sort:")
    for j in range(2,len(_list)):
        key=_list[j]
        # Insert A[j] into the sorted sequence A[1,...,j-1]
        i = j-1
        # Use while-loop taking the key to loop over the prior sorted subarray,
        # To see whether the key has room to swap to the ordered subarray.
        # 
        # _list[i]>key: Any elements in the sorted subarray should be larger than the key.
        while i>0 and _list[i]>key:
            # If that is the case, move that element to the right, and insert the key to the place.
            _list[i+1]=_list[i]
            i = i-1
            _list[i+1]=key
            print(_list)
    print("Insertion sort completed")
    return _list

obj = get_random_list(10,20)
print("Before insertion sort")
print(obj)
obj2 = insertion_sort(obj)
print(obj2)