• Sorting: ordering a list of values
• Searching: finding the position of a value within a list
In [1]:
import random

data = list(range(10000))
random.shuffle(data)
data[:5]
Out[1]:
[6984, 4192, 390, 291, 1277]

## Copy problem¶

In [ ]:
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¶

In [2]:
example_0 = data[:]
In [6]:
# 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']
In [3]:
%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
In [ ]:
# or
# %time sorted(data, key=lambda x: x, reverse=False)[:5]
In [ ]:
example_0[:5],data[:5]

## Bubble sort¶

$Complexity = ?$

In [ ]:
example_1 = data[:]
In [ ]:
swap = lambda x,y: (y, x)

print((example_1[0],example_1[1]), swap(example_1[0],example_1[1]), sep='\n')
In [ ]:
def bubble_sort(list: data) -> list:
# TODO: put your code here
return data

## Insertion sort¶

$Complexity = ?$

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

## Quicksort¶

$Complexity = ?$

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

## Merge sort¶

$Complexity = ?$

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

## Bogosort?¶

~As you wish...~

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

## Long story short¶

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

In [ ]:
import time

start = time.time()

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

# sorted(data)

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

# Linear Search¶

In [ ]:
%time data.index(33)
In [ ]:
example = [0]*10000+[1]
example[5000] = 2
example[-5:]
In [ ]:
%time example.index(0)
print()
%time example.index(1)
print()
%time example.index(2)

# Binary Search¶

In [ ]:
data_for_bs = sorted(data)
In [ ]:
def binary_search(list: data) -> int:
# TODO: put your code here
return -1
In [ ]:
%time binary_search(data)

# One more [random] thing...¶

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

In [ ]:
random.randrange(-10, 12, 2)
In [ ]:
random.randint(1, 2)
In [ ]:
random.choice(range(10))
In [ ]:
random.choices([1,2,3], weights=[0.5,0.3,0.2],k=20)
In [ ]:
lst = list(range(10))
random.shuffle(lst)
lst
In [ ]:
random.sample(range(100), k=10)
In [ ]:
random.random(), random.uniform(10,16)