Sorting Algorithm

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 arr

The 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 arr

The 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 merged

The 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.