# Sorting Algorithms

• 05-19-2009
ashir30000
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; }```
• 05-19-2009
matsp
Using code-tags would help a bit...

--
Mats
• 05-19-2009
linuxdude
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.
• 05-19-2009
iMalc
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.
• 05-20-2009
ashir30000
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.
• 05-20-2009
iMalc
Quote:

Originally Posted by ashir30000
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.
• 05-20-2009
ashir30000
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!
• 05-20-2009
iMalc
Quote:

Originally Posted by ashir30000
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.
• 05-21-2009
ashir30000
Thanks iMalc!

is swap() included in std namespace?
• 05-21-2009
cyberfish