how can i write programme with C++ that 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.......
how can i write programme with C++ that rearrange the value in a given set from max to min....
there are tons of algorithms, quicksort is a very well known example
there are several ways... my favorite is a bubble sort (pay particular attention to the part in between the big comments):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)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; }
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 01: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
hmm... I suppose there is:
But then the OP mentioned a set....Code:std::sort(c.rbegin(), c.rend());
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
...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
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.Originally Posted by laserlight
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.
Originally Posted by Rashakil Fol
I bet Brute Force is slower
to sort an array of size 100 there is 100!Code:933262154415268169923885626670049071596826438162146859293895217599993229975608941463976156518286253697920827223758251185210916864000000000000000000000000
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. :-)
Quicksort is known but may not be the greatest for his situation.Originally Posted by valis
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)
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
Bubble sort isnt that bad for small lists. It could be quicker than other algorithms on really short lists.Originally Posted by Rashakil Fol
>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.
The thing is, it might be futile if the OP was using a std::set and somehow thought that it was not already sorted.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.
Is there any advantage (aside from say, an easier implementation) of mergesort over introsort?and a variant of mergesort or introsort for large lists depending on the needs of the application (assuming any existing libraries are insufficient)
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
>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.