## Types Of Sorting Algorithm

There are several types of Sorting as Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort, Radix Sort. Lets get informed what are these? How these work? What are the features of different types of sorting?

## What is Bubble Sort?

Bubble sort is a sorting algorithm that repeatedly steps through the list to be sorted, comparing adjacent items and swapping them if they are in the wrong order.

### How Bubble Sort works?

The bubble sort algorithm works by repeatedly passing through the list to be sorted, comparing adjacent elements and swapping them if they are in the wrong order. At the end of each pass, the largest element will be in its final position, and all of the other elements will have been moved closer to their correct positions.

### Features of bubble sort

• simple and easy to understand
• requires only a small number of comparisons to sort a set of items
• iterative, meaning it can be inefficient on large data sets
• sorts in ascending order, by default

### Bubble sort code examples

``````def bubble_sort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
return alist``````

OR

``````def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr)-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr``````

OR

``````class bubbleSort:
def __init__(self, list):
self.list = list
self.size = len(list)
self.swap = 0
self.comparison = 0
def sort(self):
for i in range(self.size):
for j in range(self.size - i - 1):
self.comparison += 1
if self.list[j] > self.list[j + 1]:
self.swap += 1
self.list[j], self.list[j + 1] = self.list[j + 1], self.list[j]
return self.list
def getSwap(self):
return self.swap
def getComparison(self):
return self.comparison``````

OR

``````class bubbleSort:
def __init__(self, list):
self.list = list
def sort(self):
for i in range(len(self.list)):
for j in range(len(self.list)-1):
if self.list[j] > self.list[j+1]:
self.list[j], self.list[j+1] = self.list[j+1], self.list[j]
return self.list``````

OR

``````class bubbleSort:
def __init__(self, list):
self.list = list
def bubbleSort(self):
for i in range(len(self.list)-1, 0, -1):
for j in range(i):
if self.list[j] > self.list[j+1]:
temp = self.list[j]
self.list[j] = self.list[j+1]
self.list[j+1] = temp
return self.list``````

## What is Insertion Sort?

Insertion sort is a sorting algorithm that builds a sorted list from an unordered list by inserting elements one at a time.

### How Insertion Sort works?

The insertion sort algorithm works by taking a list of items and inserting them one at a time into a sorted list. It does this by finding the position of the item to be inserted and then inserting it into the list at that position.

### Features of Insertion Sort

• It is a simple algorithm.
• It is a stable sorting algorithm.
• It is a comparison-based sorting algorithm.
• It is a in-place sorting algorithm.
• It is a tail-recursive algorithm.
• It is a linear-time algorithm.

### Insertion sort code examples

``````def insertion_sort(lst):
for i in range(1, len(lst)):
j = i
while j > 0 and lst[j] < lst[j - 1]:
lst[j], lst[j - 1] = lst[j - 1], lst[j]
j -= 1
return lst``````

OR

``````def insertion_sort(lst):
for i in range(1, len(lst)):
j = i
while j > 0 and lst[j-1] > lst[j]:
lst[j-1], lst[j] = lst[j], lst[j-1]
j -= 1
return lst``````

OR

``````class insertionSort:
def __init__(self, list):
self.list = list
self.length = len(list)

def sort(self):
for i in range(1, self.length):
j = i
while j > 0 and self.list[j] < self.list[j-1]:
self.list[j], self.list[j-1] = self.list[j-1], self.list[j]
j -= 1
return self.list``````

OR

``````class insertionSort:
def __init__(self, list):
self.list = list
self.length = len(list)
self.swap_count = 0
self.comparison_count = 0
def sort(self):
for i in range(1, self.length):
j = i
while j > 0 and self.list[j] < self.list[j-1]:
self.swap(j, j-1)
j -= 1
self.swap_count += 1
self.comparison_count += 1
def swap(self, i, j):
temp = self.list[i]
self.list[i] = self.list[j]
self.list[j] = temp
def get_swap_count(self):
return self.swap_count
def get_comparison_count(self):
return self.comparison_count``````

