Sortowanie tabeli [faza grupowa mistrzostw]

Reprezentacja Polski w piłce nożnej sprawiła niespodziankę i awansowała do finałowej imprezy w Katarze. W związku z tym postanowiłem napisać sobie program, który będzie umożliwiał wpisywanie wyników meczy oraz będzie prezentował wszystkie potrzebne dane. Dodam też opcje stawiania wyników :P

Ale, chcieć a umieć napisać taki program, to dwie różne sprawy. Na razie tworzę ogólną koncepcję.
W tym poście, chciałbym się skupić na problemie wyłonienia zespołów, które wygrały grupę (jest ich 8 - 32 zespoły).

Jak wiadomo, grupa liczy 4 zespoły, co daje 6 meczów. Awans uzyskują 2 drużyny (z każdej z grup).
Wg specyfikacji FIFA, obowiązują następujące reguły (jeśli drużyny mają tyle samo punktów):

1 - Punkty zdobyte we wszystkich meczach grupowych
2 - Różnica bramek we wszystkich meczach grupowych
3 - Liczba bramek zdobytych we wszystkich meczach grupowych

4 - Punkty zdobyte w meczach rozegranych pomiędzy zainteresowanymi drużynami
5 - Różnica bramek w meczach rozegranych pomiędzy zainteresowanymi drużynami
6 - Liczba bramek zdobytych w meczach rozegranych pomiędzy zainteresowanymi drużynami
7 i 8 to FairPlay oraz Losowanie (co muszę ewentualnie rozwiązać inaczej)

Przechodząc do sedna.
Jaką metodę obralibyście do wyłonienia 2 drużyn (spośród 4) uwzględniając powyższe warunki?
Jak się do tego zabrać? Może ktoś z Was bawił się w takie rzeczy... chętnie wysłucham.
Jak sprytnie i w najmniejszej liczbie kroków ułożyć te dane (czyli np. przypisać drużynie 2 pozycję 1 (awans), drużynie 4 pozycję 2 (awans) oraz drużynom 1 oraz 3 odpowiedno 3 i 4 miejsce?

Nie chodzi mi o żaden kod, tylko pomysł na wykonanie... na razie jestem na etapie koncepcji... do listopada jeszcze sporo czasu :)

Dzięki,
-Pawel

Ludzie, Polska na Mistrzostwach Świata!!! :)

Mod przeniósł post do tego działu, ale aplikację piszę w Delphi...
Na razie, pomysł jest taki, że robię "na piechotę" - to jest sprawdzam każdy warunek dla każdej z drużyn (kto ma więcej punktów, a jeśli jest remis, to kolejne punkty regulaminu, czyli np. różnica bramek).
Będzie tego mnóstwo...
Mam nadzieję, że jest prostszy sposób.

No chyba to jest jasne - masz powiedziane jak porównywać wyniki dwóch drużyn. Więc posortuj drużyny względem tego porządku (niemal) zupełnego (chyba ten rzut monetą się prawie nigdy nie zdarza).

Posortuj... Jak? Jak się do tego sprytnie zabrać?

@Pepe: https://duckduckgo.com/?t=ffab&q=quicksort&ia=web

Mogę się mylić, bo wciąż rozkminiam temat... ale, tu nie chodzi o sam algorytm sortowania. A sposób użycia.
Bo cóż z tego, że posortuje tablice wg. punktów, skoro przypadków jest wiele...
Załóżmy, że 4 zespoły mają po 6pkt. Zatem, sortowanie nic nie da, bo trzeba użyć kolejnego sortowania, już uwzględniając fakt, że trzeba uwzględnić nie liczbę punktów, tylko różnice bramek, etc...
Chodzi mi zatem o podejście do tematu, nie sam algorytm sortowania.

Ps: Istnieje szansa, że nie wiem o czym piszę... i rozwiązanie jest prostsze, niż mi się wydaje.

Wystarczy jedno posortowanie, jedyne co musisz zmienić to porównywanie dwóch drużyn, uwzględniając wszystkie warunki.

funkcja czy_a_jest_wieksze_niz_b(druzyna a, druzyna b):
  jeśli a.punkty != b.punkty:
    zwróć a.punkty > b.punkty
  jeśli a.stosunek_bramek != b.stosunek_bramek:
    zwróć a.stosunek_bramek > b.stosunek_bramek
  itd...

to byłaby funkcja która porównuje dwie drużyny podczas sortowania

