Sorting algorithms are fundamental to computer science which convert unsorted data into particular order. Sorting is widely applicable in our daily lives including listing items by price in retail store website and determining search order in search engine website. In this article, we will introduce the concepts behind several sorting algorithms, followed by a complete Python code for applying them to a sample unsorted list. In our example, we implement different sorting algorithms to the same sample list by ascending order
Bubble sort is considered as the most intuitive way to sort elements in the list, comparing the next element and switch position if condition is met. (In our case is that next element is smaller than existing element). It iterates and compares until all the elements are sorted.
Example
Sample : [64, 25, 12, 22, 11]
1st step: [25, 64, 12, 22, 11] → swap since A[1] 25 < A[0] 64
2nd step: [25, 12, 64, 22, 11] → swap since A[2] 12 < A[1] 64
3rd step: [25, 12, 22, 64, 11] → swap since A[3] 22 < A[2] 64
...
Keep comparing until the list is sorted
You can see that going through one round with all elements is not enough to sort all the elements. Therefore, we set a flag to break the loop if there is nothing change in the round and finish the sorting. The sorting process is relatively exhaustive since it is required to loop and compare every other element.
def bubblesort(samplelist):
length = len(samplelist)
while True:
# flag to indicate any changes in one round
no_change_flag = True
for i in range(length-1):
# compare the next and existing elements
if samplelist[i+1] < samplelist[i]:
samplelist[i], samplelist[i+1] = samplelist[i+1], samplelist[i]
no_change_flag = False
# if no change, then break the loop and return the list
if no_change_flag:
break
return samplelist
bubblesort(sample)
# [11, 12, 22, 25, 64]
Selection sort is an algorithm that takes the minimum / maximum value (sort in ascending / descending order) in the list and moves it to the proper position in the list. In our case, we select the minimum element from the sublist and place it at the next position in the list.
Example
Sample: [64, 25, 12, 22, 11]
1st step:
Sample: [64, 25, 12, 22, 11]
Sublist: [64, 25, 12, 22, 11]