Like Tree2Likes
  • 1 Post By Adak
  • 1 Post By iMalc

sorting algorithm logic

This is a discussion on sorting algorithm logic within the C Programming forums, part of the General Programming Boards category; Hi all. I wrote this algorithm, which seems to work fine, I but would like to know how it could ...

  1. #1
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242

    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]);
        }
    }
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 10-08-2012 at 08:49 AM.
    cfanatic likes this.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    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.
    cfanatic likes this.
    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"

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Yes, that is a Bubble sort. Sorry for the confusion, Cfanatic.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with logic algorithm...
    By fenixink in forum C++ Programming
    Replies: 18
    Last Post: 10-05-2011, 11:00 AM
  2. Sorting Algorithm Help
    By cjwenigma in forum C++ Programming
    Replies: 8
    Last Post: 11-02-2007, 02:04 PM
  3. sorting algorithm
    By RazielX in forum C Programming
    Replies: 4
    Last Post: 05-04-2004, 06:20 PM
  4. How abt an algorithm and logic contest
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 08-12-2002, 11:06 AM
  5. 'Sorting' algorithm
    By Dual-Catfish in forum C++ Programming
    Replies: 3
    Last Post: 11-03-2001, 01:09 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21