Sorting Algorithms

Sorting algorithms are a fundamental concept in computer science and are used to organize data in a specific order. There are many different sorting algorithms, each with its own strengths and weaknesses. In this article, we will discuss five popular sorting algorithms: bubble sort, insertion sort, selection sort, merge sort, and quick sort.

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The bubble sort algorithm can be described as follows:

def bubble_sort(arr):
 n = len(arr)
 
 # Traverse through all elements in the array
 for i in range(n):
 
 # Last i elements are already in place
 for j in range(0, n-i-1):
 
 # traverse the array from 0 to n-i-1
 # Swap if the element found is greater
 # than the next element
 if arr[j] > arr[j+1] :
 arr[j], arr[j+1] = arr[j+1], arr[j]
 return arr

The time complexity of bubble sort is O(n²) in the worst and average case, which makes it inefficient for large data sets. However, it has a space complexity of O(1), which means it is a constant space algorithm.

Insertion sort is another simple sorting algorithm that builds the final sorted list one item at a time. It compares an element with the element on its left, and if the left element is larger, it swaps the two elements. This process is repeated until the element is in its correct position. The insertion sort algorithm can be described as follows:

def insertion_sort(arr):
 for i in range(1, len(arr)):
 
 key = arr[i]
 
 # Move elements of arr[0..i-1], that are
 # greater than key, to one position ahead
 # of their current position
 j = i-1
 while j >=0 and key < arr[j] :
 arr[j + 1] = arr[j]
 j -= 1
 arr[j + 1] = key
 return arr

The time complexity of insertion sort is O(n²) in the worst and average case, which makes it inefficient for large data sets. However, it has a space complexity of O(1), which means it is a constant space algorithm.

Selection sort is similar to bubble sort and insertion sort, but it selects the smallest element from the unsorted list and places it at the beginning of the sorted list. The selection sort algorithm can be described as follows:

def selection_sort(arr):
 for i in range(len(arr)):
 # Find the minimum element in remaining
 # unsorted array
 min_idx = i
 for j in range(i+1, len(arr)):
 if arr[min_idx] > arr[j]:
 min_idx = j
 
 # Swap the found minimum element with
 # the first element
 arr[i], arr[min_idx] = arr[min_idx], arr[i]
 return arr

The time complexity of selection sort is O(n²) in the worst and average case, which makes it inefficient for large data sets. However, it has a space complexity of O(1), which means it is a constant space algorithm.

Merge sort is a divide and conquer algorithm that divides the input array into two halves, sorts the two halves separately, and then merges the sorted halves back together. The merge sort algorithm can be described as follows:

def merge_sort(arr):
 if len(arr) > 1:
 mid = len(arr)//2
 L = arr[:mid]
 R = arr[mid:]
 
 merge_sort(L)
 merge_sort(R)
 
 i = j = k = 0
 
 while i < len(L) and j < len(R):
 if L[i] < R[j]:
 arr[k] = L[i]
 i += 1
 else:
 arr[k] = R[j]
 j += 1
 k += 1
 
 while i < len(L):
 arr[k] = L[i]
 i += 1
 k += 1
 
 while j < len(R):
 arr[k] = R[j]
 j += 1
 k += 1
 return arr

The time complexity of merge sort is O(n log n) in the worst and average case, which makes it more efficient than the previous algorithms for large data sets. It also has a space complexity of O(n) which means it requires more space than the previous algorithms.

Quick sort is another divide and conquer algorithm that selects a 'pivot' element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The pivot element is then in its final position, and the sub-arrays are sorted recursively. The quick sort algorithm can be described as follows:

def quick_sort(arr, low, high):
 if low < high:
 pivot_index = partition(arr, low, high)
 quick_sort(arr, low, pivot_index)
 quick_sort(arr, pivot_index + 1, high)
 return arr

def partition(arr, low, high):
 pivot = arr[low]
 left = low + 1
 right = high
 done = False
 while not done:
 while left <= right and arr[left] <= pivot:
 left = left + 1
 while arr[right] >= pivot and right >=left:
 right = right -1
 if right < left:
 done= True
 else:
 arr[left], arr[right] = arr[right], arr[left]
 arr[low], arr[right] = arr[right], arr[low]
 return right

The time complexity of quick sort is O(n log n) in the average case and O(n²) in the worst case, which makes it more efficient than the previous algorithms for large data sets. However, it has a space complexity of O(log n) which means it requires less space than the merge sort algorithm but more space than the previous algorithms.