Students Mela: DataStructure

Showing posts with label DataStructure. Show all posts

Thursday, August 12, 2010

QuickSort Program in C

void swap(int *a, int *b)
{
  int t=*a; *a=*b; *b=t;
}
void sort(int arr[], int beg, int end)
{
  if (end > beg + 1)
  {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r)
    {
      if (arr[l] <= piv)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    swap(&arr[--l], &arr[beg]);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}

Wednesday, August 11, 2010

Sorting Program in C

/* sort.c */

/* Author    : Mr. Jake Rodriguez Pomperada,MAED-IT */

/* Date      :  March 19, 2009 Thursday */

/* Language  : C  */

/* Tool      :  Turbo C 2.0 */

/* Email     :  jakerpomperada@yahoo.com */

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

 main()

 int a[10],n=0,choice=0;

 int read_array(int []);

 while(1)

   clrscr();

   printf("\t  ============================ ");

   printf("\n\t ======== MAIN MENU ========= ");

    printf("\n\t ============================ ");

   printf("\n\n\t 1> BUBBLE SORT");

   printf("\n\n\t 2> SELECTION SORT");

   printf("\n\n\t 3> INSERTION SORT");

   printf("\n\n\t 4> BUCKET SORT");

   printf("\n\n\t 5> SHELL SORT");

   printf("\n\n\t 6> EXIT");

   printf("\n\n\t ENTER YOUR CHOICE :=> ");

   scanf("%d",&choice);

   switch(choice)

    case 1:n=read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           bubble_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 2:n=read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           select_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 3:n=read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           insert_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 4:n=  read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           bucket_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 5:n=  read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           shell_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 6: printf("\n\n\t\t THANK YOU FOR USING THIS SOFTWARE");

        printf("\n\n\t       Created By: Mr. Jake R. Pomperada, MAED-IT");

        exit(0);

getche();

int read_array(int a[])

 int n,i;

 printf("\n\n\t ENTER THE ARRAY LENGTH :: ");

 scanf("%d",&n);

 for(i=0;i<n;i++)

   printf("\n\n\t ENTER THE ELEMENT [%d] :: ",i);

   scanf("%d",&a[i]);

 return(n);

print_array(int a[],int n)

 int i;

 for(i=0;i<n;i++)

  printf("%d \t",a[i]);

 bubble_sort(int a[],int n)

 int i,j,temp;

 for(i=0;i<n-1;i++)

    for(j=0;j<n-1;j++)

     if(a[j]>a[j+1])

       temp=a[j];

       a[j]=a[j+1];

       a[j+1]=temp;

    printf("\n\n\t PASS %d :: ",i+1);

    print_array(a,n);

select_sort(int a[],int n)

 int i,j,temp;

 for(i=0;i<n-1;i++)

    for(j=i+1;j<n;j++)

       if(a[i]>a[j])

           temp=a[i];

           a[i]=a[j];

           a[j]=temp;

    printf("\n\n\t PASS %d :: ",i+1);

    print_array(a,n);

insert_sort(int a[],int n)

 int i,j,temp;

 for(i=1;i<n;i++)

   temp=a[i];

   for(j=i-1;temp<a[j] && j>=0;j--)

     a[j+1]=a[j];

   a[j+1]=temp;

   printf("\n\n\t PASS %d :: ",i);

   print_array(a,n);

 shell_sort(int a[],int n)

 int i,j,k,d,t,x,flag=0;

 int p=1;

 for(d=n/2;d>=1;d=d/2)

   flag=0;

   for(j=0;j+d<n;j++)

      for(k=j;k>=0;k=k-d)

         if(a[k]>a[k+d])

          t=a[k];

          a[k]=a[k+d];

          a[k+d]=t;

          flag=1;

    if(flag==1)

      printf("\n\n\t PASS %d ::",p++);

      for(x=0;x<n;x++)

            printf("\t %d",a[x]);

 bucket_sort(int a[],int n)

 int b[10][20],i,j,row,col,no,x,p=1;

 for(i=1;i<=5;i++)

   initzerocol(b);

   for(j=0;j<n;j++)

      row=returndigit(a[j],i);

      b[row][0]=b[row][0]+1;

      col= b[row][0];

      b[row][col]=a[j];

   merge(a,b);

   printf("\n\n\t PASS %d ::",p++);

   for(x=0;x<n;x++)

     printf("\t %d",a[x]);

 initzerocol(int b[][20])

 int i;

 for(i=0;i<10;i++)

  b[i][0]=0;

int returndigit(int no,int i)

 int k;

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

  no=no/10;

 return(no%10);

 merge(int a[],int b[][20])

 int i,j,k=0;

 for(i=0;i<10;i++)

   for(j=1;j<=b[i][0];j++)

      a[k]=b[i][j];

      k=k+1;

 /* End of Code */

We've already looked at several O(n^2) sorting algorithms, bubble sort and selection and insertion sort. Now we turn to faster sorting algorithms that can sort in time proportional to O(n*log(n)) in the average and best case time, a significant speedup, as n, the number of items to sort, grows larger. It will also now be important to consider the space taken by an algorithm. The O(n^2) sorts did not require any space over and above what was needed to store the input. Some faster sorts require (or are much easier to understand when explained by using) additional storage. Sorting methods that do not require additional space are called "in place". This property is particularly useful when dealing with large data sets, and some algorithms that seem to require additional space can be made in place with a bit of work.

Perhaps the simplest of these algorithms is heap sort, which is based on the heap data structure. The first important thing to remember about heaps is that the top element of the heap is always "next" in order (either the next highest or next lowest, in the case of numbers). Think about the consequences of this fact -- if we take all of our input values and store them in a heap, and we remove one element at a time, we will remove these elements in sorted order. But how fast is doing this?
There are two factors at work: the time it takes to create a heap by adding each element and the time it takes to remove all of the elements from a heap. Fortunately, we have a guarantee that adding a single element to and removing a single element from a heap both take O(log(n)) time. As noted above, each of these operations takes place once for each element in the input. Consequently, the algorithmic efficiency of a heap sort is O(n*log(n)), rather good indeed.
There are, however, a few tradeoffs. First, heap sort will always take O(n*log(n)) time -- while this means that its worst-case efficiency is more robust than any algorithm previously discussed, it means that even the best case time is O(n*log(n)). As you may recall, bubble sort can be optimized so that it takes only O(n) time in the best case!
Moreover, the simple implementation of heap sort will require additional space sufficient to hold a heap of size n, meaning that you need at least double the amount of space for heapsort as you do for our previous sorts. And creating a heap may have other consequences, such as increasing the constant that is normally dropped in big-O notation. As a result, for small data sets, heap sort might not be the fastest choice!
A last consideration is that heap sort is not a "stable" sort in the sense that it doesn't preserve the original order of equal elements. This might matter if, for instance, you had a list of emails that you wanted to sort by date, and you also wanted to sort alphabetically by sender. One option would be to first sort the emails alphabetically, and then sort by the date received. A stable sort would keep the alphabetical order for emails sent on the same day; an unstable sort would not.
For instance, sorting the following list of names (already in alphabetical order)

From: example@example.com       Sent: 2/1/2005
From: john@example.com          Sent: 2/1/2005
From: smith@mit.edu             Sent: 1/2/2005
...

using heap sort might yield

From: smith@mit.edu             Sent: 1/2/2005
From: john@example.com          Sent: 2/1/2005
From: example@example.com       Sent: 2/1/2005
...

Note that john@example.com is now ahead of example@example.com, even though "john" should be after "example". A proper stable sort would never put john in front of example, choosing instead to preserve the original order

From: smith@mit.edu             Sent: 1/2/2005
From: example@example.com       Sent: 2/1/2005
From: john@example.com          Sent: 2/1/2005
...

In some applications (for instance, mail readers) this can be an important feature. (Note that it's somewhat complicated to sort by treating both name and date as one feature because in some cases you might want the sort names in reverse order and dates in ascending order.)
You might take some time to think about how you could implement a heap sort without using any additional memory.
Summary
Heap sort is a relatively simple algorithm built upon the heap data structure. A naive implementation requires additional space, but it is possible to do a heap sort in place. Heap sort has guaranteed O(n*log(n))) performance, though the constant factor is typically a bit higher than for other algorithms such as quicksort. Heap sort is not a stable sort, so the original ordering of equal elements may not be maintained.
If you want more details on implementation, you can go here to get the source code for a heap and heap sort implementation.

Quicksort

by Jakub Bomba (axon)
When deciding on the best sorting algorithm we often look at its worst-case running time, and base our decision solely on that factor. That is why beginning programmers often overlook quicksort as a viable option because of its T(n^2) worst-case running time, which could be made exponentially unlikely with a little effort. In fact, quicksort is the currently fastest known sorting algorithm and is often the best practical choice for sorting, as its average expected running time is O(n log(n)).

Quicksort, like mergesort, is a divide-and-conquer recursive algorithm. The basic divide-and-conquer process for sorting a subarray S[p..r] is summarized in the following three easy steps:

Divide: Partition S[p..r] into two subarrays S[p..q-1] and S[q+1..r] such that each element of S[p..q-1] is less than or equal to S[q], which is, in turn, less than or equal to each element of S[q+1..r]. Compute the index q as part of this partitioning procedure
Conquer: Sort the two subarrays S[p...q-1] and S[q+1..r] by recursive calls to quicksort.
Combine: Since the subarrays are sorted in place, no work is needed to combing them: the entire array S is now sorted.

Before a further discussion and analysis of quicksort a presentation of its implementation procedure below:

QUICKSORT(S, P, r)
1 If p < r
2 	then q <- PARTITION(S, p, r)
3		QUICKSORT(S, p, q-1)
4		QUICKSORT(S, q+1, r)

note: to sort the whole array S, the initial parameters would be: QUICKSORT(S, 1, length[A])

PARTITION(S, p, r)
1 x <- S[r]
2 i <- p-1
3 for j <- p to r-1
4	do if S[j] <= x
5		then i <- i+1
6			swap S[i] <-> S[j]
7 swap S[i+1] <-> S[r]
8 return i+1

Quicksort's running time depends on the result of the partitioning routine - whether it's balanced or unbalanced. This is determined by the pivot element used for partitioning. If the result of the partition is unbalanced, quicksort can run as slowly as insertion sort; if it's balanced, the algorithm runs asymptotically as fast as merge sort. That is why picking the "best" pivot is a crucial design decision.

The Wrong Way: the popular way of choosing the pivot is to use the first element; this is acceptable only if the input is random, but if the input is presorted, or in the reverse order, then the first elements provides a bad, unbalanced, partition. All the elements go either into S[p...q-1] or S[q+1..r]. If the input is presorted and as the first element is chosen consistently throughout the recursive calls, quicksort has taken quadratic time to do nothing at all.
The Safe Way: the safe way to choose a pivot is to simply pick one randomly; it is unlikely that a random pivot would consistently provide us with a bad partition throughout the course of the sort.
Median-of-Three Way: best case partitioning would occur if PARTITION produces two subproblems of almost equal size - one of size [n/2] and the other of size [n/2]-1. In order to achieve this partition, the pivot would have to be the median of the entire input; unfortunately this is hard to calculate and would consume much of the time, slowing down the algorithm considerably. A decent estimate can be obtained by choosing three elements randomly and using the median of these three as the pivot.

Short Example of a Quicksort Routine (Pivots chosen "randomly")

Input: [13 81 92 65 43 31 57 26 75 0]
Pivot: 65
Partition:  [13 0 26 43 31 57 begin_of_the_skype_highlighting              13 0 26 43 31 57      end_of_the_skype_highlighting]  65  [ 92 75 81]
Pivot: 31  81  
Partition: [13 0 26]  31  [43 57]  65  [75]  81  [92]
Pivot: 13
Parititon: [0]  13  [26]  31  [43 57]  65  [75]  81  [92]
Combine: [0 13 26]  31 [43 57]  65  [75 81 92]
Combine: [0 13 26 31 43 57 begin_of_the_skype_highlighting              0 13 26 31 43 57      end_of_the_skype_highlighting]  65  [75 81 92]
Combine: [0 13 26 31 43 57 65 75 81 92]

Summary
Quicksort is a relatively simple sorting algorithm using the divide-and-conquer recursive procedure. It is the quickest comparison-based sorting algorithm in practice with an average running time of O(n log(n)). Crucial to quicksort's speed is a balanced partition decided by a well chosen pivot. Quicksort has the advantage of sorting in place, and it works well even in virtual memory environments.

Merge Sort

Merge sort is the second guaranteed O(nlog(n)) sort we'll look at. Like heap sort, merge sort requires additional memory proportional to the size of the input for scratch space, but, unlike heap sort, merge sort is stable, meaning that "equal" elements are ordered the same once sorting is complete.

Merge sort works using the principle that if you have two sorted lists, you can merge them together to form another sorted list. Consequently, sorting a large list can be thought of as a problem of sorting two smaller lists and then merging those two lists together. For instance, if you have the list

1 9 7 6

you could divide it into two lists,

1 9
and
7 6

Once those two lists are sorted:

1 9
and
6 7

They could be merged back together easily by starting at the left end of each list and then picking the smaller value. This process is illustrated below for those who find a visual approach helpful:

New list: 1
9
and
6 7

New list: 1 6
9
and
7

New list: 1 6 7
9
and
empty list

New list: 1 6 7 9

Here's the key to merge sort: once you've broken the problem in a problem of sorting and then merging two smaller lists, you can then apply merge sort to each of those smaller lists. This is a recursive process, so it will need a base case. Specifically, once we've reached a single element array, we know it's sorted (it has only one element, which must be in the right position) and we can just merge it with its neighbor to produce a new, sorted two-element array. This array, again, can be recombined with a neighbor, and so on until the entire array is sorted.
Merge sort is also our first divide-and-conquer sort. The term divide and conquer refers to breaking the problem into simpler sub-problems, each of which is then solved by applying the same approach, until the sub-problems are small enough to be solved immediately.
Merge sort guarantees O(nlog(n)) complexity because it always splits the work in half. In order to understand how we derive this time complexity for merge sort, consider the two factors involved: the number of recursive calls, and the time taken to merge each list together.
First, let's consider the number of recursive calls, as this will shed some light onto our understanding of the list merge operation. Each recursive call will either be a base case, or will result in two future recursive calls. The first call starts off by making two calls; each of those makes four, and so forth. What does this sound like?
If you thought,"a binary tree", then you're absolutely right. An easy way to visualize merge sort is as a tree of recursive calls. To save a bit of space, I will use m(lower, upper) to indicate merge sort called from element lower to element upper. For instance, m(0, n-1) would be the merge sort call for an array of size n in C/C++.

                        m(0, 3)
                      /        \
                     /          \
                    /            \
               m(0, 1)         m(2, 3)
              /       \        /      \
             /         \      /        \
       m(0, 0)     m(1, 1) m(2, 2)     m(3, 3)

So we see that for an array of four elements, we have a tree of depth three. Now let's say we doubled the number of elements in the array to eight; each merge sort at the bottom of this tree would now have double the number of elements -- two rather than one. This means we'd need one additional recursive call at each element. This suggests that the total depth of the tree is log(n) + 1, the number of times we need to halve the number of elements in the array to reach the base case.
Now, what about the amount of work done at each recursive call? At first, you might think that every merge in the tree should equate to O(n) time, but this is incorrect. At each level, the number of elements is being dramatically reduced; at the bottom branch, it is certainly not taking O(n) time to perform a non-operation. At the level where the results of the base case are being merged (at depth 1 in the above tree), each merge sort call is merging exactly half the list. At the root node is the only time the entire list is merged together at a single node.
As a result, it makes more sense to think about merge sort in terms of the number of operations performed on a single level of the tree. At each level, a total of n operations take place, and there are log(n) + 1 levels; consequently, the overall time complexity is O(n * log(n)).
Moreover, merge sort is stable -- so long as you break ties by picking from the correct list, equal elements will always end up in the same order as before. Specifically, if you split an array into a left half and a right half, you would break ties in favor of the left half, as it precedes the right half. This allows equal elements to stay ordered across merge operations.
The downside of merge sort is that it usually does require a scratch array to store the the results of a merge. In place mergesort with arrays is a complex problem beyond the scope of this discussion. On the other hand, when dealing with linked lists, merge sort can be outstanding because no scratch space is needed. As an exercise, try implementing merge sort for linked lists without using any extra space save for a few extra variables.
Implementation Here is a find a sample implementation of merge sort. The code is a bit too long to post here, but you should check it out and notice one important feature: the scratch space is only allocated once. Malloc, free and other memory allocation routines (e.g., new and delete in C++) are typically fairly slow. As a consequence, reallocating the scratch space for every recursive call would be time prohibitive and would significantly increase the constant factor of merge sort.
Summary Merge sort is a fast, stable sorting routine with guaranteed O(n*log(n)) efficiency. When sorting arrays, merge sort requires additional scratch space proportional to the size of the input array. Merge sort is relatively simple to code and offers performance typically only slightly below that of quicksort.

Insertion Sort

Insertion sort does exactly what you would expect: it inserts each element of the array into its proper position, leaving progressively larger stretches of the array sorted. What this means in practice is that the sort iterates down an array, and the part of the array already covered is in order; then, the current element of the array is inserted into the proper position at the head of the array, and the rest of the elements are moved down, using the space just vacated by the element inserted as the final space.
Here is an example: for sorting the array the array 52314 First, 2 is inserted before 5, resulting in 25314 Then, 3 is inserted between 2 and 5, resulting in 23514 Next, one is inserted at the start, 12354 Finally, 4 is inserted between 3 and 5, 12345

Selection sort

Selection sort is the most conceptually simple of all the sorting algorithms. It works by selecting the smallest (or largest, if you want to sort from big to small) element of the array and placing it at the head of the array. Then the process is repeated for the remainder of the array; the next largest element is selected and put into the next slot, and so on down the line.

Because a selection sort looks at progressively smaller parts of the array each time (as it knows to ignore the front of the array because it is already in order), a selection sort is slightly faster than bubble sort, and can be better than a modified bubble sort.
Here is the code for a simple selection sort:

	for(int x=0; x<n; x++)

	{

		int index_of_min = x;

		for(int y=x; y<n; y++)

		{

			if(array[index_of_min]<array[y])

			{

				index_of_min = y;

			}

		}

		int temp = array[x];

		array[x] = array[index_of_min];

		array[index_of_min] = temp;

	}

The first loop goes from 0 to n, and the second loop goes from x to n, so it goes from 0 to n, then from 1 to n, then from 2 to n and so on. The multiplication works out so that the efficiency is n*(n/2), though the order is still O(n^2).

Bubble sort

The simplest sorting algorithm is bubble sort. The bubble sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary, until the array is sorted. Since the worst case scenario is that the array is in reverse order, and that the first element in sorted array is the last element in the starting array, the most exchanges that will be necessary is equal to the length of the array. Here is a simple example:
Given an array 23154 a bubble sort would lead to the following sequence of partially sorted arrays: 21354, 21345, 12345. First the 1 and 3 would be compared and switched, then the 4 and 5. On the next pass, the 1 and 2 would switch, and the array would be in order.
The basic code for bubble sort looks like this, for sorting an integer array:

	for(int x=0; x<n; x++)

	{

		for(int y=0; y<n-1; y++)

		{

			if(array[y]>array[y+1])

			{

				int temp = array[y+1];

				array[y+1] = array[y];

				array[y] = temp;

			}

		}

	}

Notice that this will always loop n times from 0 to n, so the order of this algorithm is O(n^2). This is both the best and worst case scenario because the code contains no way of determining if the array is already in order.
A better version of bubble sort, known as modified bubble sort, includes a flag that is set if an exchange is made after an entire pass over the array. If no exchange is made, then it should be clear that the array is already in order because no two elements need to be switched. In that case, the sort should end. The new best case order for this algorithm is O(n), as if the array is already sorted, then no exchanges are made. You can figure out the code yourself! It only requires a few changes to the original bubble sort.

Comparison of sorting algorithm

	Time
Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Even a perfectly sorted input requires scanning the entire array
Insertion Sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	In the best case (already sorted), every insert requires constant time
Heap Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Constant	Instable	By using input array as storage for the heap, it is possible to achieve constant space
Merge Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Depends	Stable	On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
Quicksort	O(n*log(n))	O(n*log(n))	O(n^2)	Constant	Stable	Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.

Sorting Programs in C

Sorting in general refers to various methods of arranging or ordering things based on criterias (numerical, chronological, alphabetical, heirarchial etc.). In Computer Science, due to obvious reasons, Sorting (of data) is of immense importance and is one of the most extensively researched subjects. It is one of the most fundamental algorithmic problems. So much so that it is also fundmental to many other fundamental algorithmic problems such as search algorithms, merge algorithms etc. It is estimated that around 25% of all CPU cycles are used to sort data. There are many approaches to sorting data and each has its own merits and demerits. This article discusses some of the common sorting algorithms.

Bubble Sort
Bubble Sort is probably one of the oldest, most easiest, straight-forward, inefficient sorting algorithms. It is the algorithm introduced as a sorting routine in most introductory courses on Algorithms. Bubble Sort works by comparing each element of the list with the element next to it and swapping them if required. With each pass, the largest of the list is "bubbled" to the end of the list whereas the smaller values sink to the bottom. It is similar to selection sort although not as straight forward. Instead of "selecting" maximum values, they are bubbled to a part of the list. An implementation in C.

void BubbleSort(int a[], int array_size)
{
     int i, j, temp;
     for (i = 0; i < (array_size - 1); ++i)
     {
          for (j = 0; j < array_size - 1 - i; ++j )
          {
               if (a[j] > a[j+1])
               {
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
               }
          }
     }
}

A single, complete "bubble step" is the step in which a maximum element is bubbled to its correct position. This is handled by the inner for loop.

for (j = 0; j < array_size - 1 - i; ++j )
{
     if (a[j] > a[j+1])
     {
          temp = a[j+1];
          a[j+1] = a[j];
          a[j] = temp;
     }
}

Examine the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)

