Python Data Structures: Sorting Algorithms

Sorting refers to arranging data in a specific format. Sorting algorithms specify how to arrange data in a specific order. The most common sorting methods are numerical or lexical order.

Sorting is important because searching data can be optimized to a very high level if it is stored in a sorted manner. Sorting is also used to represent data in a more readable format. Below we will look at five sorting implementations in Python.

• Bubble Sort

• Merge Sort

• Insertion Sort

• Shell Sort

• Selection Sort

Bubble Sort

This is a comparison-based algorithm, in which every pair of adjacent elements is compared, and if the elements are out of order, they are swapped.

Example

def bubblesort(list):

# Swap the elements to arrange in order

for iter_num in range(len(list)-1,0,-1):

for idx in range(iter_num):

if list[idx]>list[idx+1]:

temp = list[idx]

list[idx] = list[idx+1]

list[idx+1] = temp

list = [19,2,31,45,6,11,121,27]

bubblesort(list)

print(list)

Output

When the above code is executed, it produces the following output –

[2, 6, 11, 19, 27, 31, 45, 121]

Merge Sort

Merge sort first divides the array into two equal halves and then merges them in a sorted fashion.

Example

def merge_sort(unsorted_list):
   if len(unsorted_list) <= 1:
      return unsorted_list
# Find the middle point and devide it
   middle = len(unsorted_list) // 2
   left_list = unsorted_list[:middle]
   right_list = unsorted_list[middle:]

   left_list = merge_sort(left_list)
   right_list = merge_sort(right_list)
   return list(merge(left_list, right_list))

#Merge the sorted halves
def merge(left_half,right_half):
   res = []
   while len(left_half) != 0 and len(right_half) != 0:
      if left_half[0] < right_half[0]: res.append(left_half[0])
left_half.remove(left_half[0])
else:
res.append(right_half[0])
right_half.remove(right_half[0])
if len(left_half) == 0:
res = res + right_half
else:
res = res + left_half
return res
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(unsorted_list))

Output

When the above code is executed, it produces the following output –

[11, 12, 22, 25, 34, 64, 90]

Insertion Sort

Insertion sort involves finding the correct position for a given element in a sorted list. So, we start by comparing the first two elements and sorting them accordingly. Then, we pick a third element and find its proper position within the first two sorted elements. In this way, we gradually insert more elements into the sorted list, placing them in their proper positions.

Example

def insertion_sort(InputList):
for i in range(1, len(InputList)):
j = i-1
nxt_element = InputList[i]
# Compare the current element with the next one
while (InputList[j] > nxt_element) and (j >= 0):
InputList[j+1] = InputList[j]
j=j-1
InputList[j+1] = nxt_element
list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

Output

When the above code is executed, it produces the following output –

[19, 2, 31, 45, 30, 11, 27, 121]

Shell Sort

Shell sort involves sorting elements that are far apart from each other. We sort a large sublist of a given list and continue to reduce the size of the list until all elements are sorted. The following program finds the gap by equating it to half the size of the list and then begins sorting all elements within it. We then continue to reset the gap until the entire list is sorted.

Example

def shellSort(input_list):
gap = len(input_list) // 2
while gap > 0:
for i in range(gap, len(input_list)):
temp = input_list[i]
j = i
# Sort the sublist for this gap
while j >= gap and input_list[j - gap] > temp:
input_list[j] = input_list[j - gap]
j = j - gap
input_list[j] = temp
# Reduce the gap for the next element
gap = gap//2
list = [19,2,31,45,30,11,121,27]
shellSort(list)
print(list)

Output

When the above code is executed, it produces the following result –

[2, 11, 19, 27, 30, 31, 45, 121]

Selection Sort

In selection sort, we first find the minimum value in a given list and move it to a sorted list. We then repeat this process for each remaining element in the unsorted list. The next element entering the sorted list is compared with the existing elements and placed in the correct position. Thus, at the end, all elements in the unsorted list are sorted.

Example

def selection_sort(input_list):
for idx in range(len(input_list)):
min_idx = idx
for j in range(idx +1, len(input_list)):
if input_list[min_idx] > input_list[j]:
min_idx = j
# Swap the minimum value with the compared value
input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]
l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

Output

When the above code is executed, it produces the following result –

[19, 2, 31, 45, 30, 11, 121, 27]