## What is Selection Sort?

Selection Sort is a sorting algorithm that takes an unsorted list of items and organizes them in ascending order. It does this by selecting the smallest item from the list and placing it at the beginning of the list. It then repeats this process for the remaining items in the list.

### How Selection Sort works?

In selection sort, the algorithm starts by comparing the first two elements in the list and selects the smaller one to be placed in the first position. It then compares the next two elements and selects the smaller one to be placed in second position and so on.

### Features of Selection Sort

• Easy to understand
• O(n2) time complexity
• Can be used for any data type
• Requires a loop
• Sorting is stable

### Selection sort code examples

``````def selection_sort(lst):
for i in range(len(lst)):
min_index = i
for j in range(i+1, len(lst)):
if lst[j] < lst[min_index]:
min_index = j
lst[i], lst[min_index] = lst[min_index], lst[i]
return lst``````

OR

``````class selectionsort:
def __init__(self, list):
self.list = list

def sort(self):
for i in range(len(self.list)):
min = i
for j in range(i+1, len(self.list)):
if self.list[j] < self.list[min]:
min = j
self.list[i], self.list[min] = self.list[min], self.list[i]
return self.list``````

## What is Merge Sort?

Merge sort is a comparison-based sorting algorithm that sorts data using the divide and conquer technique. The algorithm splits the data set into halves, sorts each half, and then merges the two sorted halves.

### How Merge Sort works?

The merge sort algorithm starts by dividing the input data set into two equal parts. It then proceeds to sort each part separately. After that, the two sorted parts are merged together to form the sorted data set.

### Features of Merge Sort

• Merge Sort is a comparison-based sorting algorithm.
• Merge Sort is a divide and conquer algorithm.
• Merge Sort is a stable sorting algorithm.
• Merge Sort is an in-place sorting algorithm.
• Merge Sort is a serial algorithm.

### Merge sort code examples

``````def merge_sort(a):
if len(a) > 1:
mid = len(a) // 2
left = a[:mid]
right = a[mid:]

merge_sort(left)
merge_sort(right)

i = j = k = 0

while i < len(left) and j < len(right):
if left[i] < right[j]:
a[k] = left[i]
i += 1
else:
a[k] = right[j]
j += 1
k += 1

while i < len(left):
a[k] = left[i]
i += 1
k += 1

while j < len(right):
a[k] = right[j]
j += 1
k += 1``````

OR

``````def merge_sort(alist):
if len(alist) > 1:
mid = len(alist) // 2
lefthalf = alist[:mid]
righthalf = alist[mid:]

merge_sort(lefthalf)
merge_sort(righthalf)

i = 0
j = 0
k = 0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k] = lefthalf[i]
i = i + 1
else:
alist[k] = righthalf[j]
j = j + 1
k = k + 1

while i < len(lefthalf):
alist[k] = lefthalf[i]
i = i + 1
k = k + 1

while j < len(righthalf):
alist[k] = righthalf[j]
j = j + 1
k = k + 1
return alist``````

OR

``````class mergesort:
def __init__(self, array):
self.array = array
self.length = len(array)
self.mergesort()

def mergesort(self):
if self.length > 1:
mid = self.length // 2
left = self.array[:mid]
right = self.array[mid:]
left = mergesort(left)
right = mergesort(right)
self.array = self.merge(left.array, right.array)

def merge(self, left, right):
result = []
while len(left) > 0 and len(right) > 0:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if len(left) > 0:
result += left
if len(right) > 0:
result += right
return result``````

OR

``````class mergesort:
def __init__(self, array):
self.array = array
self.length = len(array)
self.merge_sort(self.array, 0, self.length - 1)

def merge_sort(self, array, start, end):
if start < end:
mid = (start + end) // 2
self.merge_sort(array, start, mid)
self.merge_sort(array, mid + 1, end)
self.merge(array, start, mid, end)