8 6 10 3 1 2 5 4 } pass 0
6 8 3 1 2 5 4 10 } pass 1
6 3 1 2 5 4 8 10 } pass 2
3 1 2 5 4 6 8 10 } pass 3
1 2 3 4 5 6 8 10 } pass 4
1 2 3 4 5 6 8 10 } pass 5
1 2 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7

The above tabulated clearly depicts how each bubble sort works. Note that each pass results in one number being bubbled to the end of the list.

Selection Sort
The idea of Selection Sort is rather simple. It basically determines the minimum (or maximum) of the list and swaps it with the element at the index where its supposed to be. The process is repeated such that the nth minimum (or maximum) element is swapped with the element at the n-1th index of the list. The below is an implementation of the algorithm in C.

void SelectionSort(int a[], int array_size)
{
     int i;
     for (i = 0; i < array_size - 1; ++i)
     {
          int j, min, temp;
          min = i;
          for (j = i+1; j < array_size; ++j)
          {
               if (a[j] < a[min])
                    min = j;
          }

          temp = a[i];
          a[i] = a[min];
          a[min] = temp;
     }
}

Consider the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)

8 6 10 3 1 2 5 4 } pass 0
1 6 10 3 8 2 5 4 } pass 1
1 2 10 3 8 6 5 4 } pass 2
1 2 3 10 8 6 5 4 } pass 3
1 2 3 4 8 6 5 10 } pass 4
1 2 3 4 5 6 8 10 } pass 5
1 2 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7

