pranay_teja
1/16/2018 - 8:02 PM

Bubble Sort - Optimized

#include <bits/stdc++.h>
using namespace std;

//  #Sorting #Theory

void swap(int &x,int &y){
    int t=x;
    x=y;
    y=t;
}
void BubbleSort(vector<int> &a){    // passing vector by reference
    int n=a.size();
    for(int i=0;i<n;i++){	// to run swap loop for n times
        int swap_flag=0;
        for(int j=0;j<n-1-i;j++){	// x=0 to x=n-2-i
            if(a[j]>a[j+1]){        // larger elements move towards right    
                swap(a[j],a[j+1]);  // as last i elements are already sorted
                swap_flag=1;
            }
        }
        if(swap_flag==0){   // if no swap occured array already sorted, break out of loop
            break;
        }
    }
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> a(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        cout<<"Original: ";
        for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
        BubbleSort(a);
        cout<<"Sorted: ";
        for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
        
    }
    
    return 0;
}