C++

Forum

 
Help with Bubble Sort program

Dizzzeh (2)
Hey all. I'm new to C++, and learning about arrays. I've built a program that takes 10 numbers input from a user, and does a bubble sort to arrange them from smallest to largest. Or, well, it's supposed to.

The code blow only seems to sort the last two numbers. I can't figure out what I'm doing wrong here. I've tried to modify the code - changing the flag, changing the condition of the IF statement in the "sorting section", but nothing sticks.

I've browsed the Tutorials section of this site and others, but I just can't wrap my head around what might be wrong. Can anyone offer any hints or suggestions?

(Apologies for the code structure. The instructor has us using Visual Studio, and requests that we use 'void main()' to start off the program and 'getchar()' to pause the program, waiting foruser input.)

Cheers!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
#include <iostream>
using namespace std;

void main ()
{
int value [10], index, flag, dummy;

// Input Section:
// For Loop will input the numbers that the user enters into the "index" array
for (index = 0; index < 10; index++)
{
	cout << "Please enter # " << index + 1 << ": "; // "index +1" will output the index at increasing integers
	cin >> value [index]; // will put 10 numbers into the index array, in locations 0-9
}

// Sorting Section:
// Need to sort numbers in the array from small to big 

flag=1;

while (flag == 1) // while the variable 'flag' is equal to the number 1
{
	flag=0; // set the flag to 0 so that it will check to see if the values are in order.
	for (index=0; index < 9; index++); 
	{
		if (value[index-1] > value[index])
		{
			dummy = value[index-1];
			value[index-1] = value[index];
			value[index]=dummy;
			flag=1; // raise the flag to show that the program still needs to run through the loop and sort the values in the array
		}
	}
}

// Output section:
// includes the same For Loop as the Input Section, with a few modifications
for (index = 0; index < 10; index++)
{
	cout << "Value " << index + 1 << " is: " << value[index] << endl; // will output the users numbers in order, as we've sorted them from small to big
}

getchar();
getchar();

}
mobotus (275)
You sort is incorrectly formatted. Here is what you need.

http://www.cprogramming.com/tutorial/computersciencetheory/sorting1.html
PCrumley48 (173)
Take a close look:

1
2
3
4
5
6
7
8
9
 
for (index=0; index < 9; index++); // will this code execute when index == 9?	{
		if (value[index-1] > value[index])  //when index == 0, [index-1] == ??
		{
			dummy = value[index-1];  which value
			value[index-1] = value[index];//when index == 0, [index-1] == ??
			value[index]=dummy;
			flag=1; // raise the flag to show that the program still needs to run through the loop and sort the values in the array
		}
	}


To summarize:

You're trying to bubble sort the array from value[-1] through value[8].

Shouldn't take much to fix it.
Last edited on
anup30 (968)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
#include <iostream>
using namespace std;

int main () /// why void??
{
int value [10] = {9,1,0,2,3,4,5,6,8,7};

int flag=0;

while (flag < 10)
{
	for (int index=1; index < 10; index++) /// ';' in your code !!!
	{
		if (value[index-1] > value[index])
		{
			int temp = value[index-1];
			value[index-1] = value[index];
			value[index]= temp;			
		}		
	}
	flag++;
}


for (int i =0; i<10; i++)
	cout << value[i] << " ";
cout << endl;

return 0;
}

output:
0 1 2 3 4 5 6 7 8 9
PCrumley48 (173)
doing others' homework for them, anup??? "Help," not "do," I think, is the standard here.

good find in line 12; I never ran the code.

And OP specifically said
The instructor has us using Visual Studio, and requests that we use 'void main()' to start off the program


Besides, counting flag as an increasing value, while it guarantees a sort, is less than optimal for a bubble sort. What if the jnput order was:

1,2,3,4,5,6,7,8,10,9?

first pass, with a flag not set when 10/9 are switched means one pass through the array. Minimal issue with ten items, could be extreme with thousands.
Last edited on
Dizzzeh (2)
Thanks for the help, folks. Have it all sorted, now.

mobotus: Thanks for the link. For whatever reason, arrays always put me up short.

anup30: Nice catch with the ";" on line 12. Neither I, nor my compiler spotted that!

PCrumley48 : I see what you mean with sorting the wrong values in the array. Once I ran through it step by step on paper, the code made more sense and I realised that I had the conditions in my if statement back to front.

Again, thanks for all of the help. This forum and website are an amazing resource for beginners.
anup30 (968)
(Apologies for the code structure. The instructor has us using Visual Studio, and requests that we use
'void main()' to start off the program...

its a bad instruction to use void main() in C++.

when i saw the structure, at first glance i thought its complete wrong method. but, its similar to conventional double for loops, as shown in mobotus's link. (homework is already done there.)

for normal cases i use selection sort. in my test its 2 to 3 times faster than bubble sort.

as i have done the complete home work for the OP, i am giving him addition homework, :) ask the user how many number he want to input. and ask him in which format (ascending/descending) he want to sort.

