Drobny problem po posortowaniu tablicy

Witam,

Piszę zadanie do szkoły i mam drobny problem. Zadanie polega na posortowaniu tablicy, według określonego schematu, a później użytkownik podaje jakąś cyfrę będącą numerem wiersza tablicy i jeżeli jest to cyfra z pierwszej połowy tablicy (po posortowaniu) to wyświetla się T, w innym wypadku N.

Przykład
Wejście

4
4 5
12 4
3 0
12 1
2
1
2

Wyjście

N
T

Napisałem taki kod jak poniżej, tablica jest poprawnie posortowana raczej bo sprawdzałem dziesiątki razy i wygląda dobrze, natomiast mam problem z poprawnym wyświetleniem tego T,N. Czy mógłby mi ktoś coś doradzić ? :)

#include <stdio.h>
#include <stdlib.h>

void b_sort(int **tablica, int programisci);

int main()
{

    int programisci,polowa;
    int **tablica;
    int i;
    int ile_pytam, *pytam_sie;

    scanf("%d", &programisci);

    tablica = (int**)malloc(programisci * sizeof(int*));

    for(i=0;i<programisci;i++) {
    tablica[i] = (int*)malloc(3 * sizeof(int));
    tablica[i][0] = i+1;
    scanf("%d %d",&tablica[i][1],&tablica[i][2]); }

    scanf("%d",&ile_pytam);
    pytam_sie = (int*)malloc(ile_pytam * sizeof(int));
    for(i=0;i<ile_pytam;i++) { scanf("%d",&pytam_sie[i]); }

    for(i=0;i<programisci;i++) { tablica[i][3] = i+1; }
    b_sort(tablica,programisci);

    polowa=(programisci/2);

    for(i=0;i<ile_pytam;i++) { if(tablica[pytam_sie[i]][3] < polowa)
         { printf("T\n"); } else { printf("N\n"); } }

     return 0;
}

void b_sort(int **tablica, int programisci)
{
int temp,temp2,temp3,i,zmiana;
do
{
zmiana=0;
i=programisci-1;
do
{
i--;
if (tablica[i+1][1]< tablica[i][1])
{
temp=tablica[i][1]; temp2=tablica[i][2]; temp3=tablica[i][0];
tablica[i][1]=tablica[i+1][1]; tablica[i][2]=tablica[i+1][2]; tablica[i][0]=tablica[i+1][0];
tablica[i+1][1]=temp; tablica[i+1][2]=temp2; tablica[i+1][0]=temp3;
zmiana=1;
}
if (tablica[i+1][1] == tablica[i][1] && tablica[i+1][2] > tablica[i][2])
{
    temp=tablica[i][1]; temp2=tablica[i][2]; temp3=tablica[i][0];
    tablica[i][1]=tablica[i+1][1]; tablica[i][2]=tablica[i+1][2]; tablica[i][0]=tablica[i+1][0];
    tablica[i+1][1]=temp; tablica[i+1][2]=temp2; tablica[i+1][0]=temp3;
    zmiana=1;
}
}
while (i!=0);
}
while (zmiana!=0);

printf("\nTablica po posortowaniu:");
for(i=0; i<programisci; i++) printf("\n%d %d %d %d\n",tablica[i][0],tablica[i][1],tablica[i][2],tablica[i][3]);
}
 

Pozdrawiam

Znalazłem błąd, kod wygląda teraz tak:

 #include <stdio.h>
#include <stdlib.h>

void b_sort(int **tablica, int programisci);

int main()
{

    int programisci;
    int **tablica;
    int i,j;
    int ile_pytam, *pytam_sie;

    scanf("%d", &programisci);

    tablica = (int**)malloc(programisci * sizeof(int*));

    for(i=0;i<programisci;i++) {
    tablica[i] = (int*)malloc(3 * sizeof(int));
    tablica[i][0] = i;
    scanf("%d %d",&tablica[i][1],&tablica[i][2]); }

    scanf("%d",&ile_pytam);
    pytam_sie = (int*)malloc(ile_pytam * sizeof(int));
    for(i=0;i<ile_pytam;i++) { scanf("%d",&pytam_sie[i]); }

    for(i=0;i<programisci;i++) { tablica[i][3] = i; }

    b_sort(tablica,programisci);

    for(i=0;i<ile_pytam;i++) {
    for(j=0;j<programisci;j++) {
        if(pytam_sie[i] == tablica[j][0]) {
            if(j < programisci/2) { printf("T\n"); } else { printf("N\n"); } }
    } }




     return 0;
}

