//Sortowanie babelkowe
//www.algorytm.org

#include <iostream>
// Wymagane dla time() pod MSVC
#include <ctime>

// Funkcja zamienia wartosci obiektow a i b,
// identyczna implementacje mozna znalesc w <algorithm>
template<typename T> inline void swap(T& a, T& b)
{
    // c przechowuje tymczasowo wartosc obiektu a
    T c(a); a = b; b = c;
}

// Funkcja sortuje tablice wskazana przez array o rozmiarze size,
// ta implementacji nie jest optymalna dla posortowanych juz tablic, jej
// zlozonosc zawsze bedzie O(N^2), nie chcialem duplikowac implementacji
// zawartych w serwisie dlatego przedstawiam alternatywna metode.
template<typename T> void bubbleSort(T* array, size_t size)
{
    // Jezeli rozmiar tablicy rowny jest zero to zakoncz funkcje
    if (size == 0)
        return ;
    for (size_t i = 0; i < size - 1; ++i)
        for (size_t j = size - 1; j > i; --j)
            if (array[j - 1] > array[j])
                // Zamien wartosci elementow jezeli lewy wiekszy od prawego
                swap(array[j - 1], array[j]);         
}

// Funkcja wyswietla tablice wskazna przez array o rozmiarze size
template<typename T> void printArray(const T* array, size_t size)
{
    // Dla kazdego elementu tablicy
    for (size_t i = 0; i < size; ++i)
    {
        // Wyswietl element i, gdy indeks elementu + 1 dzieli sie 
        // bez reszty przez 10, wstaw znak nowego wiersza,
        // w przeciwnym wypadku wstaw znak tabulacji.
        std::cout << array[i] << ((i + 1) % 10 == 0 ? "\n" : "\t");
    }
    // Nowy wiersz
    std::cout << std::endl;
}

int main()
{
    // Stala wielkosc tablicy
    const int size = 100;
    // Tablica liczb calkowitych
    int int_array[size];
    
    // Inicjalizacja ziarna generatora liczb pseudo-losowych
    srand(time(0));
    
    // Losowa inicjalizacja tablicy
    for (size_t i = 0; i < size; ++i)
    {
        // Wartosc losowa z przedzialu od 0 do 99
        int_array[i] = rand() % 100;
    }    
    
    // Wyswietl tablice przed posortowaniem
    printArray(int_array, size);    
    // Posortuj tablice
    bubbleSort(int_array, size);
    // Wyswietl tablice po posortowaniu
    printArray(int_array, size);
    
    // Czekaj na "enter"
    std::cin.get();
    
    // Poprawne zakonczenie programu
    return EXIT_SUCCESS;
}