simplified bubble sort c++

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

Join Date: Nov 2006
Posts: 11
Reputation: d1e9v85 is an unknown quantity at this point 
Solved Threads: 0
d1e9v85 d1e9v85 is offline Offline
Newbie Poster

simplified bubble sort c++

 
0
  #1
Nov 21st, 2006
hi guys ...

this is a bubble sort program that i made
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #include<iomanip>
  5. using std::setw;
  6.  
  7. int main()
  8.  
  9. {
  10. const int arraysize = 10;
  11. int Bubble[ arraysize ];
  12.  
  13. cout << "Please enter 10 integers: " << endl;
  14.  
  15. for ( int i = 0; i < arraysize; i++ )
  16. cin >> Bubble[ i ];
  17.  
  18.  
  19. cout <<"unsorted array:\n";
  20.  
  21.  
  22. for ( int j = 0; j < arraysize; j++ )
  23. cout << setw( 4 ) << Bubble[ j ];
  24.  
  25. for(int y=0; y < arraysize; y++)
  26.  
  27. {
  28.  
  29. for ( int k =0; k < arraysize -1-y; k++ )
  30.  
  31. if(Bubble[k]>Bubble[k+1])
  32.  
  33. {
  34.  
  35. int temp = Bubble[k+1];
  36.  
  37. Bubble[k+1] = Bubble[k];
  38.  
  39. Bubble[k] = temp;
  40.  
  41. }
  42.  
  43. }
  44.  
  45.  
  46. cout << "\nSorted Bubble array:\n";
  47.  
  48. for (int l = 0; l < arraysize; l++ )
  49. cout << setw( 4 ) << Bubble[ l ];
  50.  
  51. cout << endl;
  52. return 0;
  53. }

now the problem i am getting is that :
the data in the array may be already in the proper order or near proper order, this can be done in fewer passes than nine...
how can i modify this sort to check at the end of each pass if any swaps have been made. if none have been made then the data must been in proper order so the program should terminate if the swap has been made then atleast one more pass is needed


please helpp

thank you
Last edited by ~s.o.s~; Nov 21st, 2006 at 2:37 pm.
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 15,435
Reputation: Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute 
Solved Threads: 1471
Team Colleague
Featured Poster
Ancient Dragon's Avatar
Ancient Dragon Ancient Dragon is online now Online
Still Learning

Re: simplified bubble sort c++

 
0
  #2
Nov 21st, 2006
create a bool flag before the loop starts and set it to false. when a swap is made change the flag to true. on next loop iteration if the flag is still false then no swaps were performed during the previous loop iteration.

and please next time use code tags.
Last edited by Ancient Dragon; Nov 21st, 2006 at 2:40 pm.
Don't PM me with questions -- you might get a nasty PM in response. If you have a question then post it in one of the forums.
Reply With Quote Quick reply to this message  
Join Date: Jun 2006
Posts: 7,619
Reputation: ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of ~s.o.s~ has much to be proud of 
Solved Threads: 468
Super Moderator
Featured Poster
~s.o.s~'s Avatar
~s.o.s~ ~s.o.s~ is offline Offline
Failure as a human

Re: simplified bubble sort c++

 
0
  #3
Nov 21st, 2006
You cant as such check for such conditions in case of a simple sort like bubble sort.

Take for eg. this array.
1 2 3 4 5 6 8 7

During the first seven passes no swap is performed since the next number is always greater than the current but a final swap is done in the last pass to sort the array. You cant as such terminate a bubble sort based on the flag that swap is performed or not.
I don't accept change; I don't deserve to live.
Reply With Quote Quick reply to this message  
Join Date: May 2006
Posts: 3,114
Reputation: WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of 
Solved Threads: 281
Moderator
WaltP's Avatar
WaltP WaltP is offline Offline
Posting Sensei

Re: simplified bubble sort c++

 
0
  #4
Nov 22nd, 2006
Originally Posted by ~s.o.s~ View Post
You cant as such check for such conditions in case of a simple sort like bubble sort.

Take for eg. this array.
1 2 3 4 5 6 8 7

During the first seven passes no swap is performed since the next number is always greater than the current but a final swap is done in the last pass to sort the array. You cant as such terminate a bubble sort based on the flag that swap is performed or not.
Yes you can. You set the swap flag to FALSE between the two loops (inside the outer loop, before the inner loop). When the inner loop exits and a swap has been made, the swap flag should be TRUE. If no swap has been made, the flag should be FALSE and it's safe to exit.
The 3 Laws of the Procrastination Society:
1) Never do today that which can be put off until tomorrow
2) Tomorrow never comes
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC