quick sort z losowym piwotem(elementem dzielącym)

Odpowiedz Nowy wątek
2015-01-13 12:11
0

Witam mam takie zadanie na zaliczenie. Jestem dopiero początkujący więc prosiłbym o wyrozumiałość :) Napisałem Quick sorta oczywiście z pomocami różnymi ale dzieli on tablice na dwie części a wykładowca chce abym ten element dzielący wylosował i nie mam pojęcia jak to wstawić bo ciągle błędy wyskakują różne i się trochę już gubię. Wiem że muszę wykorzystać Srand (time = NULL ) ale nie mam już pojęcia jak to wstawić czy muszę już przerobić całą funkcję czy jak?
O to mój kod:

#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

int partition(int tablica[], int pierwsza_cz, int druga_cz) // dzielimy tablice na dwie czesci, w pierwszej wszystkie liczby sa
                                                               // mniejsze badz rowne x, w drugiej wieksze lub rowne od x
{
int x = tablica[pierwsza_cz]; // obieramy x
int i = pierwsza_cz, j = druga_cz, w;
while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j
{
while (tablica[j] > x) // dopoki elementy sa wieksze od x
j--;
while (tablica[i] < x) // dopoki elementy sa mniejsze od x
i++;
if (i < j) // zamieniamy miejscami gdy i < j
{
w = tablica[i];
tablica[i] = tablica[j];
tablica[j] = w;
i++;
j--;
}
else // gdy i >= j zwracamy j jako punkt podzialu tablicy
return j;
}
}

void quicksort(int tablica[], int pierwsza_cz, int druga_cz) // sortowanie szybkie
{
int punkt_podzialu;
if (pierwsza_cz < druga_cz)
{  
punkt_podzialu = partition(tablica,pierwsza_cz,druga_cz); // dzielimy tablice na dwie czesci; 
quicksort(tablica, pierwsza_cz, punkt_podzialu); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy
quicksort(tablica, punkt_podzialu+1, druga_cz); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy
}
}

int main()
{
int ilosc_liczb, i;
cout << "Podaj ilosc liczb do posortowania: "<<endl;
cin >> ilosc_liczb;
int *tablica = new int [ilosc_liczb]; // utworzenie dynamicznej tablicy na 'ilosc_liczb' elementow
cout<<"Liczby losowe do sortowania: \n";
srand(time(NULL));
for (i = 0; i < ilosc_liczb; i++) // wczytywanie liczb do tablicy
{

    tablica[i]=rand()%20;

    cout<<tablica[i]<<"\n";

}

quicksort(tablica,0,ilosc_liczb-1); // wywolanie funkcji sortujacej

cout<<"Liczby posortowane:\n"; 
for (i = 0; i < ilosc_liczb; i++) // wypisanie posortowanej tablicy
cout << tablica[i] << endl;

system("pause");
return 0;
}
edytowany 1x, ostatnio: Shalom, 2015-01-13 12:13

Pozostało 580 znaków

2015-01-13 12:17
int x = tablica[pierwsza_cz+rand()%(druga_cz-pierwsza_cz+1)];

w main:

srand(time(0));

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-13 12:17
2

Chłopie, ty ani nie rozumiesz tego kodu który masz ani nie rozumiesz zadania które masz wykonać. Czeski film. Algorytm który masz napisać również dzieli tablicę na 2 części, z tą różnicą jednak że elementem względem którego dzielisz nie jest środek tablicy (jak w wersji Hoara) ani element skrajny (wersja Lomuto, ta którą udało ci się skądś ściągnąć...) tylko element losowy. Zakładając optymistycznie, że ten algorytm który ukradłeś działa (w co szczerze wątpię) to JEDYNA zmiana polegałaby na zamianie

int x = tablica[pierwsza_cz]; // obieramy x

Na

int x = tablica[pierwsza_cz+rand()%(druga_cz - pierwsza_cz+1)]; // obieramy x

trochę za późno ;]


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 2x, ostatnio: Shalom, 2015-01-13 12:18

Pozostało 580 znaków

2015-01-13 12:26
0

dziękuje Wam bardzo za odpowiedzi :) No niestety jestem dopiero początkujący więc nie jest dla mnie łatwe od tak programowanie dlatego pisałem w poście o wyrozumiałość :) Gdybym był taki dobry nie prosiłbym o pomoc :D jeszcze raz dziękuje i pozdrawiam! :)

Chrzani waść - rand jest prawie w każdym kursie C/C++ przy czym przeważnie na pierwszych kilku stronach. - _13th_Dragon 2015-01-13 13:09

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0