Find kth largest or smallest element in unsorted array

Question :Find K^th element(largest/smallest) in an unsorted array

Solution: Using pivot finding method of QuickSort we can find K^th element's position it will give K^th smallest element, to find K^th largest modify the program to find smallest from the end. Following program finds K^th largest in an un-sorterd array:

 
/**
 * @author Vikky.Agrawal
 *
 */
public class LargestK {

 int arr[];
 int length;
 
 LargestK(){
  arr=new int[]{16,17,18,4,12,9,5,1};
  this.length=arr.length;
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {
  new LargestK().operate();
 }
 
 
 public void operate(){
  int k=1;
  System.out.println(k+" th largest in array : "+findKthLargest(arr, 0, length-1, length-k));
  
 }
 
 
 //Using QuickSort's pivot finding method
 public int findKthLargest(int[] arr, int p, int q, int k) {

  if(p==q){
   if(k==p){
    return arr[p];
   }else{
    return -1;
   }
  } 
  
  else if (p < q) {
   int pivot = findPivot(arr, p, q);
   
   if (pivot == k)
    return arr[pivot];
   if (pivot > k) {
    return findKthLargest(arr, 0, pivot-1, k);
   } else {
    return findKthLargest(arr, pivot + 1, length-1, k);
   }
  }else{
   return -1;
  }
  
 }
 
 public int findPivot(int[] arr, int p, int r){
  
  int x=arr[r];
  int i=p-1; 
  
  for(int j=p ;j<r; j++){
   if(arr[j]<= x){
    i++;
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
   }
  }  
  
  arr[r]=arr[i+1];
  arr[i+1]=x;
  return i+1;
 }
}

Complexity Analysis:
Time required to find pivot = O(n)
In average cases only half of the array will be searched(assuming pivot will divide the array in half), time required to divide will be T(n/2).
Hence total time to find K^th largest T(n) = T(n/2)+O(n) = O(n) average case.
In worst case pivot might divide the array in 1 an n-1 always, hence worst case time will be T(n) = T(n-1)+O(n) = O(n²).

Find minimum in a stack

Question: Design a data structure where it supports LIFO and a function min which gives min of the elements present at the moment in that structure.

Solution: To implement LIFO we can use Stack data structure, but to maintain current minimum we can use auxiliary space, here I am implementing it using another auxiliary stack. Initialize auxiliary stack with first element pushed in the stack as it would be the minimum at present. Now whenever a new element is pushed we check whether it is less than top element in auxiliary stack?if this condition satisfies then push it to auxiliary stack too. While popping through the stack, again check whether top of auxiliary is same as popped element, then pop from auxiliary also. At any time top of auxiliary will give min of the elements present in the stack.

Following program implements above logic.

/**
 * @author vikky.agrawal
 * Min should return minimum of elements present at the moment in stack.
 * 
 */

public class StackImpl {

 Node top =null; 
 
 public static void main(String[] arg){ 
   
  //Find min implementation
  
  StackImpl stack1=new StackImpl();
  StackImpl auxiliary=new StackImpl();
  
  for (int i = 1; i < 10; i++) {
   int data=(int) (Math.random() * 100);
   stack1.push(data);
   
   if(auxiliary.top==null){
    auxiliary.push(data);
   }else{
    int temp=auxiliary.peek();
    if(temp>0 && temp>data){
     auxiliary.push(data);
    }
   }
   
  }
  System.out.println("Original stack :");
  stack1.printStack();
  
  System.out.println("Auxiliary stack : ");
  auxiliary.printStack();
  
  //System.out.println("Min element right now is :"+auxiliary.peek());
  
  for (int i = 1; i < 5; i++) {
   
   int popped=stack1.pop();
   
   System.out.println("Popped element is :"+popped);
   
   if(auxiliary.peek()== popped){
    auxiliary.pop();
   }   
            System.out.println("Next Min element right now is :"+auxiliary.peek()); 
  }
 }
  
 /**
  * Helper functions for stack operations
  */
 
 public void push(int data){
  if(top==null){
   top=new Node(data);
  }else{
   Node temp=new Node(data);
   temp.setLink(top);
   top=temp;
  }
 }
 
 public int pop(){
  if(top==null){
   return -1;
  }else{
   Node temp=top;
   top=top.getLink();
   return temp.getData();
  }
 }
 
