Sorting¶
Sl No. |
Algorithm |
Worst Time |
Average Time |
Best Time |
Memory |
Stability |
---|---|---|---|---|---|---|
1 |
Bubble Sort |
\[n^2\]
|
\[n^2\]
|
\[n\]
|
\[1\]
|
Stable |
2 |
Selection Sort |
\[n^2\]
|
\[n^2\]
|
\[n^2\]
|
\[1\]
|
Unstable |
3 |
Insertion Sort |
\[n^2\]
|
\[n^2\]
|
\[n^2\]
|
\[1\]
|
Stable |
4 |
Merge Sort |
\[n * log(n)\]
|
\[n * log(n)\]
|
\[n * log(n)\]
|
\[n\]
|
Stable |
5 |
Quick Sort |
\[n * log(n)\]
|
\[n * log(n)\]
|
\[n^2\]
|
\[n * log(n)\]
|
Unstable |
Note
Stable : Relative position of equal elements after sorting remains same.
In-place Sorting : Sorting Input elements without having backup, thus unsorted form is lost.
Bubble Sort¶
Description¶
Important
- TIme Complexity
Worst Case: \(n^2\)
Average Case: \(n^2\)
Best Case: \(n\)
Python¶
def bubble_sort(data):
for i in range(len(data) - 1):
for j in range(0, len(data) - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
return data
Implementation¶
Selection Sort¶
Description¶
Important
- TIme Complexity
Worst Case: \(n^2\)
Average Case: \(n^2\)
Best Case: \(n^2\)
Python¶
def selection_sort(data):
for i in range(len(data)):
min_index = i
for j in range(i + 1, len(data)):
if data[min_index] > data[j]:
min_index = j
data[i], data[min_index] = data[min_index], data[i]
return data
Implementation¶
Insertion Sort¶
Description¶
Tip
Insertion sort is used when number of elements is small.
It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.
Important
- TIme Complexity
Worst Case: \(n^2\)
Average Case: \(n^2\)
Best Case: \(n^2\)
Python¶
def insertion_sort(data):
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and key < data[j]:
data[j + 1] = data[j]
j -= 1
data[j + 1] = key
return data
Implementation¶
Merge Sort¶
Description¶
Important
- TIme Complexity
Worst Case: \(n * log(n)\)
Average Case: \(n * log(n)\)
Best Case: \(n * log(n)\)
Python¶
def merge_sort(data):
if len(data) > 1:
mid = len(data) // 2
left = data[:mid]
right = data[mid:]
merge_sort(left)
merge_sort(right)
i = 0
j = 0
k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
data[k] = left[i]
i += 1
else:
data[k] = right[j]
j += 1
k += 1
while i < len(left):
data[k] = left[i]
i += 1
k += 1
while j < len(right):
data[k] = right[j]
j += 1
k += 1
Implementation¶
Quick Sort¶
Description¶
Important
- TIme Complexity
Worst Case: \(n * log(n)\)
Average Case: \(n * log(n)\)
Best Case: \(n^2\)
Python¶
Algorithm for partition¶
def partition(data, low, high):
pivot = data[high]
i = low # To keep the index of element smaller than pivot
j = low # To keep the index of element greater than pivot
while j < high:
if data[j] < pivot:
data[j], data[i] = data[i], data[j]
i += 1
j += 1
data[i], data[high] = data[high], data[i]
return i
Recursive Algorithm for quicksort¶
def quick_sort(data, low, high):
if low < high:
pivot = partition(data, low, high)
quick_sort(data, low, pivot - 1)
quick_sort(data, pivot + 1, high)