CODEWITHSUNDEEP
c++bubble-sort
user9929640
user9929640

Reputation:

Need Help as to how I am getting a different Output

I am trying to implement the Bubble Sort Algorithm in C++ but I am not getting the desired output which I require, so I need help regarding that. 

#include <iostream>
using namespace std; 

void BubbleSort(int arr[] , int n)
{
    for(int i=0 ; i<n-1 ; i++) // Iterating for (n-1) Rounds 
    {
        for(int j=0 ; j<n ; j++)
        {
            if(arr[j]>arr[j+1])
            {
                int temp ; 
                temp=arr[j]; 
                arr[j]=arr[j+1];
                arr[j+1]=temp ; 
            }
        }
    }
}

int main()
{
    int n,arr[50] ; 
    cin >> n ; 

    for(int i=0 ; i<n ; i++)
    {
        cin >> arr[i]; 
    }

    BubbleSort(arr,n);

    for(int i=0 ; i<n ; i++)
    {
        cout << arr[i] << " " ; 
    }
}

Sample Test Case (with Size 7): 2 13 4 1 3 6 28
Expected Output: 1 2 3 4 6 13 28
Actual Output (that I am getting): 1 0 2 3 4 6 13

Upvotes: 0

Views: 53

Answers (2)

j23
j23

Reputation: 3530

Change the inner loop to for(int j=0 ; j<n-i-1 ; j++). Every time an inner loop gets completely executed, an element will be in correct position. That means, inner loop should executes n-i-1 times.

#include<iostream>
using namespace std ; 

void BubbleSort(int arr[] , int n)
{

    for(int i=0 ; i<n-1 ; i++) // Iterating for (n-1) Rounds 
{

    for(int j=0 ; j<n-i-1 ; j++)
    {
        if(arr[j]>arr[j+1])
        {
            int temp ; 
            temp=arr[j]; 
            arr[j]=arr[j+1];
            arr[j+1]=temp ; 
        }

    }
}

}

int main(){
    int n,arr[50] ; 
    cin >> n ; 

    for(int i=0 ; i<n ; i++)
    {
        cin >> arr[i]; 
    }

    BubbleSort(arr,n);

    for(int i=0 ; i<n ; i++)
    {
        cout << arr[i] << " " ; 
    }
}

In bubble sort, one complete execution of the inner loop will put the largest element of the array into the bottom of the array. After the first execution of the inner loop, the largest element will be in the nth position or last position. So during the second execution, inner loop should parse only n-1 elements and copies the second largest element to n-1 th position or second last position. Similarly, it goes for n-2,n-3 ... till the first element i.e n-i. Hence j<n-i-1

To put it simply, it sorts from the bottom to top (upward direction) like the bubbles.

Upvotes: 0

Vlad from Moscow
Vlad from Moscow

Reputation: 310960

In this loop

for(int j=0 ; j<n ; j++)
{
    if(arr[j]>arr[j+1])
    {
        int temp ; 
        temp=arr[j]; 
        arr[j]=arr[j+1];
        arr[j+1]=temp ; 
    }

}

there is an attempt to access memory beyond the array when j is equal to n - 1 because in this case j + 1 gives n and the array does not have an element at the index equal to n. So this expression arr[j+1] in this case is invalid.

Upvotes: 1

Related Questions