Sorting algorithms are one of the fundamental concepts in computer science and data structures and algorithms (DSA). The goal of a sorting algorithm is to rearrange a collection of elements in a specific order. Sorting algorithms are used in various areas of computer science, such as databases, file systems, and scientific simulations.
In this blog post, we will explore some of the most common sorting algorithms used in DSA, and provide Python code snippets as examples.
Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. In a data structure, the comparison operator determines the new order of elements.
Algorithms for sorting can be divided into several types. Among the most popular algorithms are:
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Merge Sort
1. Bubble Sort
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass of the list is repeated until the list is sorted. Here's a Python implementation of the Bubble sort algorithm:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arrThe time complexity of the Bubble sort is O(n^2).
2. Selection Sort
A simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > A[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
The time complexity of the Selection sort is O(n^2).
3. Insertion Sort
Insertion sort is another simple sorting algorithm that builds the final sorted array one item at a time. It iterates through an input array and removes one element per iteration, finds the place the element belongs in the sorted list, and inserts it there. Here's a Python implementation of the Insertion sort algorithm:
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arrThe time complexity of the Insertion sort is O(n^2).
4. Merge Sort
Merge sort is a divide and conquer sorting algorithm that recursively splits the input array into two halves, sorts them, and then merges the sorted halves to produce the final sorted array. Here's a Python implementation of the Merge sort algorithm:
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)
def merge(left_half, right_half):
i = j = 0
merged = []
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
merged.append(left_half[i])
i += 1
else:
merged.append(right_half[j])
j += 1
merged += left_half[i:]
merged += right_half[j:]
return mergedThe time complexity of the Merge sort is O(nlogn).
5. Quick Sort
Quick sort is another divide and conquer sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. Here's a Python implementation of the Quick sort algorithm:
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left_half = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right_half = [x for x in arr if x > pivot]The time complexity of the Quick sort is O(n^2).
Such explained above, there are many more sorting algorithms defined.
You can learn about them and more in the dedicated article on Sorting algorithms.
Comments