Sorting: ordering a list of values
Searching: finding the position of a value within a list

import random 

data = list(range(10000))
random.shuffle(data)
data[:5]

[6984, 4192, 390, 291, 1277]

Copy problem¶

import copy

test = [0, 1, 2, '3',[4, 5]]
test_no_copy = test
test_copy = copy.copy(test) # or test[:]
test_deepcopy = copy.deepcopy(test)

test_no_copy[0] = 5
test_copy[1] = 6
print(f'ORIGIN: {test},\nCOPY: {test_copy},\nNO_COPY: {test_no_copy}\n')

test_copy[4].append(7)
print(f'ORIGIN: {test},\nCOPY: {test_copy},\nNO_COPY: {test_no_copy}\n')

print(f'ORIGIN: {test},\nCOPY: {test_copy},\nDEEP_COPY: {test_deepcopy}\nNO_COPY: {test_no_copy}\n')
test_deepcopy[4].append(8)
print(f'ORIGIN: {test},\nCOPY: {test_copy},\nDEEP_COPY: {test_deepcopy}\nNO_COPY: {test_no_copy}\n')

Sorting¶

Built-in sort function¶

example_0 = data[:]

# def length_key(x)
#     return len(x)

example_words = ['small', 'verylongword', 'larger', 'evenlarger']
example_words.sort()
print('Sorted by default (alphabetically)')
print(example_words)
print()

example_words.sort(reverse=True)
print('Sorted in reverse order')
print(example_words)
print()

example_words.sort(key=lambda x: len(x))
print('Sorted by length')
print(example_words)
print()

example_words.sort(key=lambda x: len(x), reverse=True)
print('Sorted by length in reverse order')
print(example_words)

Sorted by default (alphabetically)
['evenlarger', 'larger', 'small', 'verylongword']

Sorted in reverse order
['verylongword', 'small', 'larger', 'evenlarger']

Sorted by length
['small', 'larger', 'evenlarger', 'verylongword']

Sorted by length in reverse order
['verylongword', 'evenlarger', 'larger', 'small']

%time example_0.sort(key=lambda x: x, reverse=False) # <- method, returns None, data will be modified

CPU times: user 7.61 ms, sys: 2.77 ms, total: 10.4 ms
Wall time: 9.32 ms

# or
# %time sorted(data, key=lambda x: x, reverse=False)[:5]

example_0[:5],data[:5]

Bubble sort¶

BubbleSort

$C o m p l e x i t y = ?$

example_1 = data[:]

swap = lambda x,y: (y, x)

print((example_1[0],example_1[1]), swap(example_1[0],example_1[1]), sep='\n')

def bubble_sort(list: data) -> list:
    # TODO: put your code here
    return data

Insertion sort¶

InsertionSort

$C o m p l e x i t y = ?$

def insertion_sort(list: data) -> list:
    # TODO: put your code here
    return data

Quicksort¶

Quicksort

$C o m p l e x i t y = ?$

def quick_sort(list: data) -> list:
    # TODO: put your code here
    return data

Merge sort¶

MergeSort

$C o m p l e x i t y = ?$

def merge_sort(list: data) -> list:
    # TODO: put your code here
    return data

Bogosort?¶

~~~As you wish...~~~

# def bogo_sort(list: data) -> list:
#     # TODO: put your code here
#     return data

Long story short¶

TableSort

Bonus task¶

Implement and compare time complexity of sorting algorithms on random data (mean of 5 independent runs), also use built-in function

import time

start = time.time()

while (time.time() - start  < 2):  # wait 2 seconds
    pass

# sorted(data)

end = time.time()
print(end - start)

Linear Search¶

LinearSearch

%time data.index(33)

example = [0]*10000+[1]
example[5000] = 2
example[-5:]

%time example.index(0)
print()
%time example.index(1)
print()
%time example.index(2)

Binary Search¶

BinarySearch

data_for_bs = sorted(data)

def binary_search(list: data) -> int:
    # TODO: put your code here
    return -1

%time binary_search(data)

One more [random] thing...¶

https://docs.python.org/3/library/random.html

random.randrange(-10, 12, 2)

random.randint(1, 2)

random.choice(range(10))

random.choices([1,2,3], weights=[0.5,0.3,0.2],k=20)

lst = list(range(10))
random.shuffle(lst)
lst

random.sample(range(100), k=10)

random.random(), random.uniform(10,16)