i recently programed a quick sort (idea from Wikipedia). you will be surprised to know how many times its faster than selection sort! (for 10 million random values)
anup30 (968)
PCrumley48 wrote:
...while it guarantees a sort, is less than optimal for a bubble sort. What if the jnput order was:

1,2,3,4,5,6,7,8,10,9?

i dont think so.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
int flag=0;
while (flag < size)
{
	for (int index=1; index < size; index++)
	{
		if (value[index-1] > value[index])
		{
			int temp = value[index-1];
			value[index-1] = value[index];
			value[index]= temp;			
		}		
	}
	flag++;
}


is the same as
1
2
3
4
5
6
7
8
9
10
 
for( int i = 0; i < size; i++ )
{		
for(int j=0; j<size; j++)
if(ar[j] < ar[i])		
	{
		int temp = ar[i];
		ar[i] = ar[j];
		ar[j] = temp;
	}				
}
PCrumley48 (173)
not the same at all:

In a bubble sort you only swap a member with its neighbor in your chosen direction. Your example swaps element j with element i whatever their positions are in the array and requires size^2 comparisons for every sort, including a comparison every time i == j (when i==3 and j==3, for example, ar[3] < ar[3] is pointless).

Optimizing a bubble sort can reduce the number of comparisons to as low as size by doing this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
bool swapped = true;
while (swapped)
{
	swapped = false;
	for (int i = 0; i < size-1; i++)
	{
		if (ar[i] > ar[i+1])
		{
			swap (ar[i],ar[i+1]);
			if (i < size-1)
				swapped = true;
		}
	}
}

[/code]

This will always reduce the number of iterations , except when the array values are completely reversed. If the array values are entered in order there will only be one pass through the array. You can also optimize this more by keeping track of where the last swap happened, and reduce the iterating value to that point, so that if the last swap happens between items size - 1 and size, the next iteration can be limited to size-2 and so on.

Bubble sorts are not the optimal sorts for most uses anyway, of course, but they are quick to implement on a small number of values.
anup30 (968)
they don't work exactly same process, as you can see, i meant 'similar' version of bubble sort.

bubble sort is the first sorting algorithm beginners learn (or some version of it - what come to their mind if they try themselves). soon they learn selection sort. optimizing bubble sort is cant make it faster than selection sort.

your last method (Optimized bubble sort?) is the slowest of the last three codes!
PCrumley48 (173)
sorting basic bubble, counter/flag,flagged bubble, indexed bubble, same array of [1000] different int:

Basic Bubble Sort: Comparisons: 1000000, Swaps: 261025 - your last one
Flag Counter Sort:    Comparisons: 999000, Swaps: 238477 - your first one
Flagged Bubble Sort: Comparisons: 938061, Swaps: 238477 - my only one till now
Indexed Bubble Sort: Comparisons: 496814, Swaps: 238477 - latest version


See for yourself:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
#include  <iostream>
#include <time.h>
#include <stdlib.h>  

void basicbubble(int* arr,int size);
void flagcounterbubble(int* arr,int size);
void flagbreakbubble(int * arr, int size);
void indexbubble(int* arr, int size);

int main()
{
	int testarray[1000],basearray[1000];
	for (int i = 0; i < 1000; i++) basearray[i] = i;
	srand(time(NULL));
	for (int i = 0; i < 1000; i++) std::swap(basearray[i],basearray[rand() % 1000]);
	for (int j = 0; j < 4; j++)
	{
		for (int i = 0; i < 1000; i++) testarray[i] = basearray[i];
		switch(j)
		{
		case 0:
			basicbubble(testarray,1000);
			break;
		case 1:
			flagcounterbubble(testarray,1000);
			break;
		case 2:
			flagbreakbubble(testarray,1000);
			break;
		case 3:;
			indexbubble(testarray,1000);
			break;
		}
	}
}

void basicbubble(int* arr,int size)
{
	int comparisons(0),swaps(0);
	for( int i = 0; i < size; i++ )
	{
		for(int j=0; j<size; j++)
		{
			comparisons++;
			if(arr[j] < arr[i])
			{
				std::swap(arr[j],arr[i]);
				swaps++;
			}
		}
	}
	std::cout << "Basic Bubble Sort: Comparisons: " << comparisons << ", Swaps: " << swaps << std::endl;
	system("Pause");
}