 public int peek(){
  if(top!=null){
   return top.getData();
  }else{
   return -1;
  }
 }
 
 
 public boolean isEmpty(){
  if(top==null)
   return true;
  return false;
 }
 
 
 public int size(){
  int size=0;
  Node temp=top;
  
  while(temp!=null){
   size++;
   temp=temp.getLink();
  }
  return size;
 }
 
 public void printStack(){
  Node temp=top;
  System.out.print("Top->\n");
  while(temp!=null){
   System.out.println(temp.getData()+"\n|");
   temp=temp.getLink();
  }
  System.out.println("/null");
 }
 
 /**
  * static inner class to be used for Stack Data Structure
  */
  static class Node{
   private int data;
   private Node link;    
      
      Node(){
            
      }
      
      Node(int data){
       //mergedList=new Node();
          this.setData(data);
          this.setLink(null);       
      }
      
      public int getData(){
          return this.data;
      }
        
      public Node getLink(){
          return this.link;
      }
      
      public void setData(int data){
          this.data=data;
      }       
      
      public void setLink(Node link){
          this.link=link;
      }  
 }
 
 
}

Counting sort in java

Any sorting technique which includes comparison of elements requires at least Ω(n logn) time if no extra space is used.
To sort an array in linear time that is O(n) we need extra space.

Counting sort can be used to sort an array in linear time while using some extra space.
But there are few assumptions while sorting using counting sort:
1. Array A is input array, Array B is output(sorted array), Array C is auxiliary space(C[0..k])
2. Array A contains elements in the range of 0..k where k is max element, so we need auxiliary array C with space[0..k]
3. Hence complexity becomes O(n+k).

Following program implements Counting sort in java.

/**
 * @author vikky.agrawal
 *
 */
public class CountingSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
         CountingSort obj=new  CountingSort();
         int a[]=new int[]{7,2,6,9,1,2,8,0,5,4,2,3,1,6};
         obj.countingSort(a, 9);
        
    }
    
/**
 * Algorithm
 * COUNTING-SORT.(A;B;k)
 * A[1...n] input array
 * B[1...n] output array
 * C[0...k] auxiliary array(k is the max element)
 * 
 * 1 let C[0..k]be a new array
 * 2 for i =0 to k
 * 3 C[i]=0;
 * 4 for j=1 to A.length
 * 5 C[ A[j] ]=C[ A[j] ]+1;
 * 6 // C[i]now contains the number of elements equal to i.
 * 7 for i= 1 to k
 * 8 C[i]=C[i]+c[i-1];
 * 9 //C[i] now contains the number of elements less than or equal to i.
 * 10 for j= A.length down to 1
 * 11 B[C[A[j]]]=A[j];
 * 12 C[A[j]]=C[A[j]]-1;
*/
    
    /**
     * Sorting in linear time with auxiliary space O(n+k)
     */
    public int[] countingSort(int[] a,int k){
        
        
        System.out.println("Input array :");
        printArray(a);
        
        int[] b=new int[a.length];
        int[] c=new int[k+1];
        
        for(int i=0; i < a.length;i++){
            c[a[i]]=c[a[i]]+1;
        }
        // C[i] now contains the number of elements equal to i. if c[5]=3 then there are 3 5's
        
        
        //sutract 1 to make array index from 0;
        c[0]=c[0]-1;
        for(int i=1; i < c.length;i++){
            c[i]=c[i]+c[i-1];
        }
        
        //C[i] now contains the number of elements less than or equal to i.
        //if c[1]=3 then there are 3 elements which are less than or equal to 1. 
        
        for(int j=a.length-1; j&gt;=0 ;j--){
            b [ c[a[j] ]]=a[j];     //c[j] contains actual location of a[j]; 
            c[a[j]]=c[a[j]]-1;
        }
        
        System.out.println("\nSorted array :");
        printArray(b);        
        
        return b;
    }
    
    public void printArray(int[] arr){
        for (int a : arr) {
            System.out.print(a + " ");
        }    
        System.out.println();
    }

}

Complexity analysis of counting sort:
Since there is no comparison involved in counting sort, there are no inner loops.
So a total running time of O(n) is required for input array and O(k) time required for auxiliary array.
Total running time could be estimated by O(n+k); which is a linear function hence counting sort runs in linear time.