At pass 0, the list is unordered. Following that is pass 1, in which the minimum element 1 is selected and swapped with the element 8, at the lowest index 0. In pass 2, however, only the sublist is considered, excluding the element 1. So element 2, is swapped with element 6, in the 2nd lowest index position. This process continues till the sub list is narrowed down to just one element at the highest index (which is its right position).

Insertion Sort
The Insertion Sort algorithm is a commonly used algorithm. Even if you haven't been a programmer or a student of computer science, you may have used this algorithm. Try recalling how you sort a deck of cards. You start from the begining, traverse through the cards and as you find cards misplaced by precedence you remove them and insert them back into the right position. Eventually what you have is a sorted deck of cards. The same idea is applied in the Insertion Sort algorithm. The following is an implementation in C.

void insertionSort(int a[], int array_size)
{
     int i, j, index;
     for (i = 1; i < array_size; ++i)
     {
          index = a[i];
          for (j = i; j > 0 && a[j-1] > index; j--)
               a[j] = a[j-1];

          a[j] = index;
     }
}

8 6 10 3 1 2 5 4 } pass 0
6 8 10 3 1 2 5 4 } pass 1
6 8 10 3 1 2 5 4 } pass 2
3 6 8 10 1 2 5 4 } pass 3
1 3 6 8 10 2 5 4 } pass 4
1 2 3 6 8 10 5 4 } pass 5
1 2 3 5 6 8 10 4 } pass 6
1 2 3 4 5 6 8 10 } pass 7

