Heap Sort

Heap Sort

  June 22, 2018    

---

This sorting needs max Heap to sort Array
Algorithm:
As we know heap are balanced tree so they can be constructed using array.

We are already having array , heapify it using root i.e. n/2-1 roots are there so heapify  n/2-1times
After heapify 
Root node will have node greater than its child nodes
We will swap last node with its first node
decrement last node ,change  root to next element and heapify again


Code:

 void buildHeap(int a[], int n)
    {
        for(int i=n/2-1;i>=0;--i)
        heapify(a,n,i);
        for(int i=n-1;i>=0;--i)
        {
            int temp=a[0];
            a[0]=a[i];
            a[i]=temp;
            heapify(a,n,0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int a[], int n, int i)
    {
        int l=2*i+1;
        int r=2*i+2;
        int max=i;
        if(l<n && a[l]>a[max])
        max=l;
        if(r<n && a[r]>a[max])
        max=r;
        if(max!=i)
        {
            int temp=a[i];
            a[i]=a[max];
            a[max]=temp;
            heapify(a,n,max);
        }
    }

Read More

Longest Even Number

Longest Even Number

  February 05, 2018    

---

Task is to form longest even number using digits of given number.

Idea is to use Count sort to sort them and them find the least even number if 0th index is not even.

Print them.


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
public static void longestEvenNumber(String str)
{
//count Sort
int len=str.length();
int count[]=new int[10];
for(int i=0;i<len;++i)
{
++count[str.charAt(i)-'0'];
}
for(int i=1;i<10;++i)
count[i]+=count[i-1];
int op[]=new int[len];//output array
for(int i=0;i<len;++i)
{
op[count[str.charAt(i)-'0']-1]=str.charAt(i)-'0';
--count[str.charAt(i)-'0'];
}
int ev=-1;
//Look for next even number and save it
if(((op[0])&1)!=0)
for(int i=1;i<len;++i)
{
    // System.out.println("lop");
if((op[i]&1)==0)
{
ev=op[i];
op[i]=-1;
break;
}
}
for(int i=len-1;i>=0;--i)
{
if(op[i]!=-1)
System.out.print(op[i]);
}
if(ev!=-1)
System.out.print(ev);
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
longestEvenNumber(ab.next());
    System.out.println();
}
}
}

Read More

Count the Inversion Array

Count the Inversion Array

  October 26, 2017    

---

Idea is to use Modified Merge Sort algorithm so that whenever a change (Inversion)  is detected
Just mark that point and it is known than other than this slot values are sorted so inversions are mid-i;



Code:

 public static int countInversion(int arr[],int n)
{
int temp[]=new int[n+1];
return mergesort(arr,temp,0,n);
}
public static int mergesort(int arr[],int temp[],int l,int r)
{
int inv=0;
if(l<r)
{
int mid=(r+l)>>1;
inv=mergesort(arr,temp,l,mid);
inv+=mergesort(arr,temp,mid+1,r);
inv+=merge(arr,temp,l,mid+1,r);
}
return inv;
}
public static int merge(int arr[],int temp[],int l,int mid,int r)
{
int i=l;
int k=mid;
int u=l;
int inv=0;
while(i<=mid-1 && k<=r)
{
if(arr[i]<=arr[k])
temp[u++]=arr[i++];
else
{
temp[u++]=arr[k++];
inv+=mid-i;
}
}
while(i<=mid-1)
temp[u++]=arr[i++];
while(k<=r)
{
temp[u++]=arr[k++];
}
for(i=l;i<=r;++i)
arr[i]=temp[i];
return inv;
}

Read More

Merge Sort Singly LL

Merge Sort Singly LL

  October 07, 2017    

---

Idea is to split list into two parts and merge them


Code:
Node mergeSort(Node h)
{
//only one element ( length of ll is <=1)
if(h==null || h.next==null)
return h;
}
Node first=split(h);
Node second=half->next;
half->next=null;
//recur for left and right ll as we need two separate LL to sort and merge
Node left=mergeSort(first);
Node right=mergeSort(second);
return merge(left,right);
}
//divide LL in two parts
Node split(Node h)
{
if(h==null)
return h;
Node fast=h;
Node slow=h;
while(fast.next!=null && fast.next.next!=null)
{
slow=slow.next;
fast=fast.next.next;
}
return slow;

}
//only mapping is changed 
//if a is small make its next to next smaller node and so on
Node merge(Node a,Node b)
{
Node res;
if(a==null)
return b;
if(b==null)
return a;
if(a.data<b.data)
{
res=a;
res.next=merge(a.next,b);
}
else
{
res=b;
res.next=merge(a,b.next);
}
return res;
}

