rearrange the value in a given set from max to min

This is a discussion on rearrange the value in a given set from max to min within the C++ Programming forums, part of the General Programming Boards category; how can i write programme with C++ that rearrange the value in a given set from max to min.......

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    4

    rearrange the value in a given set from max to min

    how can i write programme with C++ that rearrange the value in a given set from max to min....

  2. #2
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357
    there are tons of algorithms, quicksort is a very well known example

  3. #3
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    there are several ways... my favorite is a bubble sort (pay particular attention to the part in between the big comments):
    Code:
    #include<iostream>
    #include<cstdlib>
    #include<ctime>
    
    int main()
    {
            const short int SIZE=25;
            srand(static_cast<unsigned int>(time(0)));
            int numbers[SIZE];
            int temp;
    
            std::cout<<"Unsorted: ";
    
            for(register short int i=0;i<SIZE;i++)  //loop through the array
            {
                    numbers[i]=1+rand()%100;        //initialize to random values
                    std::cout<<numbers[i]<<",";     //output unsorted array
            }
    
            /*********************************************************************/
            /*                      BEGIN BubbleSort                             */
            /*********************************************************************/
    
            for(register short int i=0;i<SIZE;i++)  //loop through each number in the array
            {
                    for(register short int x=SIZE;x>0+i;x--)        //loop through every unsorted number left
                    {                                               //starting at the bottom and moving up
                            if(numbers[x]<numbers[i])       //if the number is smaller
                            {
                                    temp=numbers[i];
                                    numbers[i]=numbers[x];  //these three lines are a swap
                                    numbers[x]=temp;
                            }
                    }
            }
    
            /*********************************************************************/
            /*                      END BubbleSort                               */
            /*********************************************************************/
    
            std::cout<<"\nSorted: ";
    
            for(register int i=0;i<SIZE;i++)        //loop through them all again
            {
                    std::cout<<numbers[i]<<",";     //output the sorted array
            }
    
            std::cout<<std::endl;
            return 0;
    }
    edit: I did min to max, but I'm sure you could figure out how to change that... and there are more efficient ways of doing it... IMO, this is the easiest (at least to remember)

    edit2: and because I did a bad job explaining how it works: http://en.wikipedia.org/wiki/Bubble_sort
    Last edited by major_small; 07-17-2005 at 12:10 AM.
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,645
    hmm... I suppose there is:
    Code:
    std::sort(c.rbegin(), c.rend());
    But then the OP mentioned a set....
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    ...but that takes all the fun out of it
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  6. #6
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by laserlight
    hmm... I suppose there is:
    Code:
    std::sort(c.rbegin(), c.rend());
    But then the OP mentioned a set....
    This could have meant 'array'. I've had exams where I lost 25 points on a question because I assumed 'set' meant balanced binary search tree.

  7. #7
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Bubble sort? No. The only worse sorting algorithm I know of is "Swap randomly, check if new array is sorted; if not then repeat."

    Bubble sort is slow. Slower than the other slow algorithms, really. Read the wikipedia link.

  8. #8
    Registered User mrafcho001's Avatar
    Join Date
    Jan 2005
    Posts
    483
    Quote Originally Posted by Rashakil Fol
    Bubble sort? No. The only worse sorting algorithm I know of is "Swap randomly, check if new array is sorted; if not then repeat."

    Bubble sort is slow. Slower than the other slow algorithms, really. Read the wikipedia link.

    I bet Brute Force is slower
    to sort an array of size 100 there is 100!
    Code:
    933262154415268169923885626670049071596826438162146859293895217599993229975608941463976156518286253697920827223758251185210916864000000000000000000000000

  9. #9
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Hmm. Brute force with permutations is pretty bad, you're right. There are cases that take n * n! time.

    Random swapping's average runtime grows at the same pace as brute force's :-)

    I suppose that if your datatype only has a finite possible number of values, such as int, you could also do brute force in the sense of generating every possible array of length n and checking to see if that is a sorted permutation of the original array. :-)

  10. #10
    *this
    Join Date
    Mar 2005
    Posts
    498
    Quote Originally Posted by valis
    there are tons of algorithms, quicksort is a very well known example
    Quicksort is known but may not be the greatest for his situation.
    Insertion sort will do perfectly for your situation and its easy to understand. Since I assume you are a beginner, look into bubble sort, insertion sort, and mergesort. You can figure out which is appropriate for your situation.

    My favorite is mergesort (non-recursive version)

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,645
    I like the accelerated heapsort described in "Computer Algorithms: Introduction to Design & Analysis" by Sara Baase and Allen Van Gelder, but then the OP still hasnt posted to clarify just what he/she meant by 'set'.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    *this
    Join Date
    Mar 2005
    Posts
    498
    Quote Originally Posted by Rashakil Fol
    Bubble sort? No. The only worse sorting algorithm I know of is "Swap randomly, check if new array is sorted; if not then repeat."

    Bubble sort is slow. Slower than the other slow algorithms, really. Read the wikipedia link.
    Bubble sort isnt that bad for small lists. It could be quicker than other algorithms on really short lists.

  13. #13
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Bubble sort isnt that bad for small lists.
    Small lists have a tendency to become big lists. Better to pick a decent algorithm from the start. For the general case I would suggest Shellsort for handling small to medium size lists and a variant of mergesort or introsort for large lists depending on the needs of the application (assuming any existing libraries are insufficient). Of course, there's also a lot to be said about using the correct data structure in the first place. If you find yourself sorting a lot, it could mean you aren't using the right data structure.

    >but then the OP still hasnt posted to clarify just what he/she meant by 'set'.
    Well, since the std::set container keeps its data ordered already, we can safely assume that "set" means a collection of items treated as a single entity but not necessarily ordered, such as an array or linked list.

    >my favorite is a bubble sort
    Dare I ask why?
    My best code is written with the delete key.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,645
    Well, since the std::set container keeps its data ordered already, we can safely assume that "set" means a collection of items treated as a single entity but not necessarily ordered, such as an array or linked list.
    The thing is, it might be futile if the OP was using a std::set and somehow thought that it was not already sorted.

    and a variant of mergesort or introsort for large lists depending on the needs of the application (assuming any existing libraries are insufficient)
    Is there any advantage (aside from say, an easier implementation) of mergesort over introsort?

    EDIT:
    oh, wait, I think I can name one - stability?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >The thing is, it might be futile if the OP was using a std::set and somehow thought that it was not already sorted.
    Maybe, but by assuming one or the other, we introduce debate about the original question, both questions end up getting answered, and the OP is happy either way.

    >Is there any advantage (aside from say, an easier implementation) of mergesort over introsort?
    Well, you can bring all of the reasons together into one: mergesort is simply better if you only have sequential access to the data, such as with linked lists or streams.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Ranged numbers
    By Desolation in forum Game Programming
    Replies: 8
    Last Post: 07-25-2006, 10:02 PM
  2. Trying to set a max for my variable...
    By GameGenie in forum C++ Programming
    Replies: 5
    Last Post: 08-23-2005, 06:55 PM
  3. Game of life
    By JoshR in forum C++ Programming
    Replies: 30
    Last Post: 04-03-2005, 02:17 PM
  4. Double output!
    By Spurnout in forum C++ Programming
    Replies: 3
    Last Post: 11-02-2002, 02:35 AM
  5. My graphics library
    By stupid_mutt in forum C Programming
    Replies: 3
    Last Post: 11-26-2001, 05:05 PM

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