The pass 0 is only to show the state of the unsorted array before it is given to the loop for sorting. Now try out the deck-of-cards-sorting algorithm with this list and see if it matches with the tabulated data. For example, you start from 8 and the next card you see is 6. Hence you remove 6 from its current position and "insert" it back to the top. That constitued pass 1. Repeat the same process and you'll do the same thing for 3 which is inserted at the top. Observe in pass 5 that 2 is moved from position 5 to position 1 since its < (6,8,10) but > 1. As you carry on till you reach the end of the list you'll find that the list has been sorted. It didn't take a course to tell you how to sort a deck of cards, did it; you prolly figured it out on your own. Amazed at the computer scientist in you ? ;)

Heap Sort
Heap sort algorithm, as the name suggests, is based on the concept of heaps. It begins by constructing a special type of binary tree, called heap, out of the set of data which is to be sorted. Note:

A Heap by definition is a special type of binary tree in which each node is greater than any of its descendants. It is a complete binary tree.
A semi-heap is a binary tree in which all the nodes except the root possess the heap property.
If N be the number of a node, then its left child is 2*N and the right child 2*N+1.

The root node of a Heap, by definition, is the maximum of all the elements in the set of data, constituting the binary tree. Hence the sorting process basically consists of extracting the root node and reheaping the remaining set of elements to obtain the next largest element till there are no more elements left to heap. Elemetary implementations usually employ two arrays, one for the heap and the other to store the sorted data. But it is possible to use the same array to heap the unordered list and compile the sorted list. This is usually done by swapping the root of the heap with the end of the array and then excluding that element from any subsequent reheaping.

