Question

C++ SORTOWANIE - sortowanie szybkie

Podaj klasy złożoności obliczeniowej dla algorytmu bąbelkowego (BUUBLE SORT) i szybkiego (QUICK SORT).

Czy występuje sortowanie w miejscu algorytmu bąbelkowego (BUUBLE SORT) i szybkiego (QUICK SORT).

W algorytmie sortowania szybkiego dzielimy zbiór danych na części zwane partycjami i dlatego ze zbioru musimy wybrać jeden z elementów, który nazwiemy wskaźnikiem. Jako wskaźnik można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy.

Zmień w algorytmie:
1. Wprowadzanie danych ma następować z klawiatury a nie jako generator liczb losowych.
2. Wprowadzanie danych ma być wywoływane jako funkcja WPROWADZ.

3. Wybrany element środkowy (piwot) zmień na: element pierwszy lub ostatni lub medianę lub element losowy.
// Sortowanie Szybkie
#include
#include
#include
#include
using namespace std;
const int N = 20; // Liczebność zbioru.
int d[N];
// Procedura sortowania szybkiego
//-------------------------------
void Sortuj_szybko(int lewy, int prawy)
{
int i,j,piwot;
i = (lewy + prawy) / 2;
piwot = d[i]; d[i] = d[prawy];
for(j = i = lewy; i < prawy; i++)
if(d[i] < piwot)
{
swap(d[i], d[j]);
j++;
}
d[prawy] = d[j]; d[j] = piwot;
if(lewy < j - 1) Sortuj_szybko(lewy, j - 1);
if(j + 1 < prawy) Sortuj_szybko(j + 1, prawy);
}
// Program główny
//---------------
int main()
{
Imię i nazwisko Data
int i;
srand((unsigned)time(NULL));
cout << " Sortowanie szybkie\n"
"------------------------\n"
" (C)2005 PK \n\n"
"Przed sortowaniem:\n\n";
// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość
for(i = 0; i < N; i++) d[i] = rand() % 100;
for(i = 0; i < N; i++) cout << setw(4) << d[i];
cout << endl;
// Sortujemy
Sortuj_szybko(0,N - 1);
// Wyświetlamy wynik sortowania
cout << "Po sortowaniu:\n\n";
for(i = 0; i < N; i++) cout << setw(4) << d[i];
cout << endl;
return 0;
}