Insertion Sort?
Insertion sort is a simple and efficient comparison sort. In this algorithm, each iteration removes an element from the input list and inserts it
into the sorted sublist.
Implementation
def insertionSort(A):
for i in range(1, len(A)):
temp = A[i]
k = i
while k > 0 and temp < A[k - 1]:
A[k] = A[k - 1]
k -= 1
A[k] = temp
A = [10,4,43,5,57,91,45,9,7]
insertionSort(A)
print(A)
- Worst-case complexity: O(n^2)
- Best case complexity: O(n)
- Average case complexity: O(n^2)
- Worst-case space complexity: O(n^2) total, O(1) auxiliary
Advantages
- Easy to implement
- Efficient for small data
- Adaptive: If the input list is presorted [may not be complete] then insertions sort takes O(n+d), where is the number of inversions
- Practically more efficient than selection and bubble sorts, even though all of them have O(n^2) worst-case complexity
- Stable: Maintains relative order of input data if the keys are the same
- In-place: It requires only a constant amount of O(1) of additional memory space
- Online: Insertion sort can sort the list as it receives it
Shell Sort?
Shell Sort (also called diminishing increment sort)was invented by Donald Shell. This sorting algorithm is a generalization of insertion sort. Insertion sort works efficiently on input that is already almost sorted. The shell sort is also known as the n-gap insertion sort.
Implementation
def ShellSort(A):
sublistcount = len(A)
while sublistcount > 0:
for startposition in range(sublistcount):
gapInsertionSort(A, startposition, sublistcount)
print ('After increments of size', sublistcount, 'The list is',
A)
sublistcount = sublistcount
def gapInsertionSort(A, start, gap):
for i in range(start + gap, len(A), gap):
currentvalue = A[i]
position = i
while position >= gap and A[position - gap] > currentvalue:
A[position] = A[position - gap]
position = position - gap
A[position] = currentvalue
A = [534,246,933,127,277,321,454,565,220]
ShellSort(A)
print(A)
- Worst-case complexity: O(nlog²n)
- Best case complexity: O(n)
- Average case complexity depends on gap sequence
- Worst-case space complexity: O(n)
Merge Sort?
Merge sort is an example of the divide and conquer strategy. Merge sort first divides the array into equal halves and then combines them in a sorted manner. It is a recursive algorithm that continually splits an array in half. If the array is empty or has one element, it is sorted by definition (the base case).
Implementation
def mergeSort(A):
if len(A) > 1:
mid = len(A)
lefthalf = A[:mid]
righthalf = A[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i = j = k = 0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
A[k] = lefthalf[i]
i = i + 1
else:
A[k] = righthalf[j]
j = j + 1
k = k + 1
while i < len(lefthalf):
A[k] = lefthalf[i]
i = i + 1
k = k + 1
while j < len(righthalf):
A[k] = righthalf[j]
j = j + 1
k = k + 1
A = [534,246,933,127,277,321,454,565,220]
mergeSort(A)
print(A)
- Worst-case complexity: O(nlogn)
- Best case complexity: O(nlogn)
- Average case complexity: O(nlogn)
- Worst-case space complexity: O(nlogn) for runtime stack space and O(݊) for the auxiliary space
Quick Sort?
Quicksort is a famous algorithm among comparison-based sorting algorithms. Like merge sort, quick sort uses the divide-and-conquer technique, and so it's a recursive algorithm. The way that quicksort uses divide-and-conquer is a little different from how merge sort does. The quicksort uses the divide-and-conquer technique to gain the same advantages as the merge sort, while not using additional storage. As a trade-off, however, it is possible that the list may not be divided into half.
Implementation
def quick_sort(A, low, high):
if low < high:
partition_point = partition(A, low, high)
quick_sort(A, low, partition_point - 1)
quick_sort(A, partition_point + 1, high)
def partition(A, low, high):
pivot = A[low]
left = low + 1
right = high
done = False
while not done:
while left <= right and A[left] <= pivot:
left = left + 1
while A[right] >= pivot and right >= left:
right = right - 1
if right < left:
done = True
else:
temp = A[left]
A[left] = A[right]
A[right] = temp
temp = A[low]
A[low] = A[right]
A[right] = temp
return right
A = [50,25,92,16,76,30,43,54,19]
quick_sort(A,0,len(A)-1)
print(A)
- Worst-case complexity: O(n^2)
- Best case complexity: O(nlogn)
- Average case complexity: O(nlogn)
- Worst-case space complexity: O(1)
If you enjoyed this article, share it with your friends and colleagues! And we will discuss interesting techniques in the upcoming blog........
