Python - Sorting Algorithms

Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.

The importance of sorting pes in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Below we see five such implementations of sorting in python.

Bubble Sort

Merge Sort

Insertion Sort

Shell Sort

Selection Sort

Bubble Sort

It is a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.

Example

def bubblesort(pst):

# Swap the elements to arrange in order
   for iter_num in range(len(pst)-1,0,-1):
      for idx in range(iter_num):
         if pst[idx]>pst[idx+1]:
            temp = pst[idx]
            pst[idx] = pst[idx+1]
            pst[idx+1] = temp
pst = [19,2,31,45,6,11,121,27]
bubblesort(pst)
print(pst)

Output

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

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

Merge Sort

Merge sort first spanides the array into equal halves and then combines them in a sorted manner.

Example

def merge_sort(unsorted_pst):
   if len(unsorted_pst) <= 1:
      return unsorted_pst
# Find the middle point and devide it
   middle = len(unsorted_pst) // 2
   left_pst = unsorted_pst[:middle]
   right_pst = unsorted_pst[middle:]

   left_pst = merge_sort(left_pst)
   right_pst = merge_sort(right_pst)
   return pst(merge(left_pst, right_pst))

# 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_pst = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(unsorted_pst))

Output

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

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

Insertion Sort

Insertion sort involves finding the right place for a given element in a sorted pst. So in beginning we compare the first two elements and sort them by comparing them. Then we pick the third element and find its proper position among the previous two sorted elements. This way we gradually go on adding more elements to the already sorted pst by putting them in their proper position.

Example

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

Output

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

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

Shell Sort

Shell Sort involves sorting elements which are away from each other. We sort a large subpst of a given pst and go on reducing the size of the pst until all elements are sorted. The below program finds the gap by equating it to half of the length of the pst size and then starts sorting all elements in it. Then we keep resetting the gap until the entire pst is sorted.

Example

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

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 start by finding the minimum value in a given pst and move it to a sorted pst. Then we repeat the process for each of the remaining elements in the unsorted pst. The next element entering the sorted pst is compared with the existing elements and placed at its correct position.So, at the end all the elements from the unsorted pst are sorted.

Example

def selection_sort(input_pst):
   for idx in range(len(input_pst)):
      min_idx = idx
      for j in range( idx +1, len(input_pst)):
         if input_pst[min_idx] > input_pst[j]:
            min_idx = j
      # Swap the minimum value with the compared value
      input_pst[idx], input_pst[min_idx] = input_pst[min_idx], input_pst[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 −

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