I've been doing c++ arrays and vectors in my book and I there is this exercice the asks you to write a bubble sort algorithm. I think I've figured out the algorithm but I need some help with the next exercise which modifies the bubble sort algorithm. Here it is:
1. After the first pass, the largest number is guaranteed to be in the highest-numbered element of the array;after the second pass, the two highest numbers" are in place and so on.Instead of making nine comparisons each pass modify the bubble sort to make eight comparisons on the the second pass, seven on the third etc.
2. The data in the array may already be in the proper order or near-proper order, so why make nine passses if fewer will suffice? Modify the sort to check at the end of each pass if any swaps have been made. If none have been made, then the data must already be in the proper order, so the program should terminate. If swaps have been made, then at least one more pass is needed.
Here is the code for the bubble sort so far:
#include <iostream> using std::cout; using std::endl;
int main() { const int arraySize=10; int bubble_sort[arraySize]={7,2,3,4,10,23,34,54,5,18}; int temp=0;
for (int x=0;x<11;x++) { for (int i=0;i<arraySize;i++) { temp=bubble_sort[i]; if (bubble_sort[i]>bubble_sort[i+1]) { bubble_sort[i]=bubble_sort[i+1]; bubble_sort[i+1]=temp; } } } for (int i=0;i<arraySize;i++) cout<<bubble_sort[i]<<endl;
}
On a side note, how do i work these html tags. I looked at the page on the site which tells you how to do it but i cant get them to work.
Well I guess I never asked a question, BUT I did say that I needed help on the exercise. To clarify, basically I have no idea what the exercise is trying to say or how to do it.
if you'll notice, the namespace line should take care of your I/O declarations. I threw in spacing to make it Much more ledgible. I renamed the last variable Just in case. I tried testing it, but I've apparantly forgotten how to use visual studio so all I can test is syntax.
1. The largest number will be at the end of what the algorithm assumes is the end of the array with each successful pass. After the first pass bubble_sort[9] wont need to be checked or swaped. after the second passs bubble_sort[8] wont need to be checked or swapped ect. Each pass needs to check a subset of the array one place smaller than the last.
for (int i=0; i<arraySize ;i++) This point and the end of each pass will be key.
2. you need to keep track of the number of swaps or more so if a swap was made in each pass.
that happens in here
if (bubble_sort[i]>bubble_sort[i+1]) {
bubble_sort[i]=bubble_sort[i+1];
bubble_sort[i+1]=temp;
}
if no swaps are made in a pass you dont need to continue. These exercise are pretty straight foreward and its hard to help without pretty much removing all the benifit of doing them.
I understand what you mean, however, it becomes a lot harder doing the exercises without an instructor to help. It might be because I am using what was designed to be a textbook and was not really targeted at individuals, but I couldn't find any other books at the library.