void flagcounterbubble(int* arr,int size)
{
	int flag=0,comparisons(0),swaps(0);
	while (flag < size)
	{
		for (int index=1; index < size; index++)
		{
			comparisons++;
			if (arr[index-1] > arr[index])
			{
				std::swap(arr[index-1],arr[index]);
				swaps++;
			}
		}
		flag++;
	}
	std::cout << "Flagged Bubble Sort: Comparisons: " << comparisons << ", Swaps: " << swaps << std::endl;
	system("Pause");
}

void flagbreakbubble(int * arr, int size)
{
	int comparisons(0),swaps(0);
	bool swapped = true;
	while (swapped)
	{
		swapped = false;
		for (int i = 0; i < size-1;i++)
		{
			comparisons++;
			if (arr[i+1] < arr[i])
			{
				std::swap(arr[i],arr[i+1]);
				swaps++;
				swapped = true;
			}
		}
	}
	std::cout << "Indexed Bubble Sort: Comparisons: " << comparisons << ", Swaps: " << swaps << std::endl;
	system("Pause");
	
}

void indexbubble(int* arr, int size)
{
	int comparisons(0),swaps(0),swapindex(size),index(size);
	bool swapped = true;
	while (swapped)
	{
		swapped = false;
		swapindex = index;
		for (int i = 0; i < swapindex-1;i++)
		{
			comparisons++;
			if (arr[i+1] < arr[i])
			{
				std::swap(arr[i],arr[i+1]);
				swaps++;
				swapped = true;
				index = i+1;
			}
		}
	}
	std::cout << "Indexed Bubble Sort: Comparisons: " << comparisons << ", Swaps: " << swaps << std::endl;
	system("Pause");

So my two horses outrun yours by quite a bit in the comparison department, particularly the second one you haven't seen yet.
anup30 (968)
PCrumley48 wrote:
my two horses...
LOL
let me clarify, they aren't my horses. flagcounterbubble() function is actually OP's method(corrected). in your comparison you didn't included sorting time(!) which is more important. all your efforts to improve bubble sort would seem fruitless - if you see the time. see the code in http://cpp.sh/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
//bubbleSorting 4 variations and selectionSort Comparson //with time
#include <iostream>
#include <ctime>
#include <cstdlib>  

void basicBubble(int* arr,int size);
void OPs(int* arr,int size);
void flagBreakBubble(int * arr, int size);
void indexBubble(int* arr, int size);
void selectionSort (int ar[], int size);
using namespace std;
int main()
{
	srand(time(NULL));
	int size = 12000; ////////////// size ///
	cout << "elements = " << size << "\n\n";
	int *ar1= new int[size];
	int *ar2= new int[size];
	int *ar3= new int[size];
	int *ar4= new int[size];
	int *ar5= new int[size];

	clock_t t0, t1, t2, t3, t4, t5, t6;
	t0 = clock();

	for (int i = 0, n; i < size; i++)
	{
		n = rand()% 25000;
		ar1[i] = n;
		ar2[i] = n;
		ar3[i] = n;
		ar4[i] = n;
		ar5[i] = n;
	}
	t1 = clock();

 basicBubble(ar1, size);   
	t2 = clock();
 OPs(ar2, size);   
	t3 = clock();
 flagBreakBubble(ar3, size);  
	t4 = clock();
 indexBubble(ar4, size);
	t5 = clock();
 selectionSort(ar5, size);
 	t6 = clock();	

 cout << "\nTime Test:\n"
	<< "settingTime     " << double(t1-t0) / CLOCKS_PER_SEC << " sec\n"
	<< "basicBubble     " << double(t2-t1) / CLOCKS_PER_SEC << " sec\n" 
	<< "OPs             " << double(t3-t2) / CLOCKS_PER_SEC << " sec\n"
	<< "flagBreakBubble " << double(t4-t3) / CLOCKS_PER_SEC << " sec\n"
	<< "indexBubble     " << double(t5-t4) / CLOCKS_PER_SEC << " sec\n"
	<< "selectionSort   " << double(t6-t5) / CLOCKS_PER_SEC << " sec\n";

 delete[] ar1;
 delete[] ar2;
 delete[] ar3;
 delete[] ar4;
 delete[] ar5;

return 0;
}

void basicBubble(int* arr,int size)  //conventional
{
	int comparisons(0),swaps(0);
	for( int i = 0; i < size; i++ )
	{
		for(int j=0; j<size; j++) ///if j<size-1; comparison= comparison-size;
		{
			comparisons++;
			if(arr[j] < arr[i])
			{
				std::swap(arr[j],arr[i]);
				swaps++;
			}
		}
	}
cout << "basicBubble: Comparisons: " << comparisons << ", Swaps: " << swaps << "\n";
return;
}

void OPs(int* arr,int size) //as OPs
{
	int flag=0,comparisons(0),swaps(0);
	while (flag < size)
	{
		for (int i=1; i < size; i++)
		{
			comparisons++;
			if (arr[i-1] > arr[i])
			{
				std::swap(arr[i-1],arr[i]);
				swaps++;
			}
		}
		flag++;
	}
cout << "OPs: Comparisons: " << comparisons << ", Swaps: " << swaps << "\n";
return;
}

void flagBreakBubble(int * arr, int size) //PCrumley48 (1)
{
	int comparisons(0),swaps(0);
	bool swapped = true;
	while (swapped)
	{
		swapped = false;
		for (int i = 0; i < size-1;i++)
		{
			comparisons++;
			if (arr[i+1] < arr[i])
			{
				std::swap(arr[i],arr[i+1]);
				swaps++;
				swapped = true;
			}
		}
	}
cout << "flagbreakbubble: Comparisons: " << comparisons << ", Swaps: " << swaps << "\n";
return;	
}

void indexBubble(int* arr, int size) //PCrumley48 (2)
{
	int comparisons(0),swaps(0),swapindex(size),index(size);
	bool swapped = true;
	while (swapped)
	{
		swapped = false;
		swapindex = index;
		for (int i = 0; i < swapindex-1;i++)
		{
			comparisons++;
			if (arr[i+1] < arr[i])
			{
				std::swap(arr[i],arr[i+1]);
				swaps++;
				swapped = true;
				index = i+1;
			}
		}
	}
cout << "indexBubble: Comparisons: " << comparisons << ", Swaps: " << swaps << "\n";
return;
}

void selectionSort (int ar[], int size) /// selectionSort()
{ 
	int comparisons= 0, swaps= 0;
	for ( int i = 0; i < size; i++ )
	{		
		int indexPos = i;
		for(int j=i+1; j<size; j++)
		{
			comparisons++;
			if (ar[j] < ar[indexPos])			
				indexPos = j;			
		}
		
		if(ar[indexPos] != ar[i])
			{
				swaps++;
				std::swap(ar[indexPos] , ar[i]);
			}

	}
cout << "selectionSort: Comparisons: " << comparisons << ", Swaps: " << swaps << "\n";
return;	
}

selectionSort() is my secondary horse - while i wont reveal my primary horse ;)
PCrumley48 (173)
wrong again - the flag-as-counter version is yours. His int flag only switches states between 0 in line 23 and 1 in line 31 (if a swap has occurred), just like the boolean flag in option three. The only thing wrong with his sort was starting at element [0] and comparing to element [-1], and apart from that, it would have worked just fine.

