Sorting Methods in Arrays

lets first understand what sorting means

sorting means arranging elements in a particular order (mostly ascending or descending)

example

[5, 2, 3, 1] → [1, 2, 3, 5]

there are many ways to sort an array, and each method works differently
why do we need sorting

sorting helps in:

searching faster
organizing data
solving many problems like binary search, merging, etc
types of sorting methods

in this blog, I will go through some common sorting methods

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort

1. Bubble Sort
the bubble sort compares adjacent elements and swaps them if they are not in order, largest element “bubbles” to the end

example
[5, 2, 3]
5 > 2 → swap → [2,5,3]

5 > 3 → swap → [2,3,5]

code

def bubblesort(arr):
    n = len(arr)

    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr

complexity

Time Complexity: O(n²)
Space Complexity: O(1)

2. Selection Sort
selection sort finds the smallest element and puts it in the correct position

example
[5, 3, 2]
smallest = 2 → swap with 5 → [2,3,5]

code

def selectionsort(arr):
    n = len(arr)

    for i in range(n):
        min_index = i

        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

complexity

Time Complexity: O(n²)
Space Complexity: O(1)

3. Insertion Sort
insertion sort builds the sorted array one element at a time
it takes an element and inserts it in the correct position

example
[5, 2, 3]

insert 2 → [2,5]

insert 3 → [2,3,5]

code

def insertionsort(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

    return arr

complexity

Time Complexity: O(n²)
Space Complexity: O(1)

4. Merge Sort
merge sort uses divide and conquer
divide array into halves and sort each half and finally merge them and give them as output

example
[5,2,3,1]

→ split → [5,2] and [3,1]

→ sort → [2,5] and [1,3]

→ merge → [1,2,3,5]

code

def mergesort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])

    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

5. Quick Sort
quick sort picks a pivot and splits array into smaller than pivot, greater than pivot

example

[5,2,3]
pivot = 5

left = [2,3]

right = []

→ [2,3] sorted → [2,3,5]

code

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    left = []
    right = []

    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])

    return quicksort(left) + [pivot] + quicksort(right)