Eh... jakoś mi to nie idzie. Nie wiem jak to poskładać do kupy...
Samo posortowanie po punktach dużo upraszcza, ale pozostaje kwestia sytuacji, gdy punkty są takie same...
Idzie jak po grudzie...

Mamy klasę Druzyna, jej atrybuty to:

• punkty
• roznica_bramek
• zdobyte_bramki

Załóżmy że mamy taką tablicę drużyn pewnej grupy, atrybuty są w takiej kolejności jak wyżej:

[Polska(6, -3, 4), Niemcy(8, 6, 3), Czechy(8, 6, 1), Ukraina(6, 1, 3)]

komparator:

funkcja czy_a_>_b(Druzyna a, Druzyna b):
  jezeli a.punkty != b.punkty:
    zwroc a.punkty > b.punkty
  jezeli a.roznica_bramek != b.roznica_bramek:
    zwroc a.roznica_bramek > b.roznica_bramek
  zwroc a.zdobyte_bramki > b.zdobyte bramki

Funkcja sortująca:

funkcja sortuj(Tab[Druzyna], n):
  dla i = 0, 1 ... n-1:
    dla j = i+1, i+2 ... n-1:
      jeżeli czy_a_>_b(Tab[i], Tab[j]):
        zamien(Tab[i], Tab[j])

Jeżeli wykonamy funkcję sortuj to tablica zostanie posortowana, i będzie wyglądać tak:

[Niemcy(8, 6, 3), Czechy(8, 6, 1), Ukraina(6, 1, 3), Polska(6, -3, 4)]

Kluczowe jest dla ciebie żeby nie używać tylko operatora > ale swojej własnej funkcji która porównuje dwie drużyny.

Dziękuję.
Będę starał się napisać własną funkcję sortującą po punktach (algorytm QuickSort), która będzie zawierać funkcję porównującą inne parametry (różnica bramek, ilość bramek strzelonych).
Piszesz o klasie Drużyna. Chyba użyje rekordu. Ogólnie, muszę zastanowić się nad typem danych, które będę przechowywać informacje dla każdej z drużyn. Na szczęście, do listopada stosunkowo daleko :)

Są jeszcze punkty regulaminu 4/5 i 6, których jeszcze nie ogarniam...
4 - Punkty zdobyte w meczach rozegranych pomiędzy zainteresowanymi drużynami
5 - Różnica bramek w meczach rozegranych pomiędzy zainteresowanymi drużynami
6 - Liczba bramek zdobytych w meczach rozegranych pomiędzy zainteresowanymi drużynami

Punkty 7 i 8 raczej się nie wydarzą (FairPlay oraz Losowanie) - choć na tę okoliczność dodam furtkę manualnego zaznaczenia awansującej drużyny.

Ja to pisałem w pseudokodzie, nigdy w życiu nie widziałem Delphi na oczy :P.
Musisz gdzieś zapisać wyniki meczy. I później użyć osobnych funkcji które by sprawdzały każdy z tych warunków.

funkcja czy_a_>_b(Druzyna a, Druzyna b):
  jezeli a.punkty != b.punkty:
    zwroc a.punkty > b.punkty
  jezeli a.roznica_bramek != b.roznica_bramek:
    zwroc a.roznica_bramek > b.roznica_bramek
  jezeli a.zdobyte_bramki != b.zdobyte_bramki:
    zwroc a.zdobyte_bramki > b.zdobyte bramki
  jezeli punkty_zdobyte_przez_x_w_meczach_z_y(a, b) != punkty_zdobyte_przez_x_w_meczach_z_y(b, a):
    zwroc punkty_zdobyte_przez_x_w_meczach_z_y(a, b) > punkty_zdobyte_przez_x_w_meczach_z_y(b, a)
  jezeli roznica_bramek_miedzy_x_i_y(a, b) != 0:
    zwroc roznica_bramek_miedzy_x_i_y(a, b) > 0
  zwroc liczba_bramek_zdobytych_przez_x_w_meczach_z_y(a, b) > liczba_bramek_zdobytych_przez_x_w_meczach_z_y(b, a)

jakoś tak to może wyglądać

Minęło trochę czasu, a ja wciąż nie wiem jak to zrobić...
Dlatego, może inaczej. Czy jest ktoś kto podjąłby się zadania napisania kodu, który pozwoliłby zrealizować funkcję sortowania drużyn, co pozwoli wyłonić 2 drużyny które awansują do fazy pucharowej?
Implementacja w Delphi. Ile taka usługa by kosztowała?

-Pawel