Significance of a semi-heap - A Semi-Heap as mentioned above is a Heap except that the root does not possess the property of a heap node. This type of a heap is significant in the discussion of Heap Sorting, since after each "Heaping" of the set of data, the root is extracted and replaced by an element from the list. This leaves us with a Semi-Heap. Reheaping a Semi-Heap is particularily easy since all other nodes have already been heaped and only the root node has to be shifted downwards to its right position. The following C function takes care of reheaping a set of data or a part of it.

void downHeap(int a[], int root, int bottom)
{
     int maxchild, temp, child;
     while (root*2 < bottom)
     {
          child = root * 2 + 1;
          if (child == bottom)
          {
               maxchild = child;
          }
          else
          {
               if (a[child] > a[child + 1])
                    maxchild = child;
               else
                    maxchild = child + 1;
          }

          if (a[root] < a[maxchild])
          {
               temp = a[root];
               a[root] = a[maxchild];
               a[maxchild] = temp;
          }
          else return;

          root = maxchild;
     }
}

In the above function, both root and bottom are indices into the array. Note that, theoritically speaking, we generally express the indices of the nodes starting from 1 through size of the array. But in C, we know that array indexing begins at 0; and so the left child is

child = root * 2 + 1
/* so, for eg., if root = 0, child = 1 (not 0) */