void b_sort(int **tablica, int programisci)
{
int temp,temp2,temp3,i,zmiana;
do
{
zmiana=0;
i=programisci-1;
do
{
i--;
if (tablica[i+1][1]< tablica[i][1])
{
temp=tablica[i][1]; temp2=tablica[i][2]; temp3=tablica[i][0];
tablica[i][1]=tablica[i+1][1]; tablica[i][2]=tablica[i+1][2]; tablica[i][0]=tablica[i+1][0];
tablica[i+1][1]=temp; tablica[i+1][2]=temp2; tablica[i+1][0]=temp3;
zmiana=1;
}
if (tablica[i+1][1] == tablica[i][1] && tablica[i+1][2] > tablica[i][2])
{
    temp=tablica[i][1]; temp2=tablica[i][2]; temp3=tablica[i][0];
    tablica[i][1]=tablica[i+1][1]; tablica[i][2]=tablica[i+1][2]; tablica[i][0]=tablica[i+1][0];
    tablica[i+1][1]=temp; tablica[i+1][2]=temp2; tablica[i+1][0]=temp3;
    zmiana=1;
}
}
while (i!=0);
}
while (zmiana!=0);

printf("\nTablica po posortowaniu:");
for(i=0; i<programisci; i++) printf("\n%d %d %d %d\n",tablica[i][0],tablica[i][1],tablica[i][2],tablica[i][3]);
}

Odpowiedzi są poprawne, ale sortowanie przekracza mi dozwolony w zadaniu czas. Jak mógłbym zoptymalizować ten kod ?

Pozdrawiam

Jakbyś opisał...

1. co dostajesz na wejściu
2. w jaki sposób ma być posortowana tablica
3. "użytkownik podaje jakąś cyfrę będącą numerem wiersza tablicy i jeżeli jest to cyfra z pierwszej połowy tablicy (po posortowaniu)" - tego nie kapuję wcale
   ...to może ktoś odpowie.

Już mówię :)

Oto treść zadania:

Niestety ostatni pomysł szefa UVN pogrążył firmę w chaosie. Wszyscy programiści, zamiast pisać programy, które powinni, postanowili wziąć udział w ogłoszonym tydzień wcześniej konkursie. Z tego powodu wszystkie projekty przeżywają zastój, a tym samym UVN ponosi duże straty. Klienci już zaczynają pytać o postępy w produkcji, których oczywiście nie ma. Szef w międzyczasie zarządził programowanie w parach, bo gdzieś przeczytał, że to zwiększa produktywność. Miał szczęście, że akurat liczba programistów na to pozwalała.

Jednak to nie przyniosło oczekiwanych skutków. Zatem szef postanowił oszczędzić tym razem zwalniając połowę wszystkich programistów UVN. Aby jednak nie narazić się na procesy o bezpodstawne zwolnienie z pracy, wymyślił pewien fortel. Mianowicie najsłabszym programistom przydzieli najtrudniejsze zadania. W wyniku tego ci utkną w martwym punkcie, niczego nie napiszą, a szef będzie miał pretekst, aby ich zwolnić. Szef powołał tajny zespół najlepszych programistów, którzy napiszą program przydzielający zadanie (trudne lub łatwe) na podstawie wyników pracy programisty. Wskaźnikiem jakości pracy jest liczba linii kodu napisanych w ciągu ostatniego tygodnia oraz liczba błędów wykrytych w ciągu ostatniego miesiąca w kodzie napisanym przez danego programistę. Oznacza to, że lepszy jest programista, który napisał więcej linii kodu. W przypadku równej liczby linii, brana jest pod uwagę liczba błędów - oczywiście lepszy jest ten programista, który popełnia ich mniej. W trakcie przygotowań stwierdzono, że nie ma dwóch programistów, którzy napisali tyle samo linii kodu i popełnili tyle samo błędów.

 Wejście

Na wejściu pojawia się liczba programistów n (2 ≤ n ≤ 20000). W kolejnych n liniach pojawiają się liczby linii kodu napisanych l (0 ≤ l ≤ 100000) oraz liczby błędów b (0 ≤ b ≤ 100000) popełnionych przez kolejnego programistę, począwszy od tego z numerem 0, a na numerze n-1 kończąc. Następnie pojawia się liczba zapytań z (0 ≤ z ≤ n) szefa do programu. W kolejnych z liniach umieszczone są pojedyncze zapytania, z których każde to numer programisty.
Wyjście

Dla każdego zapytania szefa czyli numeru programisty należy odpowiedzieć, czy należy programiście przydzielić trudne zadanie. Jeśli tak, program powinien wypisać literę T, a w przeciwnym razie literę N. 

PS: Przed napisaniem postu @up zedytował swój post. Program działa już ok, ale na szkolnej sprawdzarce wyrzuca przekroczenie czasu w jednym teście (Dozwolone jest 0.20s, a u mnie jest aż 1.99s).

