Linked List in 15 Minute!!

Definition : Linked list is a data structure used for sorting collection of data.

Properties :

  • Successive elements are connected by pointers.
  • Last element points to NULL.
  • Can grow and shrink in size during execution of a program.
  • Can be made just as long as required.
  • Its does not waste memory space.

Linked List Algorithm using C++ :

Advertisements

Algorithm Complexity Notes!

Best case denotes by Omega notation and represents lower band.

Worst case denotes by Big oh notation and represents upper band.

Average case denotes by theta notation and represents average band.

Heap Sort in 15 minute !

Definition : Heap sort is comparison based sorting algorithm based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

  • A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap.
  • Binary Heap is a Complete Binary Tree, it can be easily represented as array and array based representation is space efficient. If the parent node is stored at index I, the left child can be calculated by  2 * I + 1 and right child by 2 * I + 2.

Heap Sort Algorithm for sorting in increasing order:
1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
3. Repeat above steps until size of heap is greater than 1.

Heap Sort Algorithm

Insertion Sort

Insertion sort uses linear search to find the location of the 1st element in the unsorted list, in the sorted portion of the list. It is an elementary sorting algorithm best used to sort small data sets or insert a new element in the sorted list.

Algorithm:
Insertion sort starts with a sorted list of size 1 and inserts elements one at a time. It continues inserting each successive element into the sorted list so far.

  1. Suppose if the array is sorted till index i then we can sort the array till i+1 by inserting i+1th element in the correct position from 0 to i+1.
  2. The position at which (i+1)th element has to be inserted has to be found by iterating from 0 to i.
  3. As any array is sorted till 0th position (Single element is always sorted) and we know how to expand, we can sort the whole array.
for i ← 1 to length(A) - 1
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for
Insertion Sort Example

Property:
1. Best case performance – When the array is already sorted O(n). Total number of comparisons: N – 1 and total number of exchanges: N – 1.
2. Worst case performance – When the array is sorted in reverse order O(n2). N-1 iterations of comparison and exchanges.
3. Average case performance – O(n2)
4. It is sensitive to the input as the number of comparison and exchanges depends on the input.
5. It does not require any extra space for sorting, hence O(1) extra space.

Insertion Sort in Java :

import java.util.*;
import java.lang.*;
import java.io.*;

class InsertionSort
{
public static void main (String[] args) throws java.lang.Exception
{
int[] input = {4, 2, 9, 6, 23, 12, 34, 10, 5};
insertionSort(input);
}

private static void printNumbers( int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.println( input[i] + “, “);
}
System.out.println(“\n”);
}

public static void insertionSort( int array[]) {

int n = array.length;
for(int j = 1; j < n ; j++) {
int key = array[j];
int i = j – 1;
while( (i> -1) && (array[i]) > key) {
array[i+1] = array[i];
i–;
}
array[i+1] = key;
printNumbers(array);
}
}
}

Link : Insertion-Sort-Algorithm