Sorting and Efficiency

Sorting and Efficiency

There are various algorithms for sorting. Examples include bubble sort, insertion sort, quicksort, and mergesort. Some are more efficient and some are less. They also perform better or worse depending on the data array presented to them.

Bubble sort:

BEST: O(n)

NORMAL: O(n^2)

WORST: O(n^2)

def bubble_sort(L):

    length = len(L) - 1

    sorted = False

    while not sorted:

        sorted = True

        for i in range(length):

            if L[i] > L[i+1]:

                sorted = False

                L[i], L[i+1] = L[i+1], L[i]

    return L

Insertion sort:

BEST: O(n)
NORMAL: O(n^2)

WORST: O(n^2)

def insertion_sort(L):

    for i in range(1, len(L)):

        tmp = L[i]

        k = i

        while k > 0 and tmp < L[k - 1]:

            L[k] = L[k - 1]

            k -= 1

            L[k] = tmp

    return L

Quicksort:

 BEST: O(n log(n))

NORMAL: O(n log(n))

WORST: O(n^2)

def quick(L):
    if len(L) > 1:
        pivot = L[0] # there are much better ways of choosing the pivot!
        smaller_than_pivot = [x for x in L[1:] if x < pivot]
        larger_than_pivot = [x for x in L[1:] if x >= pivot]
        return quick(smaller_than_pivot) + [pivot] + quick(larger_than_pivot)
    else:
        return L

Mergesort:

BEST: O(n log(n))

NORMAL: O(n log(n))

WORST: O(n log(n))

def merge(L1:list, L2:list) -> 

    decreasing_from_largest = []
    while L1 and L2:
        if L1[-1] > L2[-1]:
            decreasing_from_largest.append(L1.pop())
        else:
            decreasing_from_largest.append(L2.pop())
    decreasing_from_largest.reverse() 
    return L1 + L2 + decreasing_from_largest

def merge_sort(L):

    if len(L) < 2 :
        return L
    else :
        left_sublist = L[:len(L)//2]
        right_sublist = L[len(L)//2:]
        return merge2(merge_sort(left_sublist), 
                      merge_sort(right_sublist))

I think it's very interesting to learn how to make sorting algorithms more and more efficient, depending on the array size. I interesting how the big O of an algorithm only depends on the highest order of the function.