Sortowanie bąbelkowe - optymalizacja

Question

Witam, stworzyłem taki program do sortowania bąbelkowego tablicy [n], gdzie n należy do przedziału (0,1 000 000 ). 

Niestety program w jednym przypadku jest za wolny. Czy da się go jakoś zoptymalizować?

Pozdrawiam,

FP

 

#include <iostream>

using namespace std;

void sortowanie(long long tab[],int n)
{
    for(long long i=0 ; i<n ; i++)
    {
        for(long long j=1 ; j<n-i ; j++)
        {
            if(tab[j-1]>tab[j]) swap(tab[j-1],tab[j]);
        }
    }
}

long long tab[1000010];
int main()
{
    long long n=0;

    std::ios_base::sync_with_stdio(false);
    ios_base::sync_with_stdio(0);

    while(cin>>tab[n]) n++;

    sortowanie(tab,n);

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

 

Answer 1

Możesz zrobić małe ulepszenie dla przypadku tablicy będącej w większości posortowanej. W takim przypadku zewnętrzna pętla zostaje przerwana ( C++17 ).

#include <iostream>
#include <vector>

using namespace std;

template< typename T >
void bubble_sort( T&& arr )
{
   for( auto iter_i { begin(arr) } ; iter_i != end(arr); ++iter_i )
   {
       bool swapped {false};
       for( auto iter_j { begin(arr) } ; iter_j < iter_i ; ++iter_j )
       {
           if( *iter_i < *iter_j )
           {
               swap( *iter_i , *iter_j );
               swapped = true;
           }
       }
       if( !swapped ) break;
   }
}

int main()
{
    int arr[] = {1,7,8,4,5,11,17,18};
    bubble_sort(arr);

    for( const auto& element : arr ) cout << element << " ";
}

 

Comments

i < size(arr)-1

Ciutkę ryzykowne (dla arr.size() == 0).