Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1. The subarray is already sorted.
2. Remaining subarray which is unsorted.In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray.

importsysA=[55,30,15,22,9]foriinrange(len(A):min_idx=iforjinrange(i+1,len(A)):ifA[min_idx]>A[j]:min_idx=jA[i],A[min_idx]=A[min_idx],A[i]print("Sorted Array")foriinrange(len(A))print("%d"%A[i])# OutputSortedarray915223055

Bubble Sort

Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they're in wrong order.

defbubbleSort(arr):n=len(arr)foriinrange(n):forjinrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]arr=[73,34,27,12,22,10,110]bubbleSort(arr)print("Sorted array")foriinrange(len(arr)):print("%d",%arr[i])# OutputSortedarray101222273473110

There is also a recursive version of Bubble Sort
How to implement recursive bubble sort?
Recursive bubble sort has no performance or implementation advantages, but can be a good question to check one's understanding of bubble sort and recursion.
Recursion Idea

1. Base Case: If the array size is 1, return.
2. Do One Pass of normal bubble sort. This pass fixes the last element of the current subarray.
3. Recur for all elements except last of the current subarray.

defbubble_sort(listx):fori,numinenumerate(listx):try:iflistx[i+1]<num:listx[i]=listx[i+1]listx[i+1]=numbubble_sort(listx)exceptIndexError:passreturnlistxlistx=[60,36,25,13,23,10,99]bubble_sort(listx)print("Sorted array")foriinrange(0,len(listx)):print(listx[i],end='')# OutputSortedarray10132325366099

Quick Sort

Quick sort is a divide and conquers algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quick sort that pick pivot in different ways.

1. Always pick first element as pivot.
2. Always pick last element as pivot.
3. Pick a random element as pivot.
4. Pick median as pivot.

The key process in quick sort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements before x, and put all greater elements after x. All this should be done in linear time.

defpartition(arr,low,high):i=(low-1)pivot=arr[high]forjinrange(low,high):ifarr[j]<=pivot:i=i+1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[j],arr[i+1]return(i+1)defquickSort(arr,low,high):iflow<high:pi=partition(arr,low,high)quickSort(arr,low,pi-1)quickSort(arr,pi+1,high)arr=[10,8,7,5,9,1]n=len(arr)quickSort(arr,0,n-1)print("Sorted array")foriinrange(n):print("%d"%arr[i])# OutputSortedarray1578910

The recursive quick sort implementation can be optimized in many ways.

1. The recursive quick sort implementation uses last index as pivot. This causes worst-case behaviour on already sorted arrays, which is a commonly occurring case. The problem can be solved by choosing either a random index for the pivot or choosing the middle index of the partition or choosing the median of the first, middle and last element of the partition for the pivot.
2. To reduce the recursion depth, recur first for the smaller half of the array, and use a tail call to recurse into the other.
3. Insertion sort works better for small subarrays. Insertion sort can be used for invocations on such small arrays.

Below is the typical recursive quick sort implementation.

defpartition(arr,low,high):i=(low-1)pivot=arr[high]forjinrange(low,high):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]return(i+1)defquickSort(arr,low,high):iflow<high:pi=partition(arr,low,high)quickSort(arr,low,pi-1)quickSort(arr,pi+1,high)if__name__=='__main__':arr=[4,2,6,9,2]n=len(arr)quickSort(arr,0,n-1)foriinrange(n):print(arr[i],end="")# Output22469

The below mentioned optimizations for recursive quick sort can also be applied to iterative version.

1. Partition process is same in both recursive and interactive. The same techniques to choose optimal pivot can also be applied to iterative version.
2. To reduce the stack size, first push the indexes of smaller half.
3. Use insertion sort when the size reduces below a experimentally calculated threshold.

defpartition(arr,l,h):i=(l-1)x=arr[h]forjinrange(l,h):ifarr[j]<=x:i=i+1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[h]=arr[h],arr[i+1]return(i+1)defquickSortIterative(arr,l,h):size=h-l+1stack=[0]*(size)top=-1top=top+1stack[top]=1top=top+1stack[top]=hwhiletop>=0:h=stack[top]top=top-1l=stack[top]top=top-1p=partition(arr,l,h)ifp-1>1:top=top+1stack[top]=p+1top=top+1stack[top]=harr=[4,3,5,2,1,3,2,3]n=len(arr)quickSortIterative(arr,0,n-1)print("Sorted array")foriinrange(n):print("%d"%arr[i])# OutputSortedarray12233345

Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

definsertionSort(arr):foriinrange(1,len(arr)):key=arr[i]j=i-1whilej>=0andkey<arr[j]:arr[j+1]=arr[j]j-=1arr[j+1]=keyarr=[12,11,13,5,6]insertionSort(arr)foriinrange(len(arr)):print("%d"%arr[i])# Output56111213

How to implement insertion sort recursively?
Recursive insertion sort has no performance or implementation advantages, but can be a good question to check one's understanding of insertion sort and recursion. If we take a closer look at insertion sort algorithm, we keep processed elements sorted and insert new elements one by one in the inserted array.
Recursion Idea

1. Base Case: If array size is 1 or smaller, return.
2. Recursively sort first n-1 elements.
3. Insert last elements at its correct position in sorted array.

definsertionSortRecursive(arr,n):ifn<=1:returninsertionSortRecursive(arr,n-1)'''Insert last elements at its correct position in sorted array'''last=arr[n-1]j=n-2while(j>=0andarr[j]>last):arr[j+1]=arr[j]j=j-1arr[j+1]=lastdefprintArray(arr,n):foriinrange(n):printarr[i],arr=[12,11,13,5,6]insertionSortRecursive(arr,n)printArray(arr,n)# Output56111213

Don't forget to join mytelegram community

P.S: There is going to be several parts of the Top 7 Algorithms series.