Python Searching and Sorting

Posted on | In

We assume the array elements are sorted, and we want to find if the input value is inside the array using binary search (divide and conquer).

                 
Array Size 1 2 3 4 5 6 7 8
Iterations 0 1 2 2 3 3 3 4

We notice that the iterations it takes to find out the element in worse case is $O(\log n + 1)$. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def binary_search(array, target):
    low = 0
    high = len(array)-1

    while (low <= high):
        mid = (low+high)/2
        if (array[mid] > target):
            high = mid+1
        elif (array[mid] < target):
            low = mid+1
        else:
            return mid
    return -1

a = binary_search([1, 2, 3, 4, 5], 5)
print a
# output: 4

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def recursive(input):
    if input <= 0:
        return input
    else:
        output = recursive(input - 1)
        return output

# recursive(2)
#   recursive(1)
#       recursive(0)
#           return 0
#       output = 0
#       return 0
#   output = 0
#   return 0

Fibonacci Sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

1
2
3
4
def get_fib(position):
    if position == 0 or position == 1:
        return position
    return get_fib(position - 1) + get_fib(position - 2)

Bubble Sort

       
Worst-case complexity Average-case complexity Best-case complexity Space complexity
$O(n^2)$ $O(n^2)$ $O(n^2)$ $O(n)$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bubbleSort(array):
    left = 0
    right = 1

    for i in range (len(array)):
        while right < len(array):
            if array[left] > array[right]:
                temp = array[right]
                array[right] = array[left]
                array[left] = temp
            left += 1
            right += 1

arr = [1, 5, 3, 9, 7]
bubbleSort(arr)
print arr

# output: [1, 3, 5, 7, 9]

Merge Sort

       
Worst-case complexity Average-case complexity Best-case complexity Space complexity
$O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def mergeSort(array):
    if len(array) > 1:
        mid = len(array)//2
        lefthalf = array[:mid]
        righthalf = array[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i = 0
        j = 0
        k = 0

        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                array[k] = lefthalf[i]
                i += 1
            else:
                array[k] = righthalf[j]
                j += 1
            k += 1

        while i < len(lefthalf):
            array[k] = lefthalf[i]
            i += 1
            k += 1

        while j < len(righthalf):
            array[k] = righthalf[j]
            j += 1
            k += 1

array = [1, 5, 3, 9, 7]
mergeSort(array)
print array

QuickSort

       
Worst-case complexity Average-case complexity Best-case complexity Space complexity
$O(n^2)$ $O(n \log n)$ $O(n \log n)$ $O(\log n)$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def quickSort(array):
    low = 0
    high = len(array)-1
    quickSortHelper(array, low, high)

def quickSortHelper(array, low, high):
    if low < high:
        splitPoint = partition(array, low, high)
        quickSortHelper(array, low, splitPoint-1)
        quickSortHelper(array, splitPoint+1, high)

def partition(array, low, high):
    pivot = array[low]
    lm = low + 1
    rm = high
    done = False

# the and order cannot change
    while not done:
        while lm <= rm and array[lm] <= pivot:
            lm += 1
        while lm <= rm and array[rm] >= pivot:
            rm -= 1

        if lm > rm:
            done = True
        else:
            temp = array[rm]
            array[rm] = array[lm]
            array[lm] = temp

#    temp = array[rm]
#    array[rm] = array[low]
#    array[lm] = temp
    temp = array[low]
    array[low] = array[rm]
    array[rm] = temp
    return rm

array = [1, 5, 3, 9, 7]
quickSort(array)
print array

Reference: Udacity Technical Interview Course