Read More

Merge K sorted Arrays

Merge K sorted Arrays

  August 19, 2017    

---

Explanation:

Here i am using a loop to merge two list and then calling merge to merge next array with previously merged List.

Another idea is to push elements into heap and add them to array.

Code:

         public static ArrayList<Integer> merge(ArrayList<Integer> arr,int[]arrays,int k)

         {

             ArrayList<Integer> nxt=new ArrayList<Integer>();

             int i=0;

             while(!arr.isEmpty() && i<k)

             {

                 if(arr.get(0) <arrays[i])

                 {

                     nxt.add(arr.remove(0));

                 }

                 else

                 nxt.add(arrays[i++]);

             }

             while(!arr.isEmpty())

             nxt.add(arr.remove(0));

             while(i<k)

             nxt.add(arrays[i++]);

             return nxt;

         }

        public static ArrayList<Integer> mergeKArrays(int[][] arrays,int k) 

          {

           ArrayList<Integer> arr=new ArrayList<Integer>();

           for(int i=0;i<k;i++)

           arr.add(arrays[0][i]);

           for(int i=1;i<k;i++)

           arr=merge(arr,arrays[i],k);

           return arr;

          }

Read More

How to add Value in Array Sorted

How to add Value in Array Sorted

  March 29, 2017    

---

For this we use Treemap ,it may contain many null values but one nullKey.

import java.util.*;
class treemap
{
public static void main(String args[])
{
TreeMap<Integer,Integer> treemaps=new TreeMap<Integer,Integer>(); //Storing two integer values
treemaps.put(5,null);
treemaps.put(1,null);
treemaps.put(90,null);
treemaps.put(17,null);
Set set=treemaps.entrySet(); //Use set to get values in set (For iterator)
Iterator i=set.iterator(); //set Iterator on set
while(i.hasNext())
{
Map.Entry a=(Map.Entry)i.next(); //give key and value to a MapEntry
System.out.println(a.getKey());
}
//or without Iterator
for(Map.Entry<Integer,Integer> getdata :treemaps.entrySet())
{
System.out.println(getdata.getKey());
}
}
}

Read More

Bubble sort using JAVA

Bubble sort using JAVA

  February 02, 2017    

---

import java.util.*;
class bubble
{
public static void main(String args[])
{
int n,i,key;
System.out.println("ENter range");
Scanner ab=new Scanner(System.in);
n=ab.nextInt();
int []arr=new int[n];
for(i=0;i<n;i++)
arr[i]=ab.nextInt();
for(i=0;i<n;i++)
{
for(int j=1;j<n-i;j++)
{
if(arr[j-1]>arr[j])
{
key=arr[j-1];
arr[j-1]=arr[j];
arr[j]=key;
}
}
for(int k=0;k<n;k++)
System.out.print(arr[k]+" ");

System.out.println("");
}
System.out.println("now array ");
for(i=0;i<n;i++)
System.out.print(arr[i]+" ");
}
}

Read More

Insertion sort using JAVA

Insertion sort using JAVA

  January 31, 2017    

---

import java.util.*;
class instsort
{
public static void main(String args[])
{
int n,i,key;
System.out.println("ENter range");
Scanner ab=new Scanner(System.in);
n=ab.nextInt();
int []arr=new int[n];
for(i=0;i<n;i++)
arr[i]=ab.nextInt();
for(i=1;i<n;i++)
{
key=arr[i];//we will lose the value of position so keeping it in  a variable
int j=i-1;
while(j>=0 &&arr[j]>key)//check for previous values if it is smaller
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;// place key to the its minimal value
}
for(i=0;i<n;i++)
System.out.print(arr[i]+" ");
}
}

Read More

Counting Sort 1

Counting Sort 1

  January 22, 2017    

---

this sorting is done by hash function.
it is a better approach which take less time , approx O(N).


#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
  int n;
    cin>>n;
    int arr[100]={0},inp[n];
    for(int i=0;i<n;i++)
        {
        cin>>inp[i];
        arr[inp[i]]++;
    }
    for(int i=0;i<100;i++)
        cout<<arr[i]<<" ";
    return 0;
}

Read More