December 24th, 2016, 07:02 AM

Bubble sort not working
Hey guys,
I'm attempting to implement bubble sort in C++ with the following code:
Code:
int main() {
int numbers[10] = {3, 4, 1, 7, 1, 8, 101, 89, 10, 47};
// print array
cout << "numbers array before bubble sort:" << endl;
for (int i = 0; i < 10; i++) {
cout << numbers[i] << " ";
}
cout << endl;
int total_passes = 0;
for (int i = 0; i < 9; i++) {
for (int j = i + 1; j < 10  i; j++) {
total_passes++;
if (numbers[i] > numbers[j]) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
}
// print array
cout << "numbers array after bubble sort:" << endl;
for (int i = 0; i < 10; i++) {
cout << numbers[i] << " ";
}
cout << endl;
// report total passes
cout << "Total passes = " << total_passes << endl;
return 0;
}
The inner loop is supposed to be reduced by one each time (i.e. the first time round it loops 9 times, the second time it loops 8 times etc.) because after the first inner loop the last item in the array is the largest number, after the second time round the inner loop the largest two numbers are the last two items in the array etc.
I'm getting the following output:
Code:
numbers array before bubble sort:
3 4 1 7 1 8 101 89 10 47
numbers array after bubble sort:
1 1 3 4 7 8 101 89 10 47
Total passes = 25
Any idea where I'm going wrong?
Cheers!
Miktor
December 24th, 2016, 08:24 AM

All bubble sorts are currently failing because of the pico black hole swarm earth is encountering. Gravity at the cpu level is currently indeterminate. Run your program again in spring, when astronomers say earth shall be out of this mess. https://www.youtube.com/watch?v=1XM0x_qSeOk
Despite this desperate circumstance, we'll do what we can.
1) Abhor duplicate code. I've inserted a display function (candidate for a template, and to use vectors). Write the code just once.
2) fix the bubble sort. Never use bubble sort. It's better, I'll admit than the doubly random swap sort of which I forget the name, and the performance of bubble sort on a presorted list is also tops.
(your bubble sort implementation does not have optimal performance for presorted list)
[edit]Now looking at following program I discover that it is a program that sorts, however it is not bubble sort.[/edit]
Code:
#include<iostream>
const int N = 10;
void display(const char*title, int*v, const int n) {
std::cout << title << std::endl;
for (int i = 0; i < n; i++) {
std::cout << v[i] << " ";
}
std::cout << std::endl;
}
int main() {
int numbers[N] = {3, 4, 1, 7, 1, 8, 101, 89, 10, 47};
int total_passes = 0;
display("numbers array before bubble sort:", numbers, N);
for (int i = 0; i < (N1); i++) {
for (int j = i + 1; j < N; j++) { // changed the upper limit on this line
total_passes++;
if (numbers[i] > numbers[j]) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
}
display("numbers array after bubble sort:", numbers, N);
// report total passes
std::cout << "Total passes = " << total_passes << std::endl;
return 0;
}
Last edited by b49P23TIvg; December 24th, 2016 at 08:31 AM.
[code]
Code tags[/code] are essential for python code and Makefiles!
December 24th, 2016, 09:07 AM

Hence,
Code:
#include<iostream>
const int N = 10;
void display(const char*title, int*v, const int n) {
std::cout << title << std::endl;
for (int i = 0; i < n; i++)
std::cout << v[i] << " ";
std::cout << std::endl;
}
int bubble_sort(int*v, const int n) {
// rewritten as bubble sort. bubble sort
// compares immediate neighbors only.
// returns the number of comparisons.
int temp;
int i, j, comparisons = 0, swaps = 1;
for (i = n1; swaps && i; i, comparisons += j)
for (swaps = j = 0; j < i; ++j)
if (v[j+1] < v[j])
temp = v[j+1], v[j+1] = v[j], v[j] = temp, ++swaps;
return comparisons;
}
int main() {
int numbers[N] = {3, 4, 1, 7, 1, 8, 101, 89, 10, 47};
int total_passes;
display("numbers array before bubble sort:", numbers, N);
total_passes = bubble_sort(numbers, N);
display("numbers array after bubble sort:", numbers, N);
std::cout << "Total comparisons = " << total_passes << std::endl;
return 0;
}
If in doubt, check Sorting algorithms/Bubble sort  Rosetta Code
[code]
Code tags[/code] are essential for python code and Makefiles!
December 24th, 2016, 09:11 AM

And finally, to answer your question, yes, I have an idea of where you've gone wrong.
[code]
Code tags[/code] are essential for python code and Makefiles!
December 24th, 2016, 09:42 AM

This is speed comparison of different sorting algorithms, if it helps:
December 24th, 2016, 11:32 AM

@b49P23TIvg
Thanks for all the help. I know bubble sort isn't the optimum sorting algorithm; I was trying to do one of the exercises in "C++: How To Program" at the end of the arrays and vectors chapter. :D Working my way through the book at the moment to learn C++. Also purchased C++ Primer for another viewpoint/to reinforce what I'm learning from the first book.
I expect I may be on here a bit looking for help every few days(!)
@ivanvodisek
Neat gif! Just saved it to my desktop there.
Miktor
April 19th, 2017, 09:11 AM

Hey try this code:
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Learn C++ here https://hackr.io/tutorials/learnccplusplus
Code:
// C program for implementation of Bubble sort
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n1; i++)
// Last i elements are already in place
for (j = 0; j < ni1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
/* Function to print an array */
void printArray(int arr[], int size)
{
for (int i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}