Sorting Algoritms
Bubble sort
Bubble sort is a simple sorting algorithm that repeatedly steps through the list. In this algorithm, adjacent elements are compared and swapped if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Take an array of numbers " 20 9 6 3 1", and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in yellow background are being compared.
Program (bubble-sort.py)
arr = [20,9,6,3,1]
n = len(arr)
for i in range(n-1):
for j in range(n-1-i):
if arr[j]>arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
print('Array after sorting')
print(arr)Output
Array after sorting [1, 3, 6, 9, 20]
Selection sort
The selection sort algorithm starts by finding the smallest number in the list and exchanging it with the first number. The next smallest number is found and exchanged with the second number, and so on. Use of the selection sort to order the five elements of the array is described below. Smallest element of each pass is written in blue background.
Program (selection-sort.py)
arr = [20,9,16,3,5]
n = len(arr)
for i in range(n-1):
pos_smallest = i
for j in range(i+1, n):
if arr[j] < arr[pos_smallest]:
pos_smallest = j
arr[i], arr[pos_smallest] = arr[pos_smallest], arr[i]
print('Array after sorting')
print(arr)Output
Array after sorting [3, 5, 9, 16, 20]
Insertion sort
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort.
Take an array of numbers " 20 9 16 3 5”. Following figure explains the steps.
Program (insertion-sort.py)
arr = [20,9,16,3,5]
n = len(arr)
for i in range(1,n):
temp = arr[i]
j = i - 1
while(j >= 0 and temp < arr[j]):
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = temp
print('Array after sorting')
print(arr)Output
Array after sorting [3, 5, 9, 16, 20]