Nie przyjmuje Ci czasowo, bo używasz praktycznie najgorszego możliwie sortowania (pomijam kompletne zabawki w stylu bogosort). Są trzy podstawowe sensowne sortowania: quicksort (niestabilny, najszybszy przy losowych danych, trzeba pamiętać jednak o dobrym wyborze pivota, np. losowym, przy złym łatwo wpaść w O(n^2)), mergesort (stabilny z gwarantowanym O(n log n)) lub heapsort (niestabilny, z gwarantowanym O(n log n)). Z bardziej zaawansowanych jest introsort (quicksort ze spadkiem do heapsorta dla zachowania O(n log n) i insertion sort dla małych ilości danych w podtablicy) oraz Timsort (wariant mergesorta wykorzystujący istniejący porządek danych. wolniejszy dla danych losowych od quicksorta, ale w większości przypadków rzeczywistego użycia sprawdza się zadziwiająco dobrze).

Ogólnie to nie potrzebujesz sortować tej tablicy, tylko wybrać środkowy element. Nadaje się do tego najbardziej albo quickselect, albo algorytm magicznych piątek. Mimo tego, że ten drugi gwarantuje liniowy czas działania (quickselect może być nawet kwadratowy), to w praktyce będzie często wolniejszy.

W bibliotece standardowej C++ zawarte są algorytmy z obydwu tych klas (introsort, merge sort oraz quickselect ze spadkiem do heapselect), ale ze względów dydaktycznych radzę Ci spróbować zaimplementować chociaż po jednym z każdej klasy. Powinieneś w internecie bez kłopotu znaleźć o nich informację. Za każdym razem, gdy sortujesz tablicę bąbelkowo, przez Ciebie ginie dziecko w Afryce.

Dzięki wielkie za odpowiedź, tak też myślałem, że to wina sortowania. Program ma działać w czasie O(n²+z), jest to w warunkach zadania. Próbowałem użyć quicksorta, ale coś mi nie idzie z jego implementacją. To znaczy sortuje poprawnie jedną kolumnę, ale innych już nie. Jakbym źle interpretował tego ifa:

if (tablica[i+1][1] == tablica[i][1] && tablica[i+1][2] > tablica[i][2])

