Sorting algorithms are a great way to bolster your resume because they have so many real-world applications and can be used in many fields of computer science.
Types Of Sorting Algorithms
These are the mainly used algorithms and the ones we will cover in this series are.
- Bubble Sort
- Quick Sort
- Insertion Sort
- Selection Sort
- Heap Sort
- Bucket Sort
- Radix Sort
Bubble Sort
Bubble Sort works by repeatedly swapping adjacent elements if they are in the wrong order. Although bubble sort may be the easiest to Implement, its O(n**2) complexity means that its efficiency decreases drastically on a list with more than a few elements.
We will first discuss implementing the algorithm on a simple list, then we will visualize it in a GUI with Python Tkinter.
Let's first talk about how bubble sort works, I will use the python interactive shell.
Let's first define our list.
>>> lst = [25, 63, 94, 18, 52, 71, 39]
now let's define a function to sort the list itself and discuss how the code works.
>>> def bubbleSort(lst):
n = len(lst)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
Now let's look at the code in-depth. n = len(lst) assigns the length of the list lst to the value n for use later in the function.
The iteration for i in range(n): iterates n number of times, note that we formerly defined n as the length of list lst .
The line for j in range(0, n-i-1) means that it iterates whatever is in the block iterates from 0 to n-i-1 number of times.
Now for the meat of the sort. This is the part that actually does the comparisons, let me explain how it all works out. It first takes finds the length of the list and uses this to iterate the list, iterating the list directly would cause problems because the indexes of the items would change constantly, I will show this at the end of this write-up. The next iteration for j in range(0, n-i-1): makes the code run on all the items in front of it while ensuring that it doesn't encounter an IndexError. The last part of the function checks whether the item's value is lower than that of the item next to it.
Let us run a series of tests on it with a testing algorithm.
import random as rd
def test():
for i in range(10):
arr = [rd.randint(1, 100) for i in range(rd.randint(5, 15))]
print(arr)
bubbleSort(arr)
test = True
print ("Sorted array is:")
for i in range(len(arr)):
print ("%d" %arr[i])
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
test = False
else:
pass
if test:
print('passed')
else:
print('failed')
This function will test the sorting algorithm with a series of random values chosen from 1 through 100 in a list of a random amount of values chosen 1 through 15.
Now let's put it all together and run it.
import random as rd
def bubbleSort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
def test():
for i in range(10):
arr = [rd.randint(1, 100) for i in range(rd.randint(5, 15))]
print(arr)
bubbleSort(arr)
test = True
print ("Sorted array is:")
for i in range(len(arr)):
print ("%d" %arr[i])
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
test = False
else:
pass
if test:
print('passed')
else:
print('failed')
test()
Now the output
[100, 95, 68, 6, 40, 8, 63, 47, 70, 92]
Sorted array is: [6, 8, 40, 47, 63, 68, 70, 92, 95, 100]
passed
[4, 43, 53, 57, 83, 98, 50]
Sorted array is: [4, 43, 50, 53, 57, 83, 98]
passed
[79, 80, 50, 42, 86]
Sorted array is: [42, 50, 79, 80, 86]
passed
[97, 97, 59, 85, 60, 6, 16, 33, 31, 54, 71, 6, 77, 75]
Sorted array is: [6, 6, 16, 31, 33, 54, 59, 60, 71, 75, 77, 85, 97, 97]
passed
[83, 36, 77, 45, 35]
Sorted array is: [35, 36, 45, 77, 83]
passed
[64, 18, 70, 87, 87, 35]
Sorted array is: [18, 35, 64, 70, 87, 87]
passed
[65, 13, 95, 1, 59]
Sorted array is: [1, 13, 59, 65, 95]
passed
[73, 26, 70, 97, 9, 84, 44, 5, 88, 50, 94, 52]
Sorted array is: [5, 9, 26, 44, 50, 52, 70, 73, 84, 88, 94, 97]
passed
[13, 97, 53, 61, 6, 12, 49, 51, 18, 21]
Sorted array is: [6, 12, 13, 18, 21, 49, 51, 53, 61, 97]
passed
[70, 99, 4, 89, 78]
Sorted array is: [4, 70, 78, 89, 99]
passed
As we can see, it passed all the tests. Now let's show the common mistakes that can come from miscoding this algorithm.
First, let's add print statements to the code to see what it does every step of the way.
import random as rd
def bubbleSort(arr):
print('||||||||||||||||||||||||||||||||||||||||||||||||||||||')
n = len(arr)
print(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1]:
print ('{} greater than {}, exchanging'.format(arr[j], arr[j+1]))
arr[j], arr[j+1] = arr[j+1], arr[j]
print('{} sorted to this point'.format(arr))
def test():
for i in range(10):
arr = [rd.randint(1, 100) for i in range(rd.randint(5, 15))]
bubbleSort(arr)
test = True
print ("Sorted array is:", arr)
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
test = False
else:
pass
if test:
print('passed')
else:
print('failed')
test()
Testing the code this would give this for one iteration of the test:
[17, 50, 48, 73, 5, 46, 78, 79, 15]
50 greater than 48, exchanging
[17, 48, 50, 73, 5, 46, 78, 79, 15] sorted to this point
73 greater than 5, exchanging
[17, 48, 50, 5, 73, 46, 78, 79, 15] sorted to this point
73 greater than 46, exchanging
[17, 48, 50, 5, 46, 73, 78, 79, 15] sorted to this point
79 greater than 15, exchanging
[17, 48, 50, 5, 46, 73, 78, 15, 79] sorted to this point
50 greater than 5, exchanging
[17, 48, 5, 50, 46, 73, 78, 15, 79] sorted to this point
50 greater than 46, exchanging
[17, 48, 5, 46, 50, 73, 78, 15, 79] sorted to this point
78 greater than 15, exchanging
[17, 48, 5, 46, 50, 73, 15, 78, 79] sorted to this point
48 greater than 5, exchanging
[17, 5, 48, 46, 50, 73, 15, 78, 79] sorted to this point
48 greater than 46, exchanging
[17, 5, 46, 48, 50, 73, 15, 78, 79] sorted to this point
73 greater than 15, exchanging
[17, 5, 46, 48, 50, 15, 73, 78, 79] sorted to this point
17 greater than 5, exchanging
[5, 17, 46, 48, 50, 15, 73, 78, 79] sorted to this point
50 greater than 15, exchanging
[5, 17, 46, 48, 15, 50, 73, 78, 79] sorted to this point
48 greater than 15, exchanging
[5, 17, 46, 15, 48, 50, 73, 78, 79] sorted to this point
46 greater than 15, exchanging
[5, 17, 15, 46, 48, 50, 73, 78, 79] sorted to this point
17 greater than 15, exchanging
[5, 15, 17, 46, 48, 50, 73, 78, 79] sorted to this point
Sorted array is: [5, 15, 17, 46, 48, 50, 73, 78, 79]
passed
The first mistake you can make is iterating the list instead of a range of the length of the list. Let me show what happens when you do that.
def bubbleSort(arr):
print('||||||||||||||||||||||||||||||||||||||||||||||||||||||')
n = len(arr)
print(arr)
# new changes to show what happens when you iterate the list itself
# it was formerly for i in range(n):
for i in arr:
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
print ('{} greater than {}, exchanging'.format(arr[j], arr[j+1]))
arr[j], arr[j+1] = arr[j+1], arr[j]
print('{} sorted to this point'.format(arr))
This is output from the test function I wrote
||||||||||||||||||||||||||||||||||||||||||||||||||||||
[58, 43, 23, 55, 8, 7, 48, 24, 93, 19, 62, 95, 100]
58 greater than 43, exchanging
[43, 58, 23, 55, 8, 7, 48, 24, 93, 19, 62, 95, 100] sorted to this point
58 greater than 23, exchanging
[43, 23, 58, 55, 8, 7, 48, 24, 93, 19, 62, 95, 100] sorted to this point
58 greater than 55, exchanging
[43, 23, 55, 58, 8, 7, 48, 24, 93, 19, 62, 95, 100] sorted to this point
58 greater than 8, exchanging
[43, 23, 55, 8, 58, 7, 48, 24, 93, 19, 62, 95, 100] sorted to this point
43 greater than 23, exchanging
[23, 43, 55, 8, 58, 7, 48, 24, 93, 19, 62, 95, 100] sorted to this point
55 greater than 8, exchanging
[23, 43, 8, 55, 58, 7, 48, 24, 93, 19, 62, 95, 100] sorted to this point
58 greater than 7, exchanging
[23, 43, 8, 55, 7, 58, 48, 24, 93, 19, 62, 95, 100] sorted to this point
Sorted array is: [23, 43, 8, 55, 7, 58, 48, 24, 93, 19, 62, 95, 100]
failed
This happens because the index of the items keeps changing, but if we iterate the range of the length of the list, everything will be alright because it is constant.
Let's go over another common problem that can be encountered when writing this algorithm.
def bubbleSort(arr):
print('||||||||||||||||||||||||||||||||||||||||||||||||||||||')
n = len(arr)
print(arr)
for i in range(n):
for j in range(0, n-i): #formerly for j in range(0, n-i-1)
if arr[j] > arr[j+1]:
print ('{} greater than {}, exchanging'.format(arr[j], arr[j+1]))
arr[j], arr[j+1] = arr[j+1], arr[j]
print('{} sorted to this point'.format(arr))
The changes made make the iteration try to iterate an index that is not on the list. The same error would occur if any variable is removed from that range function.
Another common mistake is not replacing the items correctly. If the items are not, the items are not replaced correctly, the sorting would not work.
Now, for the GUI part of it. it will be relatively simple to implement after understanding the basics of the algorithm. this is the link to the file. github.com/thecoder-co/sorting/blob/main/bu..
Expect a subsequent article on other sorting algorithms.
have a nice day!