Jak bedzie wygladała tablica po wywołaniu po raz pierwszy procedury PARTITION w sortowaniu szybkim gdy za piwot uznajemy ostatni element?
tab = [41,15,7,33,34,6,2,9,19,14]
Jak bedzie wygladała tablica po wywołaniu po raz pierwszy procedury PARTITION w sortowaniu szybkim gdy za piwot uznajemy ostatni element?
tab = [41,15,7,33,34,6,2,9,19,14]
Rozpisz sobie na kartce, a quicksort jest tutaj:
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-4-quicksort-randomized-algorithms/
lion137 napisał(a):
Rozpisz sobie na kartce, a quicksort jest tutaj:
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-4-quicksort-randomized-algorithms/
Czy wynik
[7,41,15,33,34,6,2,9,19,14] po pierwszym wywolaniu partition jest dobry?
Próbowałam wrzucić kod do visuala ale nie wiem w ktorym miejscu umiesic console.writeline by pokazywalo wynik po kazdym wyjsciu z petli :c
Tutaj Masz quicksort:
https://github.com/lion137/Fundamental_Algorithms/blob/master/linear_time_selec.cpp
Zamiast losowego piwota, Wybierz partition
, (tam piwotem jest ostatni element), a drukowanie tablicy Umieść po wywołaniu partition
:
void quicksort(int a[], int s, int n) {
if (s < n) {
int r = partition_random(a, s, n);
printAr(a, n);
quicksort(a, s, r - 1);
quicksort(a, r + 1, n);
}
}
Jak wybierasz za pivot ostatni element, tutaj 14, to w lewej podtablicy znajdą się liczby mniejsze, po prawej będą te większe, na środu 14, czyli
[41,15,7,33,34,6,2,9,19,14] -> [7, 6, 2, 9, 14, 41, 15, 33, 34, 19]