Thread: Sorting Algorithms

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    5

    Sorting Algorithms

    Here is my program!
    Couple of things i need help with, is finding:
    1)number of comparisons for each sort(i'm doing something already, but i don't think it's correct.
    2)number of interchanges.
    3)also need to print 5 elements of array on each line.
    If someone could help, i would very much appreciate it!

    Code:
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    
    int bubbleSort(int *array,int n);
    void printElements(int *array,int n);
    int swap(int &x, int &y);
    void heapify(int a[], int lower, int upper);
    int heapsort(int a[], int numelts);
    int quicksort(int a[], int numelts);
    int partition(int a[],int lower, int upper);
    
    int main()
    {
        //int a[]={9,6,5,23,2,6,2,7,1,8,99,98};                   // BUBBBLE SORT
        //int b[]={7,10,5,209,7,8,-2,0,100,45,9,5,2,10,6};        // HEAP SORT
        //int c[] = {3,8,-9,56,10,8,22,7,100,45,-9,5,-2,10,6};    // QUICK SORT
        int a[]={0,2,5,3,6,8,1,21,23,22,32,54,57,59,61,67,69,89,90,101,100,60,167,180,199,198,254,280,299,0};//30 elements
        int b[]={0,2,5,3,6,8,1,21,23,22,32,54,57,59,61,67,69,89,90,101,100,60,167,180,199,198,254,280,299,0};//30 elements
        int c[]={0,2,5,3,6,8,1,21,23,22,32,54,57,59,61,67,69,89,90,101,100,60,167,180,199,198,254,280,299,0};//30 elements
    	int n =30;
    	int main_count=0;
    	int count=0;
        
        
        cout<<"*******BUBBLE SORT**************"<<endl<<endl;
    	cout<<"Original Array: "<<endl;
    	printElements(a,n);
        cout<<endl<<endl;
        cout<<"Sorted Array: "<<endl; 
        main_count = bubbleSort(a,n);                 //call to bubble sort  
    	printElements(a,n);
        cout<<endl;
        cout<<"Number of comparisons: "<<main_count<<endl;  
        cout<<endl<<endl;
    
        
        cout<<"*******HEAP SORT**************"<<endl<<endl;
        cout<<"Original Array: "<<endl;
    	printElements(b,n);
        cout<<endl<<endl;
        cout<<"Sorted Array: "<<endl; 
        main_count = heapsort(b,n);                //call to heap sort  
    	printElements(b,n); 
    	cout<<endl;
        cout<<"Number of comparisons: "<<main_count<<endl;
        cout<<endl<<endl;
    
    
    
        cout<<"*******QUICK SORT**************"<<endl<<endl;
    	cout<<"Original Array: "<<endl;
    	printElements(c,n);
        cout<<endl<<endl;
        cout<<"Sorted Array: "<<endl; 
        main_count = quicksort(c,n);                //call to heap sort  
    	printElements(c,n);
        cout<<endl;
        cout<<"Number of comparisons: "<<main_count<<endl; 
        cout<<endl<<endl;
    	
        
        
        system("pause");
    	return 0;
    }
    /***************************************************************************************************************
     ***************************************************************************************************************
     ***********************************************END OF MAIN()***************************************************
     ***************************************************************************************************************
     ***************************************************************************************************************/
    
    
    
    /*This function will print the elements of the
      arrays which were sorted by different sorting
      methods. It will receive an array and # of 
      elemnents as a parameter.
    */
    void printElements(int *array,int n) //print array elements
    {
    	int i=0;
    	for(i=0;i<n;i++)
    		cout<<array[i]<<" ";
    		cout<<endl;
    }
    
    
    
    
    
    /*BUBBLE SORT
      This sorting algorithm is considered inefficient or 
      stupid, because if given data in reverse order, it
      will do a horrible job. It will make n^2(O(n^2)) comparisons.
      Bubble Sort works by comparing two adjacent items,
      and moves them if there is a need. Bubble Sort will
      work best on almost sorted order. It will have about n-1
      comparisons. This function will receive an array and a # of
      elements to process, as a parameter. This function will only return 
      count of comparisons made.
    */
    int bubbleSort(int *array,int n)//Bubble sort function 
    {
    	int i,j;
    	int count=0;
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<i;j++)
    		{
                count++;//count # of comparisons
    			
                if(array[i]<array[j])
    			{                 
    				int temp=array[i]; //swap 
    				array[i]=array[j];
    				array[j]=temp;
    			}
    
    		}
    
    	}
      return count;
    }
    
    
    
    
    
    
    /*This function will be used by both HEAP SORT and
      QUICK SORT. It will be used for interchenging
      items when required by algorithm. It will receive 
      two reference parameters x and y, and will not 
      return an answer.
    */
    int swap(int &x, int &y)
    {
         int temp;
    
    	temp = x;
    	x = y;
    	y = temp;
    	
    
    	return count;
    }
    
    
    
    /*This function will be used by HEAP SORT algorithm.
      It will be used keep the tree that is being sorted
      balanced - that is the major advantage of max heap
      over other sorts. It will receive an array to be sorted,
      and two integers lower and upper. This function will be
      called by heapsort().
    */
    void heapify(int a[], int lower, int upper)
    {
    	int parent = lower, child;
    
    	while (parent <= (upper+1)/2 - 1) {
    	     child = 2 * parent + 1;
    		if (child < upper && a[child] < a[child+1]){
    		    child++;
    		  
               }
    		if (a[child] > a[parent]) {
     		    swap(a[parent],a[child]);
    		    parent = child;
    		   
    		}
    		else
    	         return;
    	}
         return;
    }
    
    
    
    /*HEAP SORT
      This function will construct a heap and then reads
      of values. This functions will be called ny MAIN(),
      after which this function will call heapify().  
    */
    int heapsort(int a[], int numelts)
    {
        int count=0;
        
    	for (int i = numelts/2 - 1; i >= 0; i--){
    	     heapify(a,i,numelts - 1);
    	   
        }
    
    	for (int i = numelts - 1; i > 0; i--) {
    	     swap(a[0],a[i]);
    	     count++;
    		heapify(a,0,i-1);
         }
         return count;
    }
    
    
    /*This function will be used/called by quicksort().
      This function will select a position (xpos) to send
      partition and then will move array elements to the
      left or right side of position
    */
    int partition(int a[],int lower, int upper)
    {
    	  int lo = lower, hi = upper, xpos = lower;
    	  int x = a[lower];
    
    	  while(lo <= hi) {
    			while (hi >= lo && x <= a[hi]){
    				 hi--;
    				
                  }
    			if (hi >= lo) {
    				  a[lo] = a[hi];
    				  xpos = hi;
    				  lo++;
    				  
    			}
    			while (lo <= hi && x >= a[lo]){
    				  lo++;
    				 
                  }
    			if (lo <= hi)  {
    				 a[hi] = a[lo];
    				 xpos = lo;
    				 hi--;
    				 
    			}
    	}
    
    	if (xpos != lower)
    	    a[xpos] = x;
    	  
    
    	return xpos;
    }
    
    
    /*This function will be used/called by quicksort().
      This function will use a value xpos, returned
      by partition(), in order to continue the process.
    */
    void qsort(int a[], int lower, int upper)
    {
    	  int pos;
    	  
    
    	  if (lower >= upper)
    	 
    		return;
    	  pos = partition(a,lower,upper);
    	 
    	  qsort(a,lower,pos-1);
    	
    	  qsort(a,pos+1,upper);
    	  
    	  return;
      
    }
    
    /*QUICK SORT
      This function will be responsible for sorting an
      array using Quick Sort method. It will work by 
      picking a certain element(pivot), then it wil move all
      elements smaller to the left, and all larger to the right. The
      process wil be repeated untill the array is sorted. The function
      will operate recursively. Function receives array as a parameter
      and # of elements. It will be called by MAIN()
    */ 
    int quicksort(int a[], int numelts)
    {
         int count=0;
    	 qsort(a,0,numelts-1);
    	 count++;
    	 return count;
    }
    Last edited by Salem; 05-19-2009 at 08:29 AM. Reason: Added [code][/code] tags, learn to use them yourself

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Using code-tags would help a bit...

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    What don't you understand how to do? Just create 2 counters for each function. If you make a swap add 1 to your swapped counter. Also if you make a comparison add 1 to your comparison counter.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    That's not bubble sort. Bubble Sort only swaps adjacent items and as such an item gradually moves over until it is in place. Since you're not swapping adjacent items, it's actually just moving the next best item directly into the same place repeatedly each loop.
    The way you are counting the comparisons for that algorithm will work, however you're not counting the number of swaps as well. WHy don't you use that swap function that you're made right below it?
    Note, bubble sort is not stupid. It is actually a good choice when there are fewer than about 8 items.

    You're not counting comparisons at all in heap sort. You're also ignoring the count of the number of swaps. You need to actually do something with the return value the way you're got it written at the moment.

    You're not attempting to count anything in quicksort, except the number of times it is called (always 1).

    The best way to count these things is to sort objects instead of integers. The objects only need to hold an integer, but you can customise the less-than operator to count the comparisons. You can provide a swap method that counts how many times it is called as well. That way you wont need and kind of count++; inside the sorting algorithm at all.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    5
    yes, i understand that i have to have counters, the only problem is where to place them?
    i tried placing them under swaps and comparisons, but it doesn't give the right answer.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by ashir30000 View Post
    yes, i understand that i have to have counters, the only problem is where to place them?
    i tried placing them under swaps and comparisons, but it doesn't give the right answer.
    Any time your code is about to compare two items you'll need to increment the count, much like you are in your "bubbleSort" function.

    But you have a more pressing problem to solve first. How do you plan on getting the number of comparisons and the number of swaps back to your main function? You can't return both from the sorting routines unless you use some kind of struct or a std::pair. You might be better off (for your ability level) to just declare the counts as global. Remember to zero them before calling each sort routine of course.
    From then it's really quite simple. As your code is about to compare items, increment the number of comparisons. If the code is swapping items, then increment the swap count.

    Like I said though, that isn't Bubble Sort, and the difference for that algorithm with almost sorted data vs random ordering is pretty marginal. The exact number of item comparisons for that method is 0.5*(n*n - n) in every case.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    5
    Thanks for reply iMalc!
    I considered using references to get answers to main(), but i think global will work better!

    about bubble sort, the analysis you provided (0.5*(n*n - n)), resembles one of linear(insertion) sort.
    This is the bubble I've always used. If you have a better one, I'd love to look at it.

    Thanks again!

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by ashir30000 View Post
    Thanks for reply iMalc!
    I considered using references to get answers to main(), but i think global will work better!

    about bubble sort, the analysis you provided (0.5*(n*n - n)), resembles one of linear(insertion) sort.
    This is the bubble I've always used. If you have a better one, I'd love to look at it.

    Thanks again!
    Here is an implementation of BubbleSort.
    Code:
    void BubbleSort(int a[], int n) {
    	for (int i = n-1; i > 0; --i) {
    		for (int j = 0; j < i; ++j) {
    			if (a[j + 1] < a[j])
    				std::swap(a[j], a[j + 1]);
    		}
    	}
    }
    Note the swapping of j and j+1 rather than swapping i and j.

    Insertion Sort has the same number of comparisons in the worst case, but can be fewer most of the time.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    5
    Thanks iMalc!

    is swap() included in std namespace?

  10. #10

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. Sentinel in sorting algorithms
    By Albinoswordfish in forum C Programming
    Replies: 2
    Last Post: 12-17-2008, 03:21 AM
  4. Sorting Algorithms with Time
    By silicon in forum C++ Programming
    Replies: 3
    Last Post: 05-03-2005, 11:27 AM
  5. recommendations on sorting algorithms
    By btq in forum C++ Programming
    Replies: 4
    Last Post: 10-14-2002, 11:36 AM

Tags for this Thread