Extended Euclid algorithm for GCD in Python

Euclid’s recursive program based algorithm to compute GCD (Greatest Common Divisor) is very straightforward. If we want to compute gcd(a,b) and b=0, then return a, otherwise, recursively call the function using a=b and b=a mod b.

Quick Sort Algorithm in Python

Quicksort, aka partition-exchange sort, is a divide and conquer algorithm. It’s an efficient algorithm that takes O(nlogn) time to sort n items (on average). In the worst case, it might take O(n2) time.Quicksort first divides a large list/array into two smaller sub-arrays using a pivot …

Merge Sort Algorithm in Python

Merge sort is a divide and conquer algorithm that works as follows.. If the length of the given list is more than 1, divide it into n sublists using recursion, each containing 1 element because a list containing 1 element is always sorted. Again using …

Bubble Sort Algorithm in Python

Bubble sort, also known as sinking sort, is based on the concept of swapping the adjacent elements of the list/array if they are in the wrong order. As the name suggests, the smaller elements “bubble” to the top of the list. The swapping of the …

Insertion Sort Algorithm in Python

Insertion sort is a very simple sorting algorithm that is based on the swapping of the elements of the list/array. In the swapping process, it checks if the current element is less than the previous elements. If the current element is less than the previous …