Heap sort in java

Here I am taking example of MaxHeap, a minheap can be implemented and sorted in the same way after some modifications. So wherever a heap mentioned in this post it will refer to MaxHeap.

Heap property:In a Heap data structure left and right node contains value less than the parent node.
for any indice i
leftchild  : 2i + 1
rightchild : 2i + 2
parent     : floor((i − 1)/2

To build a heap we use heapify function which runs in O(logn) time, and total time taken to build a heap happens to be O(n).

To sort a heap, we remove the root node which must be maximum, and add it at the end of array. After that we use heapify function on the array but ignoring index at which this element is added.
Repeating this process for 0 to array.length sorts array.

Following program implements Heap sort in java.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

/**
 * @author vikky.agrawal
 * 
 */
public class HeapSort {

    
    ArrayList<Integer> array;

    HeapSort() {
        array = new ArrayList<Integer>();
    }
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        new HeapSort().operate();
    }

    public void operate(){
        for (int i = 0; i < 11; i++) {
            array.add(((int) (Math.random() * 100)));
        }

        System.out.println("Array before maxheapify :");
        printArray();
        
        buildMaxHeap();
        
        System.out.println("Array after max heapify");
        printArray();
        
        this.heapSort();        
        
        System.out.println("\nArray after Heap Sort");
        
        printArray();
        System.out.println("\nIs Array sorted now ? " +isSorted());
    }
    
    /**
     * Heapify takes O(log n) / O(height)
     */

    public void heapify(ArrayList<Integer> array, int index,int size) {
        
            
        int left = this.getLeft(index);
        int right = this.getRight(index);

        int largest = array.get(index);
        int temp = index;

        if (left != -1 && array.get(left) > largest && left<size) {
            largest = array.get(left);
            temp = left;
        }

        if (right != -1 && array.get(right) > largest && right <size) {
            largest = array.get(right);
            temp = right;
        }
        
        if (temp != index) {
            int tempo = array.get(index);
            array.add(index, array.get(temp));
            array.remove(index+1);
            array.add(temp, tempo);
            array.remove(temp+1);
        
            if(temp < size / 2){
                heapify(array,temp,size);
            }
        }
        
    }

    /**
     * Building a Max Heap takes O(n) time
     */
    public void buildMaxHeap() {
        int size=array.size();
        for (int i = ( size / 2)-1; i >= 0; i--) {
             this.heapify(array, i,size);
        }
    }
    
    /**
     * Heap sort takes O(n logn) overall;
     */
    public void heapSort(){
        
        int size=array.size();
        int index=size-1;
        
        for (int i = 0 ; i <size; i++) {    
            int data=array.remove(0);
            array.add(index, data);                    
            
            for (int j = ( size / 2)-1; j >= 0; j--) {
                 this.heapify(array, j,index);
            }
            index--;             
        }
        
        //Reverse the array for sorted version (runs in linear time)
        Collections.reverse(array);
    }
    
    /**
     * Helper functions for Heap
     */
    public int getLeft(int index) {
        if ((index * 2) + 1 < array.size()) {
            return (index * 2) + 1;
        } else {
            return -1;
        }
    }

    public int getRight(int index) {
        if ((index * 2) + 2 < array.size()) {
            return (index * 2) + 2;
        } else {
            return -1;
        }
    }

    public int getParent(int index) {
        if (index < array.size()) {
            if (index % 2 == 0) {
                return (index / 2) - 1;
            } else {
                return index / 2;
            }
        } else
            return -1;
    }

    public void printArray(){
        Iterator<Integer> itr = array.iterator();
        while (itr.hasNext()) {
            System.out.print(itr.next() + " ");
        }
        System.out.println();
    }
    
    public boolean isSorted(){
        
        for(int i=1;i<array.size();i++){
            if(array.get(i) > array.get(i-1)){
                return false;
            }
        }
        return true;
    }

}

Complexity analysis:
Complexity of Heap sort is O(n logn)
To build a heap it takes time: O(n), and for each element we call heapify function which takes O(logn), hence total time taken to sort the array will be: O(n logn).

Facts:
1. Heap sort is not a stable sort(order of same elements in sorted array might change)
2. Merge Sort requires Ω(n) auxiliary space(for merging), but heapsort requires only a constant space.
3. Heapsort typically runs faster in practice on machines with small or slow data caches.

