Tutorial 06 - Data sorting
Contents
Tutorial 06 - Data sorting¶
Various algorithms for data sorting and their comparison, bubble sort, selection sort, insertion sort, shell sort, quick sort, heap sort, benchmarking.
import numpy as np
import matplotlib.pyplot as plt
Bubble sort¶
Exercise 06.1: Implement the bubble sort algorithm.
def bubble_sort(array):
"""
Sorts the input data using bubble sort algorithm.
Args:
array (array_like): input data
Returns:
numpy.ndarray: sorted data
"""
# add your code here
You may evaluate the correctness of your implementation using the numpy.sort function.
random_array = np.random.rand(100)
try:
np.testing.assert_array_almost_equal(bubble_sort(random_array), np.sort(random_array), decimal=7)
except AssertionError as E:
print(E)
else:
print("The implementation is correct.")
Selection sort¶
Exercise 06.2: Implement the selection sort algorithm.
def selection_sort(array):
"""
Sorts the input data using selection sort algorithm.
Args:
array (array_like): input data
Returns:
numpy.ndarray: sorted data
"""
# add your code here
You may evaluate the correctness of your implementation using the numpy.sort function.
random_array = np.random.rand(100)
try:
np.testing.assert_array_almost_equal(selection_sort(random_array), np.sort(random_array), decimal=7)
except AssertionError as E:
print(E)
else:
print("The implementation is correct.")
Insertion sort¶
Exercise 06.3: Implement the insertion sort algorithm.
def insertion_sort(array):
"""
Sorts the input data using inserion sort algorithm.
Args:
array (array_like): input data
Returns:
numpy.ndarray: sorted data
"""
# add your code here
You may evaluate the correctness of your implementation using the numpy.sort function.
random_array = np.random.rand(100)
try:
np.testing.assert_array_almost_equal(insertion_sort(random_array), np.sort(random_array), decimal=7)
except AssertionError as E:
print(E)
else:
print("The implementation is correct.")
Shell sort¶
Exercise 06.4: Implement the shell sort algorithm.
def shell_sort(array):
"""
Sorts the input data using shell sort algorithm.
Args:
array (array_like): input data
Returns:
numpy.ndarray: sorted data
"""
# add your code here
You may evaluate the correctness of your implementation using the numpy.sort function.
random_array = np.random.rand(100)
try:
np.testing.assert_array_almost_equal(shell_sort(random_array), np.sort(random_array), decimal=7)
except AssertionError as E:
print(E)
else:
print("The implementation is correct.")
Quick sort¶
Exercise 06.5: Implement the quick sort algorithm.
def quick_sort(array):
"""
Sorts the input data using quicksort algorithm.
Args:
array (array_like): input data
Returns:
numpy.ndarray: sorted data
"""
# add your code here
You may evaluate the correctness of your implementation using the numpy.sort function.
random_array = np.random.rand(100)
try:
np.testing.assert_array_almost_equal(quick_sort(random_array), np.sort(random_array), decimal=7)
except AssertionError as E:
print(E)
else:
print("The implementation is correct.")
Heap sort¶
Exercise 06.6: Implement the heap sort algorithm.
def heap_sort(array):
"""
Sorts the input data using heapsort algorithm.
Args:
array (array_like): input data
Returns:
numpy.ndarray: sorted data
"""
# add your code here
You may evaluate the correctness of your implementation using the numpy.sort function.
random_array = np.random.rand(100)
try:
np.testing.assert_array_almost_equal(heap_sort(random_array), np.sort(random_array), decimal=7)
except AssertionError as E:
print(E)
else:
print("The implementation is correct.")
Benchmark¶
Exercise 06.7: Compare the running times of sorting algorithms for different size of input and plot the result.
# add your code here