Thursday, August 28, 2014

Array - X [ Heap Sort ]



Heap Sort

Heap sort is works by finding the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, to achieve the task only possible by using a data structure called a heap. A heap is a special type of binary tree. After the data list has been arranged into a heap, the root node (first node) is assured to be the largest (or smallest) element. Then it is removed and placed at the end of the list, the heap is reorganized, so the largest element keep moving to the root. The process continues for the rest of the elements.

Graphical Presentation of Heapify and Heap Sort






Complexity

Heap-Sort takes O(log n) time, instead of O(n) for a linear searching as in simple selection sort. This allows Heap sort to run in O(n log n) time.


·         Heap sort is always O(n log n)   
Quick sort is usually O(n log n) but in the worst case slows to O(n2)
Quick sort is generally faster, but Heap sort is better in time-critical applications
A loop of n times (actually, n-1 times) used, because it keeps removing one of the n nodes each time removing and replacing the root takes O(1) time
·         Therefore, the total time is n times.
Since re-heap takes place inside loop of n times, the total time for the loop is n*O(log n), or O(n log n)
·         Where heapifying takes O(n log n) time
The loop takes O(n log n) time
Therefore, total time is therefore O(n log n) + O(n log n)

        This is the same as                     O(n log n) time
        Worst case performance             O(n log n)
        Best case performance                Ω(n),O(n log n)
        Average case performance           O(n log n)



Algorithm

HeapSort(int ar[], int n)
1.   int i,j;
2.   int lf, rt, mid, val, num;
3.   val = (n-1)/2;
4.   for j=val to 0 step -1
5.        do
6.            for i= val to 0 step -1
7.                 do
8.                     lf = (2*i)+1;
9.                              then
10.                                  rt = (2*i)+2;
11.                        endif
12.                       if lf <= n and rt <= n
13.                            then
14.                                  if ar[rt] >= ar[lf]
15.                                            then
16.                                                      mid = rt;
17.                                  else
18.                                                      mid = lf;
19.                                  endif
20.                       else if(rt > n)
21.                                  mid = lf;
22.                        else
23.                                  mid = rt;
24.                        endif
25.                      if(ar[i] < ar[mid])
26.                            then
27.                                  num = ar[i];
28.                                  ar[i] = ar[mid];
29.                                  ar[mid] = num;
30.                       endif
31.               endfor
32.          num = ar[0];
33.          ar[0] = ar[n];
34.          ar[n] = num;
35.      endfor

Pseudo Code


HeapSort

BUILD_HEAP
heap-size (A) ← length [A]
for i ←  length[A]/2 down to 1 do
      Heapify (A, i)

HEAPSORT
BUILD_HEAP (A)
for i  length (A) down to 2 do
        exchange A[1] ↔ A[i]
heap-size [A] ¬ heap-size [A] - 1
        Heapify (A, 1)
Heapify
l ← left [i]
r ← right [i]
if l ≤ heap-size [A] and A[l] > A[i]
       then largest ← l
 else largest ← i
if r ≤ heap-size [A] and A[i] > A[largest]
      then largest ← r
if largest  ← i
    then exchange A[i] ↔ A[largest]
        Heapify (A, largest)

Source Code


import java.io.*;
    class Heap_Sort
        {
            void HeapSort(int ar[], int n)
                {
                    int i,j;
                    int lf, rt, mid, val, num;
                    val = (n-1)/2;
                    for(j=val;j>=0;j--)
                        {
                            for(i=val;i>=0;i--)
                                {
                                    lf = (2*i)+1;
                                    rt = (2*i)+2;
                                    if ((lf <= n) && (rt <= n))
                                        {
                                            if(ar[rt] >= ar[lf])
                                                {
                                                    mid = rt;
                                                }
                                            else
                                                {
                                                    mid = lf;
                                                }
                                         }
                                     else
                                         {
                                             if(rt > n)
                                                {
                                                    mid = lf;
                                                }
                                             else
                                                {
                                                    mid = rt;
                                                }
                                          }
                                    if (ar[i] < ar[mid])
                                        {
                                            num = ar[i];
                                            ar[i] = ar[mid];
                                            ar[mid] = num;
                                        }
                                }
                        }
                        num = ar[0];
                        ar[0] = ar[n];
                        ar[n] = num;
               }
        void Input()throws IOException
            {
                   BufferedReader Br=new BufferedReader(new InputStreamReader(System.in));
                   int i;
                   System.out.print("\n\tEnter size of array : ");
                   int Size=Integer.parseInt(Br.readLine());
                   int Arr[]=new int[Size];
                   for(i=0;i<Size;i++)
                       {
                           System.out.print("\tEnter Element at Arr["+i+"] : ");
                           Arr[i]=Integer.parseInt(Br.readLine());
                       }
                   System.out.print("\n\tOriginal  :  ");
                   Disp(Arr);
                   for(i=Size; i>1; i--)
                      {
                        HeapSort(Arr,i-1);
                      }  
                   System.out.print("\n\tAfter Sort : "); 
                   Disp(Arr);
            }
        void Disp(int Arr[])
            {
                 for(int i=0 ;i<Arr.length;i++)
                    {
                        System.out.print(Arr[i]+"  ");
                    }               
            }           

//Main Function
        public static  void main(String args[])throws IOException
            {
                Heap_Sort HS=new Heap_Sort();
                HS.Input();
             }
          }

Output


          Enter size of array : 5
          Enter Element at Arr[0] : 5
          Enter Element at Arr[1] : 1
          Enter Element at Arr[2] : 2
          Enter Element at Arr[3] : 9
          Enter Element at Arr[4] : 6

          Original  :  5  1  2  9  6 
          After Sort : 1  2  5  6  9 


