Thread: sorting algorithm logic

Hi all.

I wrote this algorithm, which seems to work fine, I but would like to know how it could be improved? I know that (size -1) iterations is required to do one pass(inner loop), and added an outer loop with the same number of iterations for no good reason. No logic to this line of thinking at all.

So I am now thinking that there are excess iterations with this algorithm(once again, not based on logic, just a hunch), meaning that the sorting will completed way before the outer loop has finished. Based on logic, how do I determine exactly what the number of iterations is required for the outer loop to do the job efficiently?

Thanks in advance.

Code:

#include <stdio.h>

int * sort(int array[], int size);
void display(int array[], int size);

int main(void)
{
    int array[10] = {4, 12, 8, 0, 32, 2000, 234, 786, 56, 3456};

    sort(array, 10);
    display(array, 10);

    return 0;
}

int * sort(int array[], int size)
{
    int ctr, ctr1, temp;

    for(ctr = 0; ctr < size - 1; ctr++)
    {
        for(ctr1 = 0; ctr1 < size - 1; ctr1++)
        {
            if(array[ctr1] < array[ctr1 + 1])
            {
                continue;
            }
            else
            {
                temp = array[ctr1];
                array[ctr1] = array[ctr1 + 1];
                array[ctr1 + 1] = temp;
            }
        }
    }
    return array;
}

void display(int array[], int size)
{
    int ctr;

    for(ctr = 0; ctr < size; ctr++)
    {
        printf("%d \n", array[ctr]);
    }
}

Your sorting algorithm, is a Substitution sort, which is very similar to a Bubble sort. Yours is lacking (as you guessed), essential changes to improve it:

Code:

    for(ctr = 0; ctr < size - 1; ctr++)
    {
        for(ctr1 = 0; ctr1 < size - 1; ctr1++)
        {
            if(array[ctr1] < array[ctr1 + 1])
            {
                continue;
            }
            else
            {
                temp = array[ctr1];
                array[ctr1] = array[ctr1 + 1];
                array[ctr1 + 1] = temp;
            }
        }

//Substitution sort:
for(i=0;i<SIZE-1;i++) {       //note SIZE-1
   for(j=i+1;j<SIZE;j++) {    //note the i+1 starting value
      if(array[i] > array[j]) {
          temp = array[i];
          array[i] = array[j];
          array[j] = temp;
      }      
   }
}

A Substitution sort has run-time performance very similar to a Bubble sort. I prefer the Substitution sort algorithm, because it's easy to code correctly from memory.

For a better sorter, look into Insertion sort, which is VERY fast sorting less than 100 items, AND even faster if the data to be sorted, is already partly sorted. It's also stable, and a great way to optimize a big item sorter, like Quicksort.

But it swaps adjacent items here. Looks exactly like bubble sort to me, although it has an off-by-one which causes a buffer overrun.

Two ways of reducing the work of bubblesort are:
To use an extra flag, or
To keep track of where the last swap occurred on each pass.