Quick Sort in Java

Quick sort works on the principle of divide and conquer.
Divide the list in 2 sub-lists, find a pivot element such that its actual position divides the list further in 2 lists.
So the pivot element resides at its actual position and then recursively find location of other elements. At the end of processing each element will get its actual(sorted) position and array will be sorted.

Algorithm QuickSort: 
1. QuickSort(Arr, p, r) 
2. if(p < r) 
3. q=findPivot(Arr,p,r); //find pivot and its location [ takes O(n) ] 
4. QuickSort(Arr, p,q-1); //left sub array 
5. QuickSort(Arr, q+1,r); // right sub array Algorithm for partition to find pivot 

Algorithm for partition to find pivot :
 PARTITION (Arr, p, r )
 1. x =A[r]
 2. i = p-1
 3. for j =p to r-1
 4.    if A[j] <= x
 5.     i=i+1
 6.    exchange A[i]  with A[j]
 7. exchange A[i+1] with x
 8. return i+1

Following program implements Quick sort in java.

/**
 * @author vikky.agrawal
 *
 */
public class QuickSort {

 
 int[] arr;
 
 QuickSort(){
  arr=new int[] { 5, 3, 1, 2, 9, 8 };
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {
  
  QuickSort obj = new QuickSort();
  obj.operate();
 }
 
 
 public void operate(){
  
  System.out.println("Array before sortings: ");
  printArray();
  quickSort(arr,0,5);

  System.out.println("Sorted array : ");
  printArray();
 }
 
 
 public void quickSort(int[] arr, int p, int r){
  
  if(p<r){
   int q= findPivot(arr,p,r);
   quickSort(arr, p, q-1);
   quickSort(arr, q+1, r);
  }
  
 }
 
 
 /**
  * Algorithm for partition to find pivot
  * 
  * PARTITION.A;p;r
  * 1 x =A[r]
  * 2 i = p-1
  * 3 for j =p to r-1
  * 4   if A[j] <= x 
  * 5   i=i+1 
  * 6   exchange A[i]  with A[j]
  * 7 exchange A[i+1] with x 
  * 8 return i+1
  */
 
 public int findPivot(int[] arr, int p, int r){
  
  int x=arr[r];
  int i=p-1; 
  
  for(int j=p ;j<r; j++){
   if(arr[j]<= x){
    i++;
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
   }
  }  
  
  arr[r]=arr[i+1];
  arr[i+1]=x;
  return i+1;
 }
 
 public void printArray(){
  for (int a : arr) {
   System.out.print(a + " ");
  }
  System.out.println();
 }
}

Complexity analysis:
In average case scenario each problem is divided in 2 sub problems, hence total time required will be:
T(n)= 2T(n/2)+O(n) where O(n) is to find pivot and its location.
Using Master theorem solution to above equation comes as O(n logn)(Avg case)
In worst case scenario array may be divided in (1, n-2) in that case total time required will be
 T(n)= T(1)+T(n-2)+O(n) and solution to this equation becomes : O(n^2) (Worst case)

 But worst case is rare in quick sort and analysis shows that mostly average case occurs with complexity O(n logn).
For more analysis check wiki: Quicksort#analysis  

Facts:
1. Worst case for quick sort occurs when array is already sorted.
2. Worst case also occurs when all the elements are same.

3. Quick sort gives better results than Mergesort in average case.

Merge Sort in Java

Merge sort works on the principle of divide and conquer.
Divide the list in 2 sub-lists, and repeat until there is only 1 element, a sub-list with single element is already sorted.
Now merge the sorted sub-lists to get a sorted list until there is only a single sorted list.

Algorithm:
1. MergeSort(Arr, p ,r)
2. if(p < r)
3.  q=[p+r/2];
4.  MergeSort(Arr, p,q);    //left sub array
5.  MergeSort(Arr, q+1,r);  // right sub array
6.  Merge(Arr, p , q, r);   //Merge, sorted sub arrays [takes O(n) ]

Following program implements Merge sort in java.

/**
 * @author Vikky.Agrawal
 *
 */
public class MergeSort {

 
 int[] arr;
 