Posted by at No comments:
Labels:

Thursday, August 21, 2014

Array - IX [ Merge Sort ]



Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list.


In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n  follows from the applied algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists.

In the worst case, the number of comparisons merge sort makes is equal to or slightly smaller than (n élg nù - 2élg nù  + 1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n))

        Best case performance                   O(n log n) typical,
                                                            O(n) natural variant
        Average case performance              O(n log n)
        Worst case space complexity          O(n) auxiliary

               T(n) = 2T(n/2) + cn.
        In the same way:
               T(n/2) = 2T(n/4) + cn/2, so
               T(n) = 4T(n/4) + 2cn.
        Going in this way ...
               T(n) = 2mT(n/2m) + mcn, and
               T(n) = 2kT(n/2k) + kcn = nT(1) + cnlog2n = O(n log n).

Merge Sort Algorithm

procedure MergeSort (A, left, right)
1.      if     left >= right  
2.                return
3.      else
4.                middle = b(left+right)/2
5.                MergeSort(A, left, middle)
6.                MergeSort(A, middle+1, right)
7.                Merge(A, left, middle, right)
  
procedure  Merge(A, left, middle, right)
1.            n1 = middle – left + 1
2.            n2 = right – middle
3.            create array L[n1], R[n2]
4.            for i = 0 to n1-1
                   do
                           L[i] = A[left +i]
                   done
5.            for j = 0 to n2-1
                   do
                           R[j] = A[middle+j]
6.                     done
7.            k = i = j = 0
8.            while i < n1 &  j < n2
                   do
                           if L[i] < R[j]
                                 A[k++] = L[i++]
                           else
                                 A[k++] = R[j++]
9.                             done
10.          while i < n1
                   do
                           A[k++] = L[i++]
11.          done
12.          while j < n2
                   do
                           A[k++] = R[j++]
13.                   done

Merge Sort Pseudo Code


  Merge-Sort (A, left, right)

   if     left ≥ right  
          return
  else
         middle ← b(left+right)/2û
         Merge-Sort(A, left, middle)
         Merge-Sort(A, middle+1, right)
         Merge(A, left, middle, right)

Merge(A, left, middle, right)
n1 ← middle – left + 1
n2 ← right – middle
create array L[n1], R[n2]
for i ← 0 to n1-1 do L[i] ← A[left +i]
for j ← 0 to n2-1 do R[j] ← A[middle+j]
k ← i ← j ← 0
while i < n1 &  j < n2
       if L[i] < R[j]
                         A[k++] ← L[i++]
       else
                         A[k++] ←R[j++]
while i < n1
     A[k++] ← L[i++]
while j < n2
     A[k++] ← R[j++]


7
4
3
0
2
8
6
9
1
5

7
4

3
0

2


8
6

9
1

5

7

4

3

0

2


8

6

9

1

5

4
7

0
3

2




6
8

1
9

5

0
2
3
4
7


1
5
6
8
9

0
1
2
3
4
5
6
8
9


Source Code


//MergeSort in Java
import java.io.*;
    public class Merge_Sort
        {
 int arr[],Size;
             void Merge(int top, int n, int m)
                {
                    int c= 0,c1 = 0,c2 = 0,i;
                    int arr1[]=new int[10];
                    while((c1 < n) && (c2 < m))
                        {
                            if(arr[top + c1] < arr[top + n + c2])
                                {
                                    arr1[c++] = arr[top + (c1++)];
                                }
                            else
                                {
                                    arr1[c++] = arr[top + n + (c2++)];
                                }
                        }
                    while (c1 < n)
                        {
                            arr1[c++] = arr[top + (c1++)];
                        }
                    while (c2 < m)
                        {
                            arr1[c++] = arr[top + n + (c2++)];
                        }
                    for (i = 0; i < n+m; i++)
                        {
                            arr[top + i] = arr1[i];
                        }
                }

                void Msort(int top , int n2)
                    {
                        int m;
                        int n;
                        if(n2 > 1)
                            {
                                n = n2 / 2;
                                m = n2 - n;
                                Msort(top, n);
                                Msort(top + n, m);
                                Merge(top, n, m);
                            }
                   }
    void GetData()throws IOException
        {
            BufferedReader Br=new BufferedReader(new InputStreamReader(System.in));
            System.out.print("Enter Size : ");  
            Size=Integer.parseInt(Br.readLine());
            arr=new int[Size];
            for(int i=0;i<Size;i++)
                {
                    System.out.print("Enter arr["+i+"] : ");
                    arr[i]=Integer.parseInt(Br.readLine());
                }
            System.out.print("Original Values : ");
            Disp();               
            Msort(0, Size);
       }
   
        void Disp()
            {
                for(int i=0;i<Size;i++)
                    {
                        System.out.print(" "+arr[i]);
                    }
            }
        public static void main(String args[])throws IOException
            {
                Merge_Sort MS=new Merge_Sort();
                MS.GetData();
                System.out.print("\nAfter Sort : ");
                MS.Disp();               
            }
    }


Output

Enter Size : 10
Enter arr[0] : 7
Enter arr[1] : 4
Enter arr[2] : 3
Enter arr[3] : 0
Enter arr[4] : 2
Enter arr[5] : 8
Enter arr[6] : 6
Enter arr[7] : 9
Enter arr[8] : 1
Enter arr[9] : 5
Original Values :  7 4 3 0 2 8 6 9 1 5
After Sort :  0 1 2 3 4 5 6 7 8 9



Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)