Można by liczyć, na drobną pomoc ? :(

Użyj struktur i funkcji, będzie łatwiej i wyłapiesz błędy. (1) Opakuj programistę w strukturę. (2) Napisz funkcję porównującą programistów. (3) Możesz użyć biblioteczny qsort do sortowania. Programiści do sprawdzenia są zadawani wg. pierwotnego indeksu więc nie możemy tej informacji (o ich kolejności pierwotnej) stracić podczas sortowania. Zapamiętywanie indeksu w tablicy nie jest dobrym pomysłem. Przed sortowaniem tablicy zrób jej kopię lub (4) utwórz odrębną tablicę programistów do przetestowania (to drugie zastosowano poniżej).

/* (1) */
struct {
   int linie;
   int bledy;
}
Programista;

/* (2) */
int ProgramistaPorownaj(void *a, void *b)
{
    Programista *proramista_a = (Programista*)a;
    Programista *proramista_b = (Programista*)b;
    // tutaj zwracasz wynik porównania dwóch programistow
    // <0 jeśli a < b
    //  0 jeśli a == b
    // >0 jeśli a > b
}

/* wczytujemy 'n' programistow */
Programista *programisci = ...

/* (4) wczytujemy 'z' programistow do przetestowania */
Programista *test = ...
for (i ... ) {
    scanf("%d", &indeks);
    test[i] = programisci[indeks];
}

/* (3) sortujemy */
qsort(programisci, n, sizeof(Programista), ProgramistaPorownaj);

/* próg, najlepszy z programistów do wywalenia */
Programista poprzeczka = programisci[n / 2];

/* wykonujemy i-ty test */
wywalic = ProgramistaPorownaj(&test[i], &poprzeczka) <= 0 ? 'T' : 'N';

No i teraz pytanie, co zrobić jeśli programiści nie dzielą się na 2 równe połowy? Bo obecnie powyższy algorytm wybierze wariant sprawiedliwy (równi programiści równie wylatują) oraz taki aby wyleciała co najmniej połowa. Czyli np. dla [1,2,2,2,2,3] tylko [3] zostaje.

Bardzo bym chciał użyć qsort ale nie mogę :( Musi być to własna implementacja sortowania. W założeniu jest, że liczba programistów jest parzysta.

Pozdrawiam

No to nie używaj 'qsort', napisz własne sortowanie lub inny algorytm proponowany przez @Zjarek. Wszystko inne pozostaje aktualne.

andegrand napisał(a):

W założeniu jest, że liczba programistów jest parzysta.
To nie rozwiązuje problemu. Np. jeśli mamy tylko dwóch programistów, obydwoje równi, co wtedy zrobić?

Masz wyżej w treści takie zdanie: "W trakcie przygotowań stwierdzono, że nie ma dwóch programistów, którzy napisali tyle samo linii kodu i popełnili tyle samo błędów. "
Więc to nie problem. Próbuję implementować quicksort, ale póki co nie wychodzi. Mam jeszcze pytanie na strukturach będzie to działało szybciej niż na tablicach tak jak ja zrobiłem ?

Nie chodzi o szybkość działania, różnica w tych dwóch przypadkach będzie pomijalna. Na strukturach będzie Ci łatwiej ten program napisać. Dobrym rozwiązaniem będzie wyrzucenie porównywania struktur poza sortowanie do oddzielnej funkcji. Nie musisz tego pisać generycznie (jak jest napisany oryginalny qsort), bo w C to jest trochę zabawy, z rzutowaniem void * na char *, memcpy itd.

Próbuję teraz sortować to tak:

void sortuj(struct List * Lista){
int i,j,pom;
for(i=n-1;i>0;i--)
for(j=0;j<i;j++)
if (Lista->tab[j]>Lista->tab[j+1]){
pom=Lista->tab[j];
Lista->tab[j]=Lista->tab[j+1]
Lista->tab[j+1]=pom;
}
} 

Niestety program mi się sypie, już tracę powoli nadzieję, że to zrobię :(

Ale jaka znowu lista tablic? Użyj jednej tablicy struktur i funkcji porównującej, kod masz prawie gotowy. Będzie łatwiej.

Próbuję zaadaptować Twój kod, ale nie wychodzi mi :(
Zmieniłem sortowanie na takie jak poniżej, ale dalej jest coś nie tak, czy mógłby ktoś wyłapać błąd czy to raczej nie realne ?

 #include <stdio.h>
#include <stdlib.h>

void SelectionSort(int **tablica, int programisci);

int main()
{

    int programisci;
    int **tablica;
    int i,j;
    int ile_pytam, *pytam_sie;

    scanf("%d", &programisci);

    tablica = (int**)malloc(programisci * sizeof(int*));

    for(i=0;i<programisci;i++) {
    tablica[i] = (int*)malloc(2 * sizeof(int));
    tablica[i][0] = i;
    scanf("%d %d",&tablica[i][1],&tablica[i][2]); }

    scanf("%d",&ile_pytam);
    pytam_sie = (int*)malloc(ile_pytam * sizeof(int));
    for(i=0;i<ile_pytam;i++) { scanf("%d",&pytam_sie[i]); }

    SelectionSort(tablica,programisci);

    for(i=0;i<ile_pytam;i++) {
    for(j=0;j<programisci;j++) {
        if(pytam_sie[i] == tablica[j][0]) {
            if(j < programisci/2) { printf("T\n"); } else { printf("N\n"); } }
    } }




     return 0;
}
/*
void b_sort(int **tablica, int programisci)
{
int temp,temp2,temp3,i,zmiana;
do
{
zmiana=0;
i=programisci-1;
do
{
i--;
if (tablica[i+1][1]< tablica[i][1] || (tablica[i+1][1] == tablica[i][1] && tablica[i+1][2] > tablica[i][2]))
{
temp=tablica[i][1]; temp2=tablica[i][2]; temp3=tablica[i][0];
tablica[i][1]=tablica[i+1][1]; tablica[i][2]=tablica[i+1][2]; tablica[i][0]=tablica[i+1][0];
tablica[i+1][1]=temp; tablica[i+1][2]=temp2; tablica[i+1][0]=temp3;
zmiana=1;
}
}
while (i!=0);
}
while (zmiana!=0);
}
*/

void SelectionSort(int **tablica, int programisci){
int i,j,max,pom,pom1,pom2;
for(i=programisci;i>1;i--){
max=0;
for(j=1;j<i;j++)
    if (tablica[max][1]<tablica[j][1] || (tablica[max][1] == tablica[j][1] && tablica[max][2] > tablica[j][2])) {
max=j;
pom=tablica[max][0]; pom1=tablica[max][1]; pom2=tablica[max][2];
tablica[max][0]=tablica[i-1][0]; tablica[max][1]=tablica[i-1][1]; tablica[max][2]=tablica[i-1][2];
tablica[i-1][0]=pom; tablica[i-1][1]=pom1; tablica[i-1][2]=pom2;
} }
printf("\nTablica po posortowaniu:");
for(i=0; i<programisci; i++) printf("\n%d %d %d %d\n",tablica[i][0],tablica[i][1],tablica[i][2],tablica[i][3]);
}