#include <iostream>

using namespace std;

struct auta
{
    string marka;
    int wiek;
};

wczytajDane (int n, auta *wsk)
{
    for (int i=0;i<n;i++)
    {
        cout << "Podaj marke auta " << i+1 << endl;
        cin >> wsk[i].marka;
        cout << "Podaj wiek auta " << i+1 << endl;
        cin >> wsk[i].wiek;
    }
}

wyswietl (int n, auta *wsk)
{
    for (int i=0;i<n;i++)
    {
        cout << wsk[i].marka <<"\t";
        cout << wsk[i].wiek << endl;
    }
    return 0;
}

void sortowanieBabelkowe(int n, auta *wsk)
{
    for(int i=0; i<n; i++ )
        {
            for(int j=0; j<n-1; j++ )
            {
                if( wsk[j].wiek>wsk[j+1].wiek)
                     swap(wsk[j].wiek, wsk[j+1].wiek);
            }
        }
}

void quickSort(int left, int right, auta *wsk)
{
    if (left < right)
    {
        int m = left;           // nr indeksu dla elem. osiowego
        for (int i = left + 1 ; i <= right ; i++)
            if (wsk[i].wiek < wsk[left].wiek)
            {
                swap(wsk[++m], wsk[i]);
            }
            swap(wsk[left], wsk[m]);

            quickSort(left, m - 1, wsk);
            quickSort(m + 1, right, wsk);
    }
}

void sortowanieWstawianie(int n, auta *wsk)
{
    int temp, j;
    for(int i=1;i<n; i++)
    {
        temp=wsk[i].wiek;
        for(j=i-1; j>=0&&wsk[j].wiek>temp; j--)
        {
            wsk[j+1].wiek=wsk[j].wiek;
        }
        wsk[j+1].wiek=temp;
    }
}

void sortowanieWybieranie(int n, auta *wsk)
{
    int max;
    for(int i=0; i<n; i++)
    {
        max = i;
        for(int j=i+1; j<n; j++)
        {
            if( wsk[j].wiek < wsk[max].wiek)
            {
                max = j;
                swap(wsk[max].wiek, wsk[i].wiek);
            }
        }
    }
}

void bisekcyjne(int n, auta *wsk)
{
    int l, p, x, s;
    cout<<"Podaj element do wyszukania"<<endl;
    cin>>x;
    //s-szukana
    l=0;
    p=n;
    while (l<=p)
    {
        s=(l + p)/2;
        if (wsk[s].wiek == x)
        {
            cout<<"Odnaleziono element "<<x<<" pod indeksem "<<s<<endl;
            return;
        }
        if (wsk[s].wiek < x)
        {
            l = s + 1;
        }
        else
        {
            p = s - 1;
        }
    }
    cout<<"Nie odnaleziono w wsklicy elementu "<<x<<endl;
}

int main ()
{
    int n;
    cout<<"Podaj liczbe aut"<<endl;
    cin>>n;
    auta samochod[n];
    auta *wsk;
    wsk =&samochod[0];

    wczytajDane (n,wsk);
    wyswietl (n,wsk);
    cout<<"sortowanieBabelkowe"<<endl;
    sortowanieBabelkowe(n,wsk);
    wyswietl (n,wsk);
    cout<<"quickSort"<<endl;
    quickSort(0, n-1, wsk);
    wyswietl (n,wsk);
    cout<<"sortowanieWstawianie"<<endl;
    sortowanieWstawianie(n,wsk);
    wyswietl (n,wsk);
    cout<<"sortowanieWybieranie"<<endl;
    sortowanieWybieranie(n,wsk);
    wyswietl (n,wsk);
    cout<<"bisekcyjne"<<endl;
    bisekcyjne(n, wsk);
    wyswietl (n,wsk);

}
/*
void wczytajTablice(int n, int *tab)
{
    for(int i=0;i<n;i++)
    {
          cout << "Podaj "<<i+1<<" liczbe: "<< endl;
          cin >> *tab;
          tab++;
    }
}

void wyswietlTablice(int n, int *tab)
{
    for (int i=0;i<n;i++)
    {
        cout<<*tab<<endl;
        tab++;
        //&a[i] to to samo co tab; tab++;
    }
}

int main()
{
    int n=0;
    cout << "Podaj ile liczb do tablicy chcesz wprowadzic" << endl;
    cin>>n;
    int a[n];
    int *tab;
    tab=&a[0];
    wczytajTablice(n,tab);
    wyswietlTablice(n,tab);

    return 0;
}
*/