What is Sorting?

Sorting refers to the process of arranging data in a specific order, typically in ascending or descending order, based on a linear relationship among the data items.

Why Do We Need Sorting?

Sorting is crucial when working with structured data because it allows for efficient data retrieval, simplifies data analysis, and enhances overall data management.

Sorting Algorithms

This post covers the following sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort.

Bubble Sort

Bubble Sort repeatedly steps through the array, comparing adjacent elements and swapping them if they are in the wrong order. This process continues until the array is sorted, with larger elements "bubbling" to the end.

Algorithm

Step 1: Begin
Step 2: i = 0
Step 3: if i Step 4: j = 0
Step 5: if j Step 6: if array[j] > array[j 1], goto Step 7; else goto Step 8
Step 7: Swap array[j] and array[j 1]
Step 8: increment j; goto Step 5
Step 9: increment i; goto Step 3
Step 10: End

Code

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j 1]:
                arr[j], arr[j 1] = arr[j 1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Time Complexity

Best Case : O(n)
Average Case : O(n^2)
Worst Case : O(n^2)

Selection Sort

Selection Sort finds the smallest value in the unsorted portion of the array and places it at the beginning of that portion.

Algorithm

Step 1 : Begin
Step 2 : i = 0
Step 3 : if i Step 4 : minimum_value = i; j = i 1
Step 5 : if j Step 6 : if array[minimum_value] > array[j], goto Step 7; else goto Step 8
Step 7 : minimum_value = j
Step 8 : increment j; goto Step 5
Step 9 : swap array[minimum_value] and array[i]
Step 10 : increment i; goto Step 3
Step 11 : End

Code

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i   1, len(arr)):
            if arr[j] 




  
  
  Time Complexity


Best Case : O(n^2)

Average Case : O(n^2)

Worst Case : O(n^2)  


  
  
  Insertion Sort


Insertion Sort builds the sorted array one element at a time by taking each element from the unsorted portion and inserting it into the correct position in the sorted portion.


  
  
  Algorithm


Step 1: Begin

Step 2: i = 1

Step 3: if i 
Step 4: key = arr[i]

Step 5: j = i - 1

Step 6: if j >= 0 and arr[j] > key, goto Step 7; else goto Step 10

Step 7: arr[j   1] = arr[j]

Step 8: decrement j by 1

Step 9: goto Step 6

Step 10: arr[j   1] = key

Step 11: increment i by 1; goto Step 3

Step 12: End


  
  
  Code




def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j   1] = arr[j]
            j -= 1

        arr[j   1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)





  
  
  Time Complexity


Best Case : O(n)

Average Case : O(n^2)

Worst Case : O(n^2)  


  
  
  Merge Sort


Merge Sort is a divide-and-conquer algorithm that recursively divides the array into smaller sub-arrays, sorts them, and then merges them back together.


  
  
  Algorithm


Merge Sort Algorithm


Step 1: Begin

Step 2: If length(array) 
Step 3: mid_point = length(array) // 2

Step 4: left_half = array[:mid_point]

Step 5: right_half = array[mid_point:]

Step 6: sorted_left = merge_sort(left_half)

Step 7: sorted_right = merge_sort(right_half)

Step 8: return merge(sorted_left, sorted_right)

Step 9: End

Merge Function


Step 1: Begin

Step 2: sorted_merge = []

Step 3: l = 0, r = 0

Step 4: if l 
Step 5: if left[l] 
Step 6: add left[l] to sorted_merge; increment l by 1

Step 7: add right[r] to sorted_merge; increment r by 1

Step 8: goto Step 4

Step 9: if l 
Step 10: add left[l] to sorted_merge; increment l by 1 

Step 11: goto Step 9

Step 12: if r 
Step 13: add right[r] to sorted_merge; increment r by 1

Step 14: goto Step 12

Step 15: Return sorted_merge

Step 16: End


  
  
  Code




def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 




  
  
  Time Complexity


Best Case : O(n log n)

Average Case : O(n log n)

Worst Case : O(n log n)  


  
  
  Quick Sort


Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.


  
  
  Algorithm


Quick Sort


Step 1: Begin

Step 2: If low 
Step 3: pivot_index = partition(arr, low, high)

Step 4: quicksort(arr, low, pivot_index - 1)

Step 5: quicksort(arr, pivot_index   1, high)

Step 6: End  

Partition Function


Step 1: Begin

Step 2: pivot = arr[high]

Step 3: left = low, right = high - 1

Step 4: if left 
Step 5: if arr[left] > pivot and arr[right] 
Step 6: if arr[left] 
Step 7: if arr[right] >= pivot, decrement right

Step 8: goto Step 4

Step 9: swap arr[left] and arr[high]

Step 10: return left

Step 11: End  


  
  
  Code




def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left  pivot and arr[right] = pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low 




  
  
  Time Complexity


Best Case : O(n log n)

Average Case : O(n log n)

Worst Case : O(n^2)