Thread: Whats wrong with my sorting algorithm?

I'm just trying to get a simple sorting by swapping algorithm to work on an existing unsorted array..

Code:

                                int a, b;
                                for (a = 0;a<count;a++)
                                {
                                        for (b=0;b< count;b++)
                                        {
                                                if (FREQUENCY[count] > FREQUENCY[count-1])
                                                {
                                                        int temp;
                                                        

                                                       
                                                       
                                                        temp = FREQUENCY[count];


                                                        FREQUENCY[count] = FREQUENCY[count-1];

                                                       
                                                        FREQUENCY[count - 1] = temp;
                                                }
                                        }
                                }

It's supposed to sort with the largest element being the first element and the lowest being the last. As the title says, what's wrong with it?

You should be using b to index the array, not count. count never changes in the loop.

You should forget using count, inside the for loops - that is just the controller so the for loops know when to stop.

You want to do something like this:

Code:

int a, b, temp;
for(a=0;a<count-1;a++) {
   for(b=a+1;b<count;b++) {
      if(frequency[a] < frequency[b]) {  //out of order?
         temp=frequency[a];
         frequency[a]=frequency[b];
         frequency[b]=temp;
      }
   }
}

Although similar to a bubble sort, it's actually a Substitution sort.

Originally Posted by Adak

You should forget using count, inside the for loops - that is just the controller so the for loops know when to stop.

You want to do something like this:

Code:

int a, b, temp;
for(a=0;a<count-1;a++) {
   for(b=a+1;b<count;b++) {
      if(frequency[a] < frequency[b]) {  //out of order?
         temp=frequency[a];
         frequency[a]=frequency[b];
         frequency[b]=temp;
      }
   }
}

Although similar to a bubble sort, it's actually a Substitution sort.

Does that have a better Time case than bubble sort or is it still O(n^2)?

It's an optimization of bubble sort, not a different sort. You can read about it here, as what Adak wrote is logically equivalent to the second example.

It has the same complexity as Bubble sort. In tests on random integers, it sorts faster than a naive Bubble sort, but is slower than an optimized Bubble sorter that includes the swapped flag to tell it when it can stop sorting. Especially if the data is not random, but already partially sorted.

Aside from being short and easy to memorize and code correctly, it has no particular practical use - a lot like Bubble sort. It is difficult to find a name for it, because it's frequently called Bubble sort, etc. (even by me). I had to go back to an old, old file, to find the name. That's the big advantage Bubble sort has always enjoyed - a catchy name.