CODEWITHSUNDEEP
c++bubble-sort
Normal People Scare Me
Normal People Scare Me

Reputation: 841

Bubble Sort Optimization C++

I was just practising a little bit and tried to sort an array with the bubble sort algorithm. Compiler didn't give me any warnings nor errors and it worked well! First you type 10 times a number and then the program sorts them + prints them.

Code: 

#include <iostream>
using namespace std;

void arr_sort(int* array, const int arr_size){

int temp = 0;   //Temporary integer to store (if necessary) the current element
int end = 0;    //Run time condition

while(end++ != arr_size){ // Will loop max. 10 times

    for(int i = 0; i < arr_size; i++){

        if(array[i] > array[i + 1]){    //If the current element 
            temp = array[i];    //is bigger than the next

            array[i] = array[i + 1];//Change the positions
            array[i + 1] = temp;    
        }
    }
}

}

int main(){

int arr_input[10];

for(int i = 0; i < 10;i++)      //The user has to type 10 numbers
    cin >> arr_input[i];        //which will be stored in this array

arr_sort(arr_input, 10);        //sorts the array

cout << endl << endl;

for(int i = 0; i < 10; i++)     //Print out the array!
    cout << arr_input[i] << ", ";
cout << endl;

return 0;
}

My only problem is the while-loop in the arr_sort function. I mean it sorts the array until end has the same value as arr_size. But often it doesn't need that long. My question now... How can I improve this function? How can I test if the array is completely sorted so the while-loop can stop without running another time and another time ...?

Upvotes: 2

Views: 8451

Answers (2)

Drew Dormann
Drew Dormann

Reputation: 63775

Before your for loop, assume it's sorted:

bool sorted = true;

In your if statement`, record that it's not sorted:

sorted = false;

After your for loop`, return if there was no evidence that it's not sorted:

if ( sorted ) return;

Upvotes: 6

jonhopkins
jonhopkins

Reputation: 3842

Just outside of the for loop, place a bool and set it to false. Inside the swap block, set the bool to true. After the for loop, check the value of the boolean, and if it's still false, no swaps were made so the array is sorted, so break out of the while loop.

while(end++ != arr_size){ // Will loop max. 10 times

    bool swapped = false;
    for(int i = 0; i < arr_size; i++){

        if(array[i] > array[i + 1]){    //If the current element 
            temp = array[i];    //is bigger than the next

            array[i] = array[i + 1];//Change the positions
            array[i + 1] = temp;
            swapped = true;    
        }
    }
    if (!swapped) break;
}

Upvotes: 3

Related Questions