Sorting Algorithms in Computer Science
Sorting algorithms are one of the fundamental concepts in computer science, and they play a vital role in various applications such as data processing, search algorithms, and data analysis. In this blog post, we will discuss different types of sorting algorithms and provide code examples in Python for each algorithm.
Before diving into the different sorting algorithms, it is important to understand some basic concepts of sorting. Sorting is the process of arranging a set of data in a specific order. The order could be ascending or descending, and the data could be in any format such as numbers, characters, or strings.
The efficiency of a sorting algorithm is determined by its time complexity, which is the number of operations the algorithm takes to sort a set of data. There are several time complexities, and the most common ones are O(n^2) and O(nlogn). The best-case scenario for a sorting algorithm is O(n), which means that the algorithm takes linear time to sort the data.
Bubble Sort
Bubble sort is a simple sorting algorithm that compares adjacent elements in a list and swaps them if they are in the wrong order. It repeats this process until the entire list is sorted.
The time complexity of bubble sort is O(n^2) in the worst case scenario, and O(n) in the best case scenario.
Here is the Python code for bubble sort:
def bubble_sort(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]
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)Selection Sort
Selection sort is another simple sorting algorithm that works by selecting the smallest element from the unsorted part of the list and placing it at the beginning of the list. It repeats this process until the entire list is sorted.
The time complexity of selection sort is O(n^2) in the worst case scenario, and O(n^2) in the best case scenario.
Here is the Python code for selection sort:
def selection_sort(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]
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("Sorted array is:", arr)Insertion Sort
Insertion sort is a simple sorting algorithm that works by inserting each element in its proper place in the sorted part of the list. It repeats this process until the entire list is sorted.
The time complexity of insertion sort is O(n^2) in the worst case scenario, and O(n) in the best case scenario.
Here is the Python code for insertion sort:
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("Sorted array is:", arr)Merge Sort
Merge sort is a divide and conquer algorithm that works by dividing the list into two halves, sorting each half separately, and then merging them back together in the correct order.
The time complexity of merge sort is O(nlogn) in all scenarios, making it a very efficient sorting algorithm.
Here is the Python code for merge sort:
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
arr = [64, 34, 25, 12, 22, 11, 90]
merge_sort(arr)
print("Sorted array is:", arr)Quick Sort
Quick sort is a divide and conquer algorithm that works by selecting a pivot element and partitioning the list around the pivot such that all elements less than the pivot are on one side and all elements greater than the pivot are on the other side. It then recursively applies the same process to the two resulting sub-lists.
The time complexity of quick sort is O(n^2) in the worst case scenario, and O(nlogn) in the average case scenario.
Here is the Python code for quick sort:
def partition(arr, low, high):
i = (low-1)
pivot = arr[high]
for j in range(low, high):
if arr[j] <= pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
def quick_sort(arr, low, high):
if len(arr) == 1:
return arr
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
quick_sort(arr, 0, n-1)
print("Sorted array is:", arr)Heap Sort
Heap sort is a sorting algorithm that works by building a heap data structure from the list and then repeatedly extracting the maximum element from the heap and placing it at the end of the list.
The time complexity of heap sort is O(nlogn) in all scenarios, making it an efficient sorting algorithm.
Here is the Python code for heap sort:
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i