What is Sorting?
Sorting is an algorithm that arranges the elements of a list in a certain order, either in ascending or descending. The output is a permutation or reordering of the input.
Classification
Bubble Sort
Selection Sort
Insertion Sort
Shell Sort
Merge Sort
Quick Sort
Tree Sort
Bucket Sort
Radix Sort
1. Bubble Sort
Bubble sort is the simplest sorting algorithm. Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.
The following table shows the first pass of a bubble sort. The shaded items are being compared to see if they are out of order. If there are ݊ items on the list, then there are ݊−1 pairs of items that need to be compared on the first pass. It is important to note that once the largest value in the list is part of a pair, it will continually be moved along until the on is complete. At the start of the first pass, the largest value is now in place. There are ݊−1 items left to sort, meaning that there will be ݊−2 pairs. Since each
pass places the next largest value in place, the total number of passes necessary will be ݊−1. After completing the ݊−1 passes, the smallest item must be in the correct position with no further processing required.
Implementation
//Python
def bubbleSort(A):
swapped = 1
for passnum in range(len(A)-1,0,-1):
if ( swapped == 0 ):
return
for i in range(passnum):
if A[i]>A[i+1]:
A[i], A[i+1] = A[i+1], A[I]
swapped = 1
A = [10,4,43,5,57,91,45,9,7]
bubbleSort(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(1) auxiliary
2.Selection Sort
The selection sort improves on the bubble sort by making only one exchange for every pass on the list. To do this, a selection sort looks for the smallest (or largest) value as it makes a pass and, after completing the pass, places it in the proper location. As with a bubble sort, after the first pass, the largest item is in the correct place.
The following table shows the entire sorting process. At each pass, the largest remaining item is selected and then placed in its proper location. The first pass places 93, the second pass places 77, the third places 55, and so on.
Implementation
def selectionSort(A):
for i in range(len(A)-1,0,-1):
positionOfLargest=0
for j in range(1,i+1):
if A[j]>A[positionOfLargest]:
positionOfLargest = j
A[i], A[positionOfLargest] = A[positionOfLargest], A[I]
A = [10,4,43,5,57,91,45,9,7]
selectionSort(A)
print(A)
Worst-case complexity : O(n^2)
Best case complexity: O(n^2)
Average case complexity: O(n^2)
Worst-case space complexity: O(1) auxiliary
If you enjoyed this article, share it with your friends and colleagues! And we will discuss other sorting techniques in the upcoming blog........
There weren't any rejections. Only sorting.
