CODEWITHSUNDEEP
c++algorithmbubble-sort
epikBhull
epikBhull

Reputation: 13

C++ Bubble Sort Algorithm

I have the following code written in c++ and the algorithm works when in this scenario. I am knew to c++ and don't understand what I did wrong in my 2nd test.

#include <iostream>

using namespace std;

void bubbleSort(int numbers[], int size) {
    for (int i = 0; i<size;i++) {
        for (int j=0; j<size;j++) {
            if (numbers[j] > numbers[j+1]) {
                swap(numbers[j], numbers[j+1]);
            }
        }
    }
}

int main() {
    int numbers[] = {7,5,6,4};
    bubbleSort(numbers,4);
    
    for (int print = 0; print < 4; print++) {
        cout << numbers[print] << endl;
    }
    
    
    return 0;
}

But, fails when I try to put in numbers that are already sorted:

#include <iostream>

using namespace std;

void bubbleSort(int numbers[], int size) {
    for (int i = 0; i<size;i++) {
        for (int j=0; j<size;j++) {
            if (numbers[j] > numbers[j+1]) {
                swap(numbers[j], numbers[j+1]);
            }
        }
    }
}



int main() {
    int numbers[] = {1,2,3};
    bubbleSort(numbers,3);
    
    for (int print = 0; print < 3; print++) {
        cout << numbers[print] << endl;
    }
    
    
    return 0;
}

Upvotes: 1

Views: 3841

Answers (4)

user21508463
user21508463

Reputation:

A quick look at the code reveals an anomaly:

    for (int j=0; j<size;j++) {
        if (numbers[j] > numbers[j+1]) {

Clearly, j can be as large as size-1, so that you access the non-existent slot numbers[size]. A smart run-time environment might warn you about an array overflow, but not all do.

Among size elements, you can only form size-1 pairs to be compared, so the correct code can be written

    for (int j=0; j+1<size;j++) {
        if (numbers[j] > numbers[j+1]) {

Optimization:

Notice that your code performs many unnecessary comparisons: after a complete pass over the array, as every largest element of a pair is sent to the right, the largest element reaches its final place. So in the following passes, there is no need to test the last pair, then the before last, and so on. Hence the condition

    for (int j=0; j+1<size-i;j++) {
        if (numbers[j] > numbers[j+1]) {

In fact, this minor change reduces the number of comparisons by about a factor 2.

But that is not all: it you keep a trace of the last swap that was performed during a pass, there is no need to test past this pair in the next passes, and this may further shorten these passes. Even better, if a pass ends with no swap at all, you are done !

Upvotes: 0

alok singh
alok singh

Reputation: 1

//i will make this program understandable for you, lets go.....

#include<iostream>
using namespace std;
// create the function that will print the array after the array is sorted
void printarray(int* data,int n)
{
    for ( int i=0; i<n;++i){
        cout <<data[i]<<" ";
    }
}
//this function has parameters that will accept the array data and the number 
//no. of elements in the array.
void bubblesort(int* data, int n){
    for ( int i=0; i<n; ++i){
        for ( int i=0; i<n-1; ++i){
            if ( data[i]>data[i+1]){
//these statements are for swapping the element.
                int temp=data[i];
                data[i]=data[i+1];
                data[i+1]=temp;
            }
        }
    }
}
int main()
{
    int data[]={ 12, 45,23, 78, 87, 2, 65, 90, 12, 34};
// 'n' here find the no. of elements is the array.
    int n=sizeof(data)/sizeof(data[0]);
//recall the functions in sequence..........
    bubblesort(data,n);
    printarray(data,n);

}

Upvotes: 0

user14221102
user14221102

Reputation:

Implementing bubble sort in its entirety is problematic. In the example code, the inner loop repeatedly iterates over the full array while disregarding the shift by 1. The inner loop iterates over the whole array in a traditional bubble sort's first iteration of the outer loop, "bubbling" the smallest/largest value to the array's end. On the subsequent iteration, the inner loop only has to iterate up to the array's second-smallest/largest point rather than the full array. The inner loop then iterates through a smaller and smaller subset of the array, making bubbles of the associated the associated value to the proper stop with each successive run in the outside loop.

Upvotes: 0

Sam Varshavchik
Sam Varshavchik

Reputation: 118330

for (int j=0; j<size;j++) {

If size is 3, if the array has three values, for example, this loop iterates with values of j of 0, 1, and 2.

if (numbers[j] > numbers[j+1]) {

When j is 2 this compares numbers[2] with numbers[3].

There is no numbers[3]. This is undefined behavior. The loop is off by 1 value.

Additionally, the overall bubble sort implementation is flawed. In the shown code the inner loop iterates over the entire array (ignoring the off-by-1 bug), every time. In a classical bubble sort the first pass (the first iteration of the outer loop) results in the inner loop iterating over the entire array and "bubbling" the smallest/largest value to the end of the array. On the next pass the inner loop does not need to iterate over the entire array, but only up until the 2nd smallest/largest position of the array. And so on, each pass (the outer loop) results in the inner loop iterating over a smaller, and smaller subset of the array, "bubbling" the corresponding value to the appropriate stop.

In addition to fixing the off-by-1 bug you'll also need to adjust the overall logic of this bubble sort, if you wish to get a perfect grade for your homework assignment.

Upvotes: 2

Related Questions