def merge(self, array, start, mid, end):
left = array[start:mid + 1]
right = array[mid + 1:end + 1]
i = 0
j = 0
k = start
while i < len(left) and j < len(right):
if left[i] <= right[j]:
array[k] = left[i]
i += 1
else:
array[k] = right[j]
j += 1
k += 1
while i < len(left):
array[k] = left[i]
i += 1
k += 1
while j < len(right):
array[k] = right[j]
j += 1
k += 1``````

OR

``````class mergesort:
def __init__(self, data):
self.data = data
self.length = len(data)
self.merge_sort(self.data, 0, self.length - 1)
def merge_sort(self, data, left, right):
if left < right:
mid = (left + right) // 2
self.merge_sort(data, left, mid)
self.merge_sort(data, mid + 1, right)
self.merge(data, left, mid, right)
def merge(self, data, left, mid, right):
left_data = data[left:mid + 1]
right_data = data[mid + 1:right + 1]
left_data.append(999999999) # sentinel value
right_data.append(999999999) # sentinel value
i = j = 0
for k in range(left, right + 1):
if left_data[i] <= right_data[j]:
data[k] = left_data[i]
i += 1
else:
data[k] = right_data[j]
j += 1``````

## What is Quick Sort?

Quick sort is a sorting algorithm which partitions the input array into two arrays: one larger than the Kth element, and one smaller. It then recursively sorts the two arrays.

### How Quick Sort works?

In the quick sort algorithm, the partitioning is done recursively. The leftmost element in the sublist is compared with the rightmost element. If they are equal, the sublist is sorted. If the leftmost element is less than the rightmost element, the leftmost element is placed in the new sublist and the rightmost element is placed in the old sublist. If the leftmost element is greater than the rightmost element, the rightmost element is placed in the new sublist and the leftmost element is placed in the old sublist.

### Features of Quick Sort

• Quick sort is a divide and conquer algorithm
• The algorithm partitions the input array into two parts: the leftmost subarray and the rightmost subarray
• The leftmost subarray is then sorted using a recursive call to quick sort
• The rightmost subarray is not sorted and is returned to the caller
• The partitioning step is repeated until the entire array is sorted

### Quick sort code examples

``````def quick_sort(alist):
quick_sort_helper(alist, 0, len(alist) - 1)``````

OR

``````def quick_sort(array):
if len(array) <= 1:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)``````

OR

``````class quicksort:
def __init__(self, array):
self.array = array
self.length = len(array)

def partition(self, low, high):
pivot = self.array[high]
i = low - 1
for j in range(low, high):
if self.array[j] <= pivot:
i += 1
self.array[i], self.array[j] = self.array[j], self.array[i]
self.array[i + 1], self.array[high] = self.array[high], self.array[i + 1]
return i + 1

def quick_sort(self, low, high):
if low < high:
pi = self.partition(low, high)
self.quick_sort(low, pi - 1)
self.quick_sort(pi + 1, high)

def print_array(self):
print(self.array)``````

OR

``````class quicksort:
def __init__(self, array):
self.array = array
self.length = len(array)
self.quicksort(0, self.length - 1)

def quicksort(self, start, end):
if start < end:
pivot = self.partition(start, end)
self.quicksort(start, pivot - 1)
self.quicksort(pivot + 1, end)

def partition(self, start, end):
pivot = self.array[end]
i = start - 1
for j in range(start, end):
if self.array[j] <= pivot:
i += 1
self.swap(i, j)
self.swap(i + 1, end)
return i + 1

def swap(self, i, j):
self.array[i], self.array[j] = self.array[j], self.array[i]``````

## What is Heap Sort?

Heap sort is a sorting algorithm that works by first creating a heap out of the unsorted list, and then iteratively removing the largest element from the heap and inserting it into the correct position in the sorted list.

### How Heap Sort works?