With only 1000 elements in the array, the time() came back identical for all four versions on my system. But oddly enough, when I use your array setup using completely random numbers and timing in main() (very nice, by the way), the basic sort shows far fewer swaps and better time, If I revert back to my array setup using shuffled distinct values, the number of basic version swaps and time goes way up. I'm thinking that my shuffled setup is a special case - and duplicate neighbors in a random setup would decrease swap numbers, obviously. With an array already in order, the basic version still swaps elements and fails badly in timing, whereas if the elements are in perfect reverse order it goes at warp speed. . .So the difference in timing depends a lot on original parameters. Apples don't always equal oranges, after all!


I know we are talking about draft horses here -and there is no doubt most other sorts are thoroughbreds, but draft horses can be useful too. So if I need to build some kind of sort, for a limited number of items, bubble is quick, clean and easy to code. Mostly, though, I don't bother writing sort routines since there are so many others out there who have already done the work. The purpose of writing and evaluating any sort nowadays is for the learning of what goes on behind the dashboard.
Last edited on
PCrumley48 (173)
Thinking about horses -- A better comparison would be kiddie ride ponies vs thoroughbreds, probably!
PCrumley48 (173)
Nice work.

However - if course requirement is to write and use a bubble sort it doesn't leave much choice, right? Baby steps. . .
Last edited on
anup30 (968)
in my system (3Ghz x64 core2duo)

bubble sort: 16000 randoms in 1.279 sec >>> kiddie ride
selection sort: 27000 randoms in 1.294 sec >>> normal horse
quick sort: 3.0 million randoms in 1.2 sec >>> space shuttle

and notice relation between number increment vs time increment.
such as for bubble sort:
10,000 randoms 0.5 sec
20,000 randoms 2 sec
40,000 randoms 8 sec

for twice the size, time required 4 times more.

but in quick sort for twice size, required time is lower than 3 times.
3 million in 1.2 sec
6 million in 3.12 sec
12 million in 8.986 sec
Topic archived. No new replies allowed.