In the function, what basically happens is that, starting from root each loop performs a check for the heap property of root and does whatever necessary to make it conform to it. If it does already conform to it, the loop breaks and the function returns to caller. Note that the function assumes that the tree constituted by the root and all its descendants is a Semi-Heap.

Now that we have a downheaper, what we need is the actual sorting routine.

void heapsort(int a[], int array_size)
{
     int i;
     for (i = (array_size/2 -1); i >= 0; --i)
     {
          downHeap(a, i, array_size-1);
     }

     for (i = array_size-1; i >= 0; --i)
     {
          int temp;
          temp = a[i];
          a[i] = a[0];
          a[0] = temp;
          downHeap(a, 0, i-1);
     }
}

Note that, before the actual sorting of data takes place, the list is heaped in the for loop starting from the mid element (which is the parent of the right most leaf of the tree) of the list.

for (i = (array_size/2 -1); i >= 0; --i)
{
     downHeap(a, i, array_size-1);
}

Following this is the loop which actually performs the extraction of the root and creating the sorted list. Notice the swapping of the ith element with the root followed by a reheaping of the list.

for (i = array_size-1; i >= 0; --i)
{
     int temp;
     temp = a[i];
     a[i] = a[0];
     a[0] = temp;
     downHeap(a, 0, i-1);
}

