Sorting Algorithms

Sorting

1. Why do we need to sort?
2. Merge Sort
3. Quick Sort

Why do we need to sort?

Sorting is among the most important, and well studied, of computing problems. Python does have a built in method for sorting a collection but it is very advance and highly optimised, it's known as timsort, even java's inbuilt sorting method uses this algorithm. A programmer should usually depend on built-in sorting functions than rolling out a search algorithm from scratch. But with that being said it is still imperative to have a deep understanding of how sorting algorithms functions as it makes you more and more aware about your program in terms of efficiency and space complexity
We will see and study two of the quicker sorting algorithms, mergesort and quicksort.Both these algorithms work on divide and conquer design pattern.

Merge Sort

Merge sort is a recursive algorithm.It works by splitting the list into half and then calling mergesort on both the halves independently. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list. If the length of list is 1 or if its an empty list, then the list is returned as it is, it is the base case

 
def mergeSort(list):
    if len(list)>1:
        midpoint = len(list)//2
        left = list[:midpoint]
        right = list[midpoint:]

        mergeSort(left)
        mergeSort(right)

        i=0
        j=0
        k=0

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

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

        while j < len(right):
            list[k]=right[j]
            j=j+1
            k=k+1
    return list

Quick Sort

Quick Sort also works on divide and conquer technique to gain the similar advantage that mergesort has.
In a quick sort we first select a pivot value, this can be done by either choosing either the first element or the last element or choosing the median of the middle , first and last element.And then the array is partitioned around the pivot element. For clearer understanding as to how quicksort works, watch this video:

Here is the implementation -->

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

def quickSort(arr,low,high):
    if low < high:
 
        # pi is partitioning index, arr[p] is now
        # at right place
        pi = partition(arr,low,high)
 
        # Separately sort elements before
        # partition and after partition
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
        return arr

More sorting algorithms will be coming up soon!