Like Tree1Likes

Need help sorting arrays

This is a discussion on Need help sorting arrays within the C Programming forums, part of the General Programming Boards category; Oh, don't know what algorithm, I just do it my way actually. Code: /* AUTH: Kevin Strijbos DATE: 17/01/2012 DESCR: ...

  1. #16
    Registered User
    Join Date
    Jan 2012
    Posts
    69
    Oh, don't know what algorithm, I just do it my way actually.

    Code:
    /* AUTH: Kevin Strijbos   DATE: 17/01/2012
       DESCR: includes 2 functions that combine arrays
       */
    
    
    #include <stdio.h>
    
    
    #define MAX_LENGTH 10
    
    
    void initializeArray (int numbers[], int *pointers[]);
    void initializeMinima (int *pointers[]);
    
    
    int main (void)
    {
    	int numbers[MAX_LENGTH];
    	int *pointers[MAX_LENGTH];
    	int counter;
    
    
    	for (counter = 0; counter < MAX_LENGTH ;counter++)
    	{
    		printf("Give a number:\t\n");
    		scanf("%d", &numbers[counter]);
    	}
    
    
    	
    	initializeArray(numbers,pointers);
    
    
    	for (counter = 0; counter < MAX_LENGTH ;counter++)
    		printf("Element %d:\t%d\n", counter, *pointers[counter]);
    
    
    	initializeMinima(pointers);
    
    
    	printf("-----------------------------------\n");
    
    
    	for (counter = 0; counter < MAX_LENGTH ;counter++)
    		printf("Element %d:\t%d\n", counter, *pointers[counter]);
    
    
    	return 0;
    }
    
    
    void initializeArray (int numbers[], int *pointers[])
    {
    	int counter;
    
    
    	for (counter = 0; counter < MAX_LENGTH ;counter++)
    		pointers[counter] = &numbers[counter];
    }
    
    
    void initializeMinima (int *pointers[])
    {
    	int *temp, index, minima, counter, smallCounter;
    
    
    	for (counter = 0; counter < MAX_LENGTH - 1 ;counter++)
    	{
          minima = *pointers[counter];
          index = counter;
    
    
          for (smallCounter = counter + 1; smallCounter < MAX_LENGTH ;smallCounter++)
          {
             if (*pointers[smallCounter] < minima)
             {
                minima = *pointers[counter];
                index = smallCounter;
             }
          }
    
    
          /* swapping minima */
          temp = pointers[counter];
          pointers[counter] = pointers[index];
          pointers[index] = temp;      
       }
    }
    Btw: copied the source code and created a new project, still no errors nor warnings.

  2. #17
    Registered User
    Join Date
    Jan 2012
    Posts
    69
    The other student put the swap part in the if test and it worked, maybe that's a clue?

  3. #18
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by kevinstrijbos View Post
    Oh, don't know what algorithm, I just do it my way actually.
    Quote Originally Posted by kevinstrijbos View Post
    The other student put the swap part in the if test and it worked, maybe that's a clue?
    If you don't know how it works, how can you expect to fix it?


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #19
    Registered User
    Join Date
    Jan 2012
    Posts
    69
    I know how it works, I just don't know how the algorythm's called, nor if it exists. I implemented this method at least 10 times in java and I had no problems with it, worked like a charm.
    But what I've figured out till now; if you put the swap part in the if-test in the 2nd for loop (bubble sort), it works. But it really isn't that much of a difference.

    Don't know what it is, I'll just use bubble from now on...

  5. #20
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Oh, don't know what algorithm, I just do it my way actually.
    That's what I did the first time I had to sort something too, and it also turned out to be "bubble sort". I was pretty impressed when I saw some of the other ideas people have had thru the years, lol.

    Actually, it's not even really bubblesort, because of the inner loop. It's just bubble-esque, and probably even more inefficient (no offence -- I guess that doesn't matter for now).

    But since your code does now compile cleanly, time to think about the logic of your algorithm. Can you describe in words what you believe it is supposed to do (like, in detail, pseudocode maybe)?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #21
    Registered User
    Join Date
    Jan 2012
    Posts
    69
    To be honest I'm indeed surprised "Aha, I'm not the only one!".

    What I want it to do:
    I need to found length -1 minimas, so I make a for loop that runs till length - 1 (MAX_LENGTH - 1).
    I need to initialise my minimum, so I make the element with index counter the minimum, and I make my index = counter, so I know where my current minimum is.
    Next I need to check if there's another number left (one that isn't already "chosen" as a minimum) in my array, so I put up a 2nd counter (smallCounter).
    If I find a value smaller than my current minimum, I make that value my minimum and I put smallCounter in "index" (so that I know where my current minimum is...)
    When the 2nd loop is finished, I just swap.

    I hope my explanation is a little bit clear?

    PS: efficiency indeed doesn't matter currently, they just want it to be "clean" code, so that it's easy to read, and I think it's pretty clean since you all can read and understand it .

  7. #22
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    Actually, I think your sort most resembles selection sort. You find the smallest element in the list and put it at the beginning. Then you do the same for sub-arrays starting at index 1, 2, 3, ..., n-1. Bubble sort would have the swap inside the inner loop.

  8. #23
    Registered User
    Join Date
    Jan 2012
    Posts
    69
    Oh well, all the same for me.

    EDIT: Followed the link and it's indeed rather selection sort, and it mostly outperforms bubble sort. Take that MK27! Haha, just joking.
    Last edited by kevinstrijbos; 01-17-2012 at 03:41 PM.
    MK27 likes this.

  9. #24
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    FYI kevinstrijbos, the algorithm you have been using is selection sort.
    The inner loop selects the smallest (or largest) item and the outer loop swaps that into the correct place each time.

    This is perfectly fine for sorting 10 items. When you need to sort 10000 or more items some day then you'll probably want to look into something better!
    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"

  10. #25
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Selection sort is faster than a crude Bubble sort, but slower than an optimized Bubble sort, or any other (serious) sorting algorithm. It's "claim to fame" is that it will always use the fewest number of swaps of any comparison sorting algorithm.

    If you were the Avis parking lot attendant, and your boss said you had to sort all the 1,000 cars parking in the parking lot, you'd definitely want to use the logic from Selection sort. Minimum cost of making comparisons (just glance at the cars), but costly to make the swaps (you need to drive the car from space to space).

    Other than that, it's never the best choice for sorting. For a small (less than 100) number of items, especially if it's nearly sorted, Insertion sort rocks. For larger quantities, Shell sort (which is Insertion sort with varying gaps), is quite effective and not complicated. For a large or huge number of items, Quicksort (perhaps optimized with Insertion sort, giving it a nice boost!) and Merge sort, are two of the best sorting algorithms.

    Sorting has some wonderful, and well studied algorithms; well worth your studying.
    Last edited by Adak; 01-18-2012 at 01:44 AM.

  11. #26
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by Adak View Post
    Selection If you were the Avis parking lot attendant, and your boss said you had to sort all the 1,000 cars parking in the parking lot, you'd definitely want to use the logic from Selection sort. Minimum cost of making comparisons (just glance at the cars), but costly to make the swaps (you need to drive the car from space to space).
    Actually, the option that is the fastest when moving items is hideously expensive would be to use "Exact Sort" whose number of item moves is at most n+1, whereas Selection Sort is up to 3(n-1). (There being 3 moves in a swap)

    Other than that, it's never the best choice for sorting. For a small (less than 100) number of items, especially if it's nearly sorted, Insertion sort rocks. For larger quantities, Shell sort (which is Insertion sort with varying gaps), is quite effective and not complicated. For a large or huge number of items, Quicksort (perhaps optimized with Insertion sort, giving it a nice boost!) and Merge sort, are two of the best sorting algorithms.[/QUOTE]Perhaps if you're just sorting ints, but even for small numbers, if the data type is slow to move then selection sort is good.

    There's generally about three main classes of sorting algorithm that you ever need, meaning that you can get by with everything just knowing three sorting algorithms:
    O(n*n) for when there are very few items
    O(n*log n) when there are a lot of items
    O(n) for when there are a ridiculously large number of items and the data type allows bucket sorting etc.
    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"

  12. #27
    Registered User
    Join Date
    Jan 2012
    Posts
    69
    Hmmhmm, but I've heard about something like quantum-sort? It appears that it is O(n), doesn't matter which array?

  13. #28
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Radix sort and similar are O(n), but they only work for a limited class of inputs (Linear-Time Sorting). And practically speaking, the constant factors ignored by big-O notation seem to matter in their real-world run times.

    I'd imagine quantum sorting would be O(1) in time complexity, with some potentially unfortunate implementation details (starting with a total lack of hardware on which to run the algorithm).

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Can i get some help with sorting arrays
    By airitout717 in forum C++ Programming
    Replies: 1
    Last Post: 12-03-2011, 03:15 AM
  2. Replies: 16
    Last Post: 01-01-2008, 03:07 PM
  3. Replies: 2
    Last Post: 02-23-2004, 05:34 AM
  4. Help with sorting arrays
    By Silence in forum C Programming
    Replies: 5
    Last Post: 05-17-2002, 10:05 AM
  5. Sorting Arrays
    By Jax in forum C Programming
    Replies: 3
    Last Post: 11-11-2001, 11:35 AM

Tags for this Thread


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