Loading....
Coupon Accepted Successfully!

 

Question 1

What is heap sort?
 


A Heap is an almost complete binary tree.In this tree, if the maximum level is i, then, upto the (i-1)th level should be complete. At level i, the number of nodes can be less than or equal to 2^i. If the number of nodes is less than 2^i, then the nodes in that level should be completely filled, only from left to right.

The property of an ascending heap is that, the root is the lowest and given any other node i, that node should be less than its left child and its right child. In a descending heap, the root should be the highest and given any other node i, that node should be greater than its left child and right child.

To sort the elements, one should create the heap first. Once the heap is created, the root has the highest value. Now we need to sort the elements in ascending order. The root can not be exchanged with the nth element so that the item in the nth position is sorted. Now, sort the remaining (n-1) elements. This can be achieved by reconstructing the heap for (n-1) elements.

A highly simplified pseudocode is given below


heapsort()
{
   n = array();   // Convert the tree into an array.
   makeheap(n);   // Construct the initial heap.

   for(i=n; i>=2; i--)
   {
      swap(s[1],s[i]);
      heapsize--;
      keepheap(i);
   }
}

makeheap(n)
{
   heapsize=n;
   for(i=n/2; i>=1; i--)
     keepheap(i);
}

keepheap(i)
{
   l = 2*i;
   r = 2*i + 1;
  
   p = s[l];
   q = s[r];
   t = s[i];

   if(l<=heapsize && p->value > t->value)
     largest = l;
   else
     largest = i;

   m = s[largest];

   if(r<=heapsize && q->value > m->value)
     largest = r;

   if(largest != i)
   {
      swap(s[i], s[largest]);
      keepheap(largest);
   }
}



Question 2

What is the difference between Merge Sort and Quick sort?
 


Both Merge-sort and Quick-sort have same time complexity i.e. O(nlogn). In merge sort the file a[1:n] was divided at its midpoint into sub-arrays which are independently sorted and later merged. Whereas, in quick sort the division into two sub-arrays is made so that the sorted sub-arrays do not need to be merged latter.

Question 3

Give pseudocode for the mergesort algorithm
 



Mergesort(a, left, right)
{
   if(left    {
     I=(left+right)/2;
     Mergesort(a,left, I);
     Mergesort(a,I+1,right);
     Merge(a,b,left,I,right);
     Copy(b,a,left,right);
   }
}



The merge would be something liks this


merge(int a[], int b[], int c[], int m, int n)
{
  int i, j, k;
  i = 0;
  j = 0;
  k = 0;

  while(i<=m && j<=n)
  {
    if(a[i]      {
        c[k]=a[i];
        i=i+1;
    }
    else
    {
        c[k]=a[j];
        j=j+1;
    }
    k=k+1;
  }

  while(i<=m)
    c[k++]=a[i++];

  while(j<=n)
    c[k++]=a[j++];
}



Question 4

Implement the bubble sort algorithm. How can it be improved? Write the code for selection sort, quick sort, insertion sort.
 


Here is the Bubble sort algorithm


void bubble_sort(int a[], int n)
{
  int i, j, temp;

  for(j = 1; j    {
     for(i = 0; i       {
        if(a[i] >= a[i + 1])
        {
           //Swap a[i], a[i+1]
        }
     }
  }
}



To improvise this basic algorithm, keep track of whether a particular pass results in any swap or not. If not, you can break out without wasting more cycles.


void bubble_sort(int a[], int n)
{
  int i, j, temp;
  int flag;
   
  for(j = 1; j    {
     flag = 0;
     for(i = 0; i       {
        if(a[i] >= a[i + 1])
        {
           //Swap a[i], a[i+1]
           flag = 1;
        }
     }

     if(flag==0)break;
  }
}




This is the selection sort algorithm


void selection_sort(int a[], int n)
{
   int i, j, small, pos, temp;

   for(i = 0; i     {
      small = a[i];
      pos   = i;

      for(j = i + 1; j        {
         if(a[j]           {
            small = a[j];
            pos   = j;
         }
      }
 
      temp   = a[pos];
      a[pos] = a[i];
      a[i]   = temp;
   }
}





Here is the Quick sort algorithm


int partition(int a[], int low, int high)
{
   int i, j, temp, key;

   key = a[low];
   i   = low + 1;
   j   = high;

   while(1)
   {
       while(i = a[i])i++;
  
       while(key 
       if(i         {
           temp = a[i];
           a[i] = a[j];
           a[j] = temp;
       }
       else
       {
           temp   = a[low];
           a[low] = a[j];
           a[j]   = temp;
           return(j); 
       }
   }
}


void quicksort(int a[], int low, int high)
{
   int j;
   
   if(low     {
       j = partition(a, low, high);
       quicksort(a, low, j - 1);
       quicksort(a, j + 1, high);
   }
}


int main()

  // Populate the array a
  quicksort(a, 0, n - 1);
}





Here is the Insertion sort algorithm


void insertion_sort(int a[], int n)
{
   int i, j, item;

   for(i = 0; i     {
       item = a[i];
       j    = i - 1;
  
       while(j >=0 && item         {
          a[j + 1] = a[j];
          j--;
       }

       a[j + 1] = item;
   }
}







Test Your Skills Now!
Take a Quiz now
Reviewer Name