`Witajcie, robię dokładnie to samo zadanie, jednak w czystym C :)
Docelowo wyznaczam** k-ty element z algorytmu Hoara**, po czym sortuję** QuickSortem** elementy od największego do k-tego. Do znalezienia pivota dzielącego na partycje zawsze używam mediany median z algorytmu magicznych piątek. Wszystko działa poprawnie, jednak podczas weryfikacji zadania również pojawia się problem związany z czasem. Może medianę median powinienem liczyć w osobnej tablicy, a nie poprzez swapowanie wartości w tablicy źródłowej? Czy byłby ktoś w stanie wskazać, co możnaby zoptymalizować, aby całość działała sprawniej?
#include <stdio.h>
typedef struct{
int p;
char c;
} struktura;
void swap(struktura *struc, int i, int j){ // zamiana miejscami elementow tablic
struktura temp;
temp = struc[i]; struc[i] = struc[j]; struc[j] = temp;
}
void insertsort(struktura *zadania, int left, int right){ // insert sort do sortowania piecioelementowych czesci tablic
int i, j;
struktura temp;
for(j = right-1; j>=left; j--){
temp = zadania[j];
i=j+1;
while(i<=right && temp.p > zadania[i].p){
zadania[i-1] = zadania[i];
i++;
}
zadania[i-1] = temp;
}
}
int magic_fives(struktura *zadania, int left, int right){ // funkcja zwraca index elementu będącego medianą median 5-elementowych podzbiorów
int left2 = left, right2 = left+4, i=left, med; // left2 i right2 - skrajne wartosci 5-elem. podzbiorow
if(right-left<5){ // gdy zostało tylko 5 lub mniej median po rekurencji...
insertsort(zadania, left, right); // ... posortuj ten zbiór...
return (left+right)/2; //... i zwróć jego element środkowy - jest to MEDIANA MEDIAN
}
else{ // instrukcje dla 5-elementowych podzbiorów:
while(right2<=right){
insertsort(zadania, left2, right2);
swap(zadania, i, left2+2); // medianę przesuń na początek analizowanego przedziału...
i++; // ... pozycja następnej mediany będzie o 1 większa
left2 += 5; // wyznaczenie lewej granicy kolejnej piątki
right2 += 5; // wyznaczenie prawej granicy kolejnej piątki
}
if(left2<=right){ // sprawdzimy jeszcze, czy w ogóle zostały jakieś elementy, z których jeszcze wyznaczymy ostatnią medianę
insertsort(zadania,left2,right);
swap(zadania, i, (left2+right)/2);
i++;
}
return magic_fives(zadania, left, i-1); // wyznaczenie mediany median od 0 do i-1, gdzie 'i-1' to index ostatniej wyznaczonej mediany
}
}
int partition(struktura *zadania, int pocz, int j){
int med_index = magic_fives(zadania, pocz, j); // podzial zawsze względem mediany median
swap(zadania, med_index, pocz); // mediana median na poczatek
int i = pocz;
while(i<j){
while(zadania[i].p<=zadania[pocz].p) i++;
while(zadania[j].p>zadania[pocz].p) j--;
if(i<j) swap(zadania, i, j);
}
swap(zadania,pocz,j);
return j; // index pivota
}
void quick_sort(struktura *zadania, int lewy, int prawy){
int i = lewy, j = prawy;
int x = zadania[magic_fives(zadania,i,j)].p; // podzial zawsze względem mediany median
do {
while((zadania[i].p < x) && (i <= prawy)) i++;
while((zadania[j].p > x) && (j > lewy)) j--;
if(i <= j){
swap(zadania, i, j);
i++; j--;
}
} while (i <= j);
if(lewy < j) quick_sort(zadania, lewy, j);
if(i < prawy) quick_sort(zadania, i, prawy);
}
int main(void){
int n, k, ki, j, i, pivot, a;
scanf("%d", &n);
struktura zadania[n];
for(a=0;a<n;++a) scanf("%d %c", &zadania[a].p, &zadania[a].c);
scanf("%d", &k); // chcemy znaleźć k-ty element i posortować wszystkie od niego większe
j=n-1; i=0;
pivot = partition(zadania, 0, j); // pivot (w tym wypadku mediana median) - na lewo od niego przerzucam liczby mniejsze, na prawo wieksze - zwraca nam jego index
ki=n-k; // liczymy od końca (k-ty element ma index: n-k)
while(ki!=pivot){ //zasada jest prosta - jeśli index pivota jest inny niż index k-tego elementu, wykonuj pętlę while
if(pivot<ki) i = pivot+1; // nasze nowe i musi być jedną pozycję na prawo od pivota
else j=pivot-1;
pivot = partition(zadania, i, j);
}
quick_sort(zadania, ki, n-1);
for(a=n-1;a>=pivot;a--) printf("%c\n", zadania[a].c);
return 0;
}