The following are some snapshots of the array during the sorting process. The unodered list -

8 6 10 3 1 2 5 4

After the initial heaping done by the first for loop.

10 6 8 4 1 2 5 3

Second loop which extracts root and reheaps.

8 6 5 4 1 2 3 10 } pass 1
6 4 5 3 1 2 8 10 } pass 2
5 4 2 3 1 6 8 10 } pass 3
4 3 2 1 5 6 8 10 } pass 4
3 1 2 4 5 6 8 10 } pass 5
2 1 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7
1 2 3 4 5 6 8 10 } pass 8

Heap sort is one of the preferred sorting algorithms when the number of data items is large. Its efficiency in general is considered to be poorer than quick sort and merge sort.

Thursday, May 27, 2010

DataStructure Interview Questions

1.) What is Heap data structure?

The binary heap data
structures is an array that can be viewed as a complete binary tree.
Each
node of the binary tree corresponds to an element of the array.
The
array is completely filled on all levels except possibly lowest.

2.)
What are the major data structures used in the following areas : RDBMS,
Network data model & Hierarchical data model?

1. RDBMS Array
(i.e. Array of structures)
2. Network data model Graph
3.
Hierarchical data model Trees

3.) Why is the isEmpty() member
method called?

The isEmpty() member method is called within the
dequeue process to determine if there is an item in the
queue to be
removed i.e. isEmpty() is called to decide whether the queue has at
least one element.
This method is called by the dequeue() method
before returning the front element.
What method is used to place a
value onto the top of a stack?
push() method, Push is the direction
that data is being added to the stack.
push() member method places a
value onto the top of a stack.

