Heap Sort

Heap sort is a sorting method on Binary Heap.

First things First

All you need to know about heap. 

1. Heap must be a Complete Binary Tree 
2. All trees are either Min Heap or Max Heap
3. Heap sort is an in-place sort algorithm
4. It is not very stable

Here I plan to construct Heap Sort Algorithm on a Min Heap.The Algorithm primarily has two main functions.

1. Heapify Function
2. Heap Sort Function

References from CLRS 

 Parent(i) 1 return(floor(i/2))

 Left (i)    1 return ( 2 * i + 1 )

 Right (i)  1 return ( 2 * i + 2 )

 Property for Max Heap 

    A[ Parent ] >= A[ i ]

 Property for Min Heap

     A[ Parent ] <= A[ i ]

Heapify Function

heapify(int arr[], int n, int i) largest=i l=2*i+1 r=2*i+2 if(l<n arr="" l="">arr[largest]) largest=l if(r<n arr="" r="">arr[largest]) largest=r if(largest!=i) swap(arr[i], arr[largest]) heapify(arr,i,largest)

Heap Sort Function

heapsort(int arr[], int n) for(int i=floor(n/2); i>=0;i--) heapify(arr,n,i) for(int i=n-1; i>=0;i--) swap(arr[0],arr[i]) heapify(arr,i,0)

Deletion of node is done at the root node after swapping it with the last node of the list. Deleting it takes O(1) time complexity.
Worst Case Time Complexity : O(n log n)
Space Complexity : O(n)
Source Code: HeapSort.cpp
References: StudyTonight

Naive Pattern Searching Algorithm

Naive Pattern Search algorithm as the name suggests is a very naive method of searching a pattern. The naive logic is to compare every instance of the pattern with every instance of the text.

Algorithm

for i in range 0 to N-M # Primary Comparison of the # Sample text with Pattern for j in range 0 to M; if text[i+j]!=pat[j] break; # Implies that j loop has traversed # to the last instance of the pattern, # and all comparisons are matching if(j==M) print("Instance found at:"i+1) Where N is the Length of the text and M is the Length of the pattern

Naive algorithm is not an optimized solution because the complexity is O(n^2). We need better and more optimized solutions.

Source Code: NaiveSearchAlgo

Insertion Sort

Insertion Sort algorithm is a sort algorithm which is used to sort an array in a particular order.
It is very less efficient with large lists.

Properties:

1. Stable 
2. O(1) ExtraSpace 
3. O(n^2) comparisons & Swap 
4. Adaptive: O(n) time when nearly sorted
5. Very low overhead

Insertion sort is an algorithm of choice when the data is nearly sorted or when the problem size is small. 

Algorithm

Assume in an array a[1...n] of unsorted elements void insertionSort(int a[],int n) for(i=1;i<n;i++) min=a[i];j=i-1; while(j>=0&&a[j]>min) a[j+1]=a[j];j--; a[j+1]=min;

Example 

The following table shows the steps for sorting the sequence {3, 7, 4, 9, 5, 2, 6, 1}. In each step, the key under consideration is underlined. The key that was moved (or left in place because it was biggest yet considered) in the previous step is shown in bold.

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

References: 1 

Note: To be edited further with a Code for the algorithm