Sorting data is probably the most common tasks you’ll need to do in your programs. As a user of many different online applications, you are sorting data every day. Every single shopping website allows you to sort the data. For example, you can sort by lowest price, highest price, number of customer reviews, average review score, and so on. It doesn’t matter if its Amazon, Target, Barnes n Noble, or the Lego store. Its all pretty easy to do, all we have to do as the user is click a link, and our data is sorted. The sorting problem has been solved, and all modern programming languages have sorting logic already built-in, and they’re very efficient, so you will not need to implement your own sorting algorithm. It does help to understand the theory and application of some common sorting techniques, and that is what we will examine now.
Bubble Sort
The bubble sort is the first sorting algorithm to learn about. You won’t likely use it in the wild, as it is not very efficient. It is easy to understand, however, and it’s a good first sorting routine to learn. A bubble sort starts by comparing the first two elements to each other to see which is larger. If the first element is bigger than the second, then the two elements get swapped. The bubble sort then advances and does the same operation on the next two elements. This continues until all items in the array have been inspected and the largest value has moved all the way to the right (top) of the array. The algorithm then repeats the entire process working on all the elements except the one before the last item and then the one before that and so on until the array is fully sorted.
This visualization is the first pass of the code example below.
- Easier to understand and implement
- Not very good performance: O(n2)
- Other sorting algorithms are higher performance
- A good first sorting algorithm to learn
Bubble sort Python code
def bubbleSort(data_to_sort):
for i in range(len(data_to_sort) - 1, 0, -1):
for j in range(i):
if data_to_sort[j] > data_to_sort[j + 1]:
temp = data_to_sort[j]
data_to_sort[j] = data_to_sort[j + 1]
data_to_sort[j + 1] = temp
print(f'Iteration: {abs(i - len(data_to_sort))}', data_to_sort)
list_to_sort = [90, 50, 10, 20, 70, 60, 40, 30, 80]
print('Original List: ', list_to_sort)
bubbleSort(list_to_sort)
print('Sorted List: ', list_to_sort)
Original List: [90, 50, 10, 20, 70, 60, 40, 30, 80] Iteration: 1 [50, 10, 20, 70, 60, 40, 30, 80, 90] Iteration: 2 [10, 20, 50, 60, 40, 30, 70, 80, 90] Iteration: 3 [10, 20, 50, 40, 30, 60, 70, 80, 90] Iteration: 4 [10, 20, 40, 30, 50, 60, 70, 80, 90] Iteration: 5 [10, 20, 30, 40, 50, 60, 70, 80, 90] Iteration: 6 [10, 20, 30, 40, 50, 60, 70, 80, 90] Iteration: 7 [10, 20, 30, 40, 50, 60, 70, 80, 90] Iteration: 8 [10, 20, 30, 40, 50, 60, 70, 80, 90] Sorted List: [10, 20, 30, 40, 50, 60, 70, 80, 90]
- Python Program for Bubble Sort (stechies)
- Python Program for Bubble Sort (tutorialgateway)
- How the Bubble Sorting technique is implemented in Python (codespeedy)
- Bubble Sort algorithm in Python (programminginpython)
- Python Bubble Sort (thecrazyprogrammer)
- Sorting a list using bubble sort in Python (codesdope)
Merge Sort
Merge sort is a divide and conquer algorithm that breaks an array into smaller pieces to operate on. Merge sort has better performance than the bubble sort. How it works is to successively break an array down until there are only individual arrays of one element each. At that point, the algorithm begins merging these arrays back up into each other until the original array is rebuilt fully sorted.
- Divide and conquer
- Breaks array into individual pieces
- Uses recursion to operate on the data
- Merges the pieces back into the array in sorted form
- Has good performance on large amounts of data
Merge sort Python code
def mergesort(data_to_sort):
if len(data_to_sort) > 1:
mid = len(data_to_sort) // 2
leftarray = data_to_sort[:mid]
rightarray = data_to_sort[mid:]
mergesort(leftarray)
mergesort(rightarray)
i, j, k = 0, 0, 0
while i < len(leftarray) and j < len(rightarray):
if leftarray[i] < rightarray[j]:
data_to_sort[k] = leftarray[i]
i += 1
else:
data_to_sort[k] = rightarray[j]
j += 1
k += 1
while i < len(leftarray):
data_to_sort[k] = leftarray[i]
i += 1
k += 1
while j < len(rightarray):
data_to_sort[k] = rightarray[j]
j += 1
k += 1
list_to_sort = [90, 50, 10, 20, 70, 60, 40, 30, 80]
print('Original List: ', list_to_sort)
mergesort(list_to_sort)
print('Sorted List: ', list_to_sort)
Original List: [90, 50, 10, 20, 70, 60, 40, 30, 80] Sorted List: [10, 20, 30, 40, 50, 60, 70, 80, 90]
- Merge Sort Python Tutorial – An Efficient Way Of Sorting (simplifiedpython)
- How to sort elements using Merge sort in python (spiderlabweb)
- Merge Sort: A Quick Tutorial and Implementation Guide (pythoncentral)
- Merge Sort with Python Code Implementation (teachyourselfpython)
- Python program to merge two lists and sort it (codevscolor)
Quick Sort
Quicksort is also a divide and conquer algorithm that uses recursion to perform its job, and often has better performance than Merge Sort. Quicksort completes the sorting of data in place in the existing array. The main feature of Quicksort is the selection of a Pivot Point. The pivot point is used to begin partitioning the array. The purpose of the partitioning process is to move items that are on the wrong side of the pivot value and figure out the point at which to split the array. In the quick sort, there is a lower index and an upper index. It begins by incrementing the lower index, as long as it is less than the upper index, and until it finds a value that’s larger than the pivot value. Then the upper index is decremented until it finds a value that is less than the pivot value as long as the upper index is greater than the lower index. When those two indexes cross each other, the array is split. The pivot value is then swapped with the upper index so the left side contains values below the pivot, and the right side contains values above the pivot. This process continues until the arrays can no longer be split. All of the sorting logic gets done in the partition step of the quick sort, and the data is sorted in place.
Quick sort Python code
def quickSort(data_to_sort, first, last):
if first < last:
pivotindex = partition(data_to_sort, first, last)
quickSort(data_to_sort, first, pivotindex - 1)
quickSort(data_to_sort, pivotindex + 1, last)
def partition(values, first, last):
pivotvalue = values[first]
lower = first + 1
upper = last
done = False
while not done:
while lower <= upper and values[lower] <= pivotvalue:
lower += 1
while values[upper] >= pivotvalue and upper >= lower:
upper -= 1
if upper < lower:
done = True
else:
temp = values[lower]
values[lower] = values[upper]
values[upper] = temp
temp = values[first]
values[first] = values[upper]
values[upper] = temp
return upper
list_to_sort = [90, 50, 10, 20, 70, 60, 40, 30, 80]
print('Original List: ', list_to_sort)
quickSort(list_to_sort, 0, len(list_to_sort) - 1)
print('Sorted List: ', list_to_sort)
Original List: [90, 50, 10, 20, 70, 60, 40, 30, 80] Sorted List: [10, 20, 30, 40, 50, 60, 70, 80, 90]
- How to implement QuickSort in Python (educative)
- The Shortest Quicksort Implementation in Python (finxter)
- Quick Sort implementation example in Python (codezup)
- Quick Sort Algorithm (interviewbit)
- QuickSort in Python (coderwall)
- Quicksort with Python (stackoverflow)
Bubble Sort Merge Sort and Quick Sort in Python Summary
There are many algorithms to sort data. We had a look at three of the more common ones implemented in Python. Those are the Bubble sort, the merge sort, and the quick sort. Each has an algorithmic complexity associated with them, and varying degrees of performance and ease of use.
