Thread: what do you think about this simple sorting algorithm?

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    48

    what do you think about this simple sorting algorithm?

    hi to everyone. I need to reverse an array. I made this simple algorithm, and i want to know what would you change of it, and also want to know an algorithm that you recommend for doing this task.

    Code:
    void sort()
    {
        int array[5];                                          // array to reverse
        int lowIndex, highIndex;                      // lower and higher indexes in the array
        int lowElement, highElement;              // lower and higher elements in the array
    
        array[0] = 1;
        array[1] = 2;
        array[2] = 3;
        array[3] = 13;
        array[4] = 5;
    
        lowIndex = 0;
        highIndex = 4;                                  // This is array's length at first
        
        while ( highIndex >= lowIndex )
        {  
            // storage lower and higher elements
            lowElement = array[lowIndex];
            highElement = array[highIndex];
    
            // change their index
            array[lowIndex] = highElement;
            array[highIndex] = lowElement;
    
            // counters
            lowIndex += 1;
            highIndex -= 1;        
        }
    
        int i;
    
        for ( i = 0 ; i < 5 ; i++ )
        {
            printf ( "%i\n" , array[i] );
        }   
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    This isn't sorting anything, just reversing.

    Technically you only need one extra piece of storage to swap two numbers, but (a) 4 bytes isn't going to hurt anybody these days and (b) your compiler might be able to optimize it away anyway.

    You don't need to swap in the case that lowIndex == highIndex, so you can change that while condition.

    In terms of reversing in place, I don't think you'll be able to do much better than this.

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    48
    You're right, i might change post title. Sorry about that, i thought that reversing an array was a part of sorting it, but actually what i'm sorting here is array's indexes not array elements.
    Thanks about the while condition and that unnecesary four bytes. I've changed it.

    Code:
    void sort()
    {
        int array[5];
        int lowIndex, highIndex;
        int lowElement;
        array[0] = 1;
        array[1] = 2;
        array[2] = 3;
        array[3] = 13;
        array[4] = 5;
        
        lowIndex = 0;
        highIndex = 4;   
        
        while ( highIndex > lowIndex )
        {        
            lowElement = array[lowIndex];
            array[lowIndex] = array[highIndex];
            array[highIndex] = lowElement;
            lowIndex += 1;
            highIndex -= 1;        
        }
    
        int i;
    
        for ( i = 0 ; i < 5 ; i++ )
        {
            printf ( "&#37;i\n" , array[i] );
        }   
        
    }
    Last edited by mariano_donati; 02-22-2008 at 10:58 AM. Reason: Forgot to post new code

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Sorry about that, i thought that reversing an array was a part of sorting it, but actually what i'm sorting here is array's indexes not array elements.
    So what are you actually trying to do?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Nov 2007
    Posts
    48
    Reversing it.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Reversing it.
    Okay, so far your code looks fine, though changing the while loop to a for loop might make it clearer, and I believe that in C you should declare your variables at the start of the block, so int i; is out of place.

    I suggest that you change:
    Code:
    void sort()
    to:
    Code:
    void reverse(int array[], size_t size)
    then rewrite the code to be more general in terms of the size of the input array.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    A tad bit lighter.
    Code:
    #include <stdio.h> 
    
    
    void sort()
    {
    	int array[5];                             // array to reverse
    	int loopsNeeded ;                              // lower and higher indexes in the array
    	int tempElement ;              
    	int maxIndex , i ; 
    
    	array[0] = 1;
    	array[1] = 2;
    	array[2] = 3;
    	array[3] = 13;
    	array[4] = 5;
    
    	maxIndex = 4 ; 
    	loopsNeeded = (5+1)/2 ; 
    
    	for (i = 0 ; i < loopsNeeded ; ++i) 
    	{  
    		// Swap ends 
    		tempElement = array[i] ;
    		array[i] = array[maxIndex-i] ; 
    		array[maxIndex-i] = tempElement ; 
    	}
    
    	for ( i = 0 ; i <= maxIndex ; i++ )
    	{
    		printf ( "&#37;i\n" , array[i] );
    	}   
    }
    
    int main(void) { 
    	sort() ; 
    	return 0 ; 
    }
    Mainframe assembler programmer by trade. C coder when I can.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Don't add 1 when calculating loopsNeeded. The middle item can stay untouched
    Code:
    	loopsNeeded = _countof(array)/2 ;
    The iterator approach:
    Code:
    int *begin = &array[0];
    int *end = &array[_countof(array)];
    while (begin < --end)
    {
    	int tempElement = *end;
    	*end = *begin; 
    	*begin++ = tempElement;
    }
    Last edited by iMalc; 02-22-2008 at 01:02 PM.
    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
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Quote Originally Posted by iMalc View Post
    Don't add 1 when calculating loopsNeeded. The middle item can stay untouched
    You are right. I was thinking 1st, 2nd, 3rd, and should have been thinking 0th, 1st, 2nd. My intent was to ignore the middle element in an odd-sized array.
    Mainframe assembler programmer by trade. C coder when I can.

  10. #10
    Registered User
    Join Date
    Nov 2007
    Posts
    48
    thanks!, i knew if a made a post here you would reply me with this kind of answers. I really appreciate it. Thanks again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Sort the best sorting algorithm?
    By sehr alt in forum A Brief History of Cprogramming.com
    Replies: 21
    Last Post: 06-20-2007, 02:19 PM
  2. simple hashing algorithm??
    By iori in forum C Programming
    Replies: 7
    Last Post: 04-14-2003, 05:18 PM
  3. I need help with sorting a simple structure please
    By AlmostBeginner in forum C Programming
    Replies: 2
    Last Post: 04-11-2003, 03:01 AM
  4. a simple algorithm and questions
    By ustuzou in forum C++ Programming
    Replies: 0
    Last Post: 02-18-2002, 11:12 AM
  5. Simple File Creation Algorithm
    By muffin in forum C Programming
    Replies: 13
    Last Post: 08-24-2001, 03:28 PM