Heap sorting is a comparison-based sorting algorithm. It works by first constructing a heap out of the input elements. The root node of the heap is then compared with the last node of the heap. If the root node is greater than the last node, the last node is replaced with the root node. If the root node is less than the last node, the last node is left unchanged. This process is then repeated for the children of the last node, and so on, until the entire heap is sorted.

Simply, the algorithm starts by sorting the first element in the array. It then compares the first two elements and inserts the larger element into the array at the appropriate position. The algorithm then compares the last two elements and inserts the larger element into the array at the appropriate position. The process then repeats until the entire array is sorted.

### Features of Heap Sort

• Heap Sort is a stable sorting algorithm.
• Heap Sort is an in-place sorting algorithm.
• Heap Sort takes linear time to sort an array of n elements.

### Heap sort code examples

``````def heap_sort(a):
n = len(a)
for i in range(n, -1, -1):
for i in range(n - 1, 0, -1):
a[i], a[0] = a[0], a[i]

OR

``````def heap_sort(arr):
for i in range(len(arr)):
heapify(arr, i)
for i in range(len(arr) - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, 0, i - 1)
return arr``````

OR

``````class heapsort:
def __init__(self, array):
self.array = array
self.heapSize = len(array)
self.buildHeap()
self.sort()

def buildHeap(self):
for i in range(self.heapSize//2, -1, -1):
self.heapify(i)

def heapify(self, i):
left = 2*i + 1
right = 2*i + 2
largest = i
if left < self.heapSize and self.array[left] > self.array[largest]:
largest = left
if right < self.heapSize and self.array[right] > self.array[largest]:
largest = right
if largest != i:
self.array[i], self.array[largest] = self.array[largest], self.array[i]
self.heapify(largest)

def sort(self):
for i in range(self.heapSize-1, 0, -1):
self.array[0], self.array[i] = self.array[i], self.array[0]
self.heapSize -= 1
self.heapify(0)``````

Radix Sort is a sorting algorithm that sorts elements in a list according to the numerical value of each element’s digit.

Radix Sort is a sorting algorithm that works by dividing an input into a series of buckets and sorting each bucket independently.

• It is a comparison-based sorting algorithm.
• It is a stable sorting algorithm.
• It is a Divide-and-Conquer algorithm.
• It is an in-place sorting algorithm.
• It is a deterministic sorting algorithm.
• It is a priority queue-based sorting algorithm.

``````def Radix_Sort(A, d):
# A is the list to be sorted
# d is the number of digits
# initialize the buckets
buckets = [[] for _ in range(10)]
# initialize the index
index = 1
# loop until the index is greater than the number of digits
while index <= d:
# loop through the list
for i in range(len(A)):
# get the digit at the index
digit = (A[i] // (10 ** (index - 1))) % 10
# append the number to the bucket
buckets[digit].append(A[i])
# empty the list
A = []
# loop through the buckets
for i in range(10):
# loop through the bucket
for j in range(len(buckets[i])):
# append the number to the list
A.append(buckets[i][j])
# empty the bucket
buckets[i] = []
# increase the index
index += 1
return A``````

OR

``````class RadixSort:
def __init__(self, arr):
self.arr = arr
self.max = max(arr)
self.digit = 1
self.bucket = [[] for i in range(10)]

def sort(self):
while self.max // self.digit > 0:
for i in self.arr:
self.bucket[i // (self.digit * 10) % 10].append(i)
self.arr.clear()
for i in self.bucket:
self.arr.extend(i)
self.digit *= 10
self.bucket = [[] for i in range(10)]
return self.arr``````

OR

``````class RadixSort:
def __init__(self):
self.n = 0
self.digit = 1
self.output = [0] * self.n
self.temp = [0] * self.n

def getDigit(self, num, digit):

def sort(self, A):
for i in range(self.n):
self.temp[i] = A[i]
for i in range(self.n):
self.output[i] = self.temp[i]
for i in range(self.n):
self.count[self.getDigit(self.output[i], self.digit)] += 1