 MergeSort(){
  arr=new int[] { 5, 3, 1, 2, 9, 8 };
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {

  MergeSort obj = new MergeSort();
  obj.operate();
 }
 
 
 public void operate(){
  System.out.println("Array before sortings: ");
  printArray();
  mergeSort(arr,0,5);

  System.out.println("Sorted array : ");
  printArray();
 }
 
 
 public void mergeSort(int[] arr, int p, int r){
  if(p<r){
   int q=(p+r)/2;
   mergeSort(arr, p, q);
   mergeSort(arr, q+1, r);
   merge(arr,p,q,r);
  }
 }
 
 public void merge(int[] arr, int p, int q, int r){
  
  int length=arr.length;
  int[] tempArray =new int[length];

  for (int i=0;i<length; i++) {
   tempArray[i]=arr[i];
  }
  
  int temp=p;
  int i=p,j=q+1;
  for(; i<=q && j<=r ; ){
   if(tempArray[i] < tempArray[j]){
    arr[temp++]=tempArray[i];
    i++;
   }else{
    arr[temp++]=tempArray[j];
    j++;
   }
  }
  
  while(i <= q){
   arr[temp++]=tempArray[i];
   i++;
  }
  
  while(j < r){
   arr[temp++]=tempArray[j];
   j++;
  }
 }
 

 public void printArray(){
  for (int a : arr) {
   System.out.print(a + " ");
  }
  System.out.println();
 }

}

Complexity analysis:
Since each problem is divided in 2 sub problems and then these sub problems merged.
Total time required will be T(n)= 2T(n/2)+O(n)
where O(n) is to merge sub problems.
Using Master theorem #case2 solution to above equation comes as O(n logn).

In worst case scenario Merge sort beats Quick sort which requires O(n^2)
worst case time.

For more analysis follow wikipedia: Merge_sort#Analysis
In the worst case, the number of comparisons merge sort makes is equal to or slightly smaller than (n logn - 2 logn + 1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n))

Master theorem for complexity analysis

Master theorem is used to analyze complexity of many problems in divide and conquer category.
Master theorem deals with recurrence relations in the form:

T(n)= aT(n/b)+f(n)
where:
n is size of original problem
a is number of sub-problems
n/b size of sub-problems(assuming sub-problems of equal size)

f(n) is the time required to conquer(dividing or merging) the sub-problems;

such as merging in merge sort or finding pivot in quick sort</em>

There are 3 cases to solve such kind of recurrences:
In each of three cases we compare f(n) with (n ^log_ba). Polynomially larger of these functions determines solution.

Case 1:
If f(n) = O( n^c ) where c < log_ba
then solution becomes T(n) = θ(n ^log_ba)

In first case, comparison states that (n ^log_ba) is larger than f(n),hence solution θ(n ^log_ba)

For example:
T(n) = 9T(n/3)+1000n²
a=9, b=3, f(n)=n² (leaving constant terms)
n ^log_ba = n ^log₃9 = n³ which is polynomially greater than n².
Hence solution T(n) = θ(n³)

Case 2:
 if f(n) = θ(n ^{log _b a} )
then solution becomes T(n) = θ(n ^log_ba logn)
In second case, comparison states that (n ^log_ba) is equal to f(n), we multiply f(n) by logarithmic factor hence solution θ(n ^log_ba logn)

For example:
T(n) = T(n/2)+c (Binary search)
a=1, b=2, f(n)=c (constant)
n ^log_ba = n ^log₂1 = n⁰ = 1 which is equal to f(n).
Hence solution T(n) = θ(logn)

Case 3:
if f(n) = Ω( n^c ) where c > log_ba
and it is also true that af(n/b) <= kf(n) for some constant k < 1,
and sufficiently large n.
then solution becomes T(n) = θ( f(n) )

In third case comparison states that (n ^log_ba) is smaller than f(n).
hence solution θ( f(n) )

For example:
T(n) = 2T(n/2)+10n² a=2, b=2, f(n)=n² (leaving constant terms)
n ^log_ba = n ^log₂2 = n which is polynomially smaller than n².
Hence solution T(n) = θ(n²)  

Facts :
Master theorem doesn't apply if function is not polynomially large enough to determine solution.
 eg : T(n) = 2T(n/2)+nlogn here a=2,b=2
f(n) = n logn;
n^log_ba = n;
so f(n) is greater than n^log_ba but not polynomially large enough, its large by a factor of logarithm hence can't determine solution.