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.

Recursion

Iteration vs Recursion 

An iteration looks like this:

def interation(a):

    b = 1

    for i in range(a):

        b = b * (i+1)

    return b

Essentially the code iterates over the same set of instructions and returns the final result. Here is what it looks like:

>>> iteration(5)
i b * (i + 1) b 0 1 * (0 + 1) 1 1 1 * (1 + 1) 2 2 2 * (2 + 1) 6 3 6 * (3 + 1) 24 4 24 * (4 + 1) 120

A recursion looks like this:

def recursion(a):

    if a <= 1:      #base case

        return 1

    else:

        return a * recursion(a - 1)

This recursive function calls same function over and over again until the base case and then evaluates the entire expression. Here s what it looks like:

>>> recursion(5)

factorial(5)
	5 * factorial(4)
		4 * factorial(3)
			3 * factorial (2)
				2 * factorial (1)
					1        #base case

(((((1)*2)*3)*4)*5) = 120

Recursions are very powerful and useful! Knowing how to run a recursive call is powerful for coding and opens up a whole new field of opportunities!

Python: Default Values

Python's built in functions have built in values. For example, the print function has the following default values:

>>> help(print)
Help on built-in function print in module builtins:

print(...)
    print(value, ..., sep=' ', end='\n', file=sys.stdout, flush=False)
...


The default values are pre-set. So the following code produces:

>>> print(1, 2, 3, 4, 5)
1 2 3 4 5


You can change various default values:

>>> print(1, 2, 3, 4, 5, sep='.')
1.2.3.4.5
>>> print(1, 2 , 3, 4, 5, sep='. . .', end='!')
1. . .2. . .3. . .4. . .5!


You can also make functions that have their own default values:

>>> def default_value(value1, value2 = 0, value3 = []):
>>>     print (value1, value2, value3, sep='. . .')
>>> default_value('abc')
abc. . .0. . .[]


You can change default values:

>>> def default_value(value1, value2 = 0, value3 = []):
>>>     print (value1, value2, value3, sep='. . .')
>>> default_value('abc', value2= 1234, value3 = ['a', 'b', 1])

abc. . .1234. . .['a', 'b', 1]

But be careful when working with mutable objects:

>>> def default_value(value1, value2=[]):

>>>     (value2.append(value1))

>>>     print(value2)

>>> default_value(1)

[1]

>>> default_value(1)

[1, 1]

>>> default_value(1)

[1, 1, 1]

>>> default_value(1)

[1, 1, 1, 1]

    

Classes

Every other class derives from the object class.

>>> help(object)
Help on class object in module builtins:

class object
  |     The most base type


Special methods in Python begin and end with 2 underscores and are called by particular syntax, e.g.:

x.__init__( . . . ) 
x.__eq__(y) <==> x==y
x.__str__() <==> str(x)
x.__floordiv__(y) <==> x//y

Various functions like print() call __str__