# Mastering Sorting Algorithms with Python: A Comprehensive Guide for Data Scientists and Developers

## Exploring the Most Popular Sorting Algorithms and Their Performance Characteristics for Efficient Data Manipulation

# 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 algorithm gets its name from the way smaller elements “bubble” to the top of the list.

Here is the implementation of bubble sort in Python:

`def bubble_sort(arr):`

swapped = False # If already sorted, skip

n = len(arr)

# track the number of passes through the array.

for i in range(n):

# to compare adjacent elements in the array.

for j in range(0, n - i - 1):

if arr[j] > arr[j + 1]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

swapped = True

if swapped == False: # already sorted

break

return arr

Bubble sort has a time complexity of **O(n²).**

# Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time.

`def insertion_sort(arr):`

for i in range(len(arr)-1):

# j is always i + 1

j = i + 1

# internal loop for j>0 and j moves from right to left

while(j > 0):

if arr[j] < arr[j-1]:

arr[j], arr[j-1] = arr[j-1], arr[j]

j = j - 1

# if j = 0, we break the internal loop

else:

break

return arr

Insertion sort has a time complexity of **O(n²)** in the worst-case scenario, making it inefficient for large arrays.

# Cyclic Sort

Cyclic sort is an in-place and linear-time sorting algorithm that finds the minimum unsorted element and swaps it with the element at its correct position.

Here is the implementation of the cyclic sort in Python:

`def cyclic_sort(arr):`

i = 0

# keep track of the progress through the array.

while i < len(arr):

j = arr[i] - 1 # correct position

if arr[i] != arr[j]:

arr[i], arr[j] = arr[j], arr[i] # swap if incorrect position

else:

i += 1

return arr

Cyclic sort has a time complexity of **O(n)**, making it more efficient than other sorting algorithms such as bubble sort or insertion sort.

# Merge Sort

Merge sort is a divide-and-conquer algorithm that sorts an array by dividing it into smaller sub-arrays and then merging them in a sorted manner.

`def merge_sort(arr):`

if len(arr) > 1:

# array is divided into two halves

mid = len(arr) // 2

left_half = arr[:mid]

right_half = arr[mid:]

# two halves are then sorted recursively

merge_sort(left_half)

merge_sort(right_half)

# two sorted halves are then merged back together in a sorted manner

i = j = k = 0

while i < len(left_half) and j < len(right_half):

# adds the smaller value to the result array arr.

if left_half[i] < right_half[j]:

arr[k] = left_half[i]

i += 1

else:

arr[k] = right_half[j]

j += 1

k += 1

# add any remaining values from the left and right halves

while i < len(left_half):

arr[k] = left_half[i]

i += 1

k += 1

while j < len(right_half):

arr[k] = right_half[j]

j += 1

k += 1

return arr

Merge sort has a time complexity of **O(n log n).**

# Quick Sort

Quick sort is a divide-and-conquer algorithm that sorts an array by choosing a “pivot” element and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

` def quickSort(nums):`

sort(nums, 0, len(nums) - 1)

return nums

# takes the array, lowest value and highest value

def sort(nums, low, high):

if low >= high:

return

s, e = low, high

# get the mid of the array

m = int(s + (e - s) / 2)

# get the mid element

p = nums[m]

# while the start is less than or equal to the end

while s <= e:

# if the array is sorted, it won't swap

# i.e the the left half is already sorted

while nums[s] < p:

s += 1

# same for the other half

while nums[e] > p:

e -= 1

# for start < end index, we swap them

if s <= e:

nums[s], nums[e] = nums[e], nums[s]

s += 1

e -= 1

# Now that the pivot is at correct index, we sort the two halfs

sort(nums, low, e)

sort(nums, s, high)

Quick sort has an average time complexity of **O(n log n)**

That’s all folks!

Happy Coding 💛