4.) What is Linked List ?

Linked
List is one of the fundamental data structures. It consists of a
sequence of? nodes,
each containing arbitrary data fields and one or
two (”links”) pointing to the next and/or previous nodes.
A linked
list is a self-referential datatype because it contains a pointer or
link to another data of the same type.
Linked lists permit insertion
and removal of nodes at any point in the list in constant time, but do
not allow random access.

5.) Difference between calloc and
malloc?

malloc: allocate n bytes calloc: allocate m times n bytes
initialized to 0

6.) How many parts are there in a declaration
statement?

There are two main parts, variable identifier and data
type and the third type is optional
which is type qualifier like
signed/unsigned.

7.) What is the difference bitween NULL AND VOID
pointer?

NULL can be value for pointer type variables. VOID is a
type identifier which has not size.
NULL and void are not same.
Example: void* ptr = NULL;
Core Dimension is a Dimension table which
is used dedicated for single fact table or Datamart.
Conform
Dimension is a Dimension table which is used across fact tables or
Datamarts.

8.) How can a node be inserted in the middle of a
linked list?

By repointing the previous and the next elements of
existing nodes to the new node. You can insert a
node in the middle
of a linked list by repointing the previous and the next elements of
existing nodes to the new node.

9.) What are the various kinds of
sorting techniques? Which is has best case?

Bubble sort Quick
sort Insertion sort Selection sort Merge sort Heap sort Among the
sorting algorithms quick sort is the best one

10.) Without using
/,% and * operators. write a function to divide a number by 3?

#include

#include
void main()
{
int i,n;
float
j=0;
clrscr();
printf("enter the no");
scanf("%d",&n);
for(i=n;i>2;i=i-3)
{
j=j+1;
if(i==4)
{
j=j+1.333333;
}
if(i==5)
{
j=j+1.666666;
}
printf("%f",j);
getch();
}

11.)
What is the use of fflush() function?

The function fflush forces
a write of all buffered data for the given output or update stream via
the stream's underlying write function.

12.) What is binary tree?

A
binary tree is a tree in which every node has exactly two links i.e
left and right link

13.) Which one is faster? A binary search of
an orderd set of elements in an array or a sequential search of the
elements.

Binary search is faster because we traverse the
elements by using the policy of Divide and Conquer. we compare the
key
element with the approximately center element, if it is smaller than it
search is applied in the smaller elements only otherwise
the search
is applied in the larger set of elements. its complexity is as we all
know is log n as compared to the sequential one
whose complexity is
n.