Algorytm porządkowania tablicy najmniejszą ilością zmian

0

Witam,
Czasem gdy mam wolny czas, wymyślam sobie zadanie i je rozwiązuję. Ostatnio wymyśliłem zadanie, z którym mam problem.
Chciałbym uporządkować tablicę 2 wymiarową najmniejszą ilością zamian komórek. Na studiach miałem podobne zadania, lecz było to ponad 20 lat temu. Z tego co pamiętam, dla podobnych zadań tworzyło się graf. Notatek już nie mam, a w pamięci zostały tylko szczątki typu tworzenie grafu eulerowskiego itp. W żaden sposób nie mogę sobie przypomnieć jak stworzyć graf dla takiego zadania.
Przykładowo mam tablicę:
E5 D5 B2 B1 E3
C5 B4 A1 A5 C1
D2 B5 D3 E2 A2
C3 B3 E4 C4 D4
C2 A3 D1 E1 A4,
którą chcę posortować w jak najmniejszej liczbie zamian pozycji.
Obecnie przychodzi mi do głowy tylko przedstawienie tej tablicy w formie jednowymiarowej, i użycie sortowania szybkiego (quicksort), ale czy to da najmniejszą możliwą ilość zamian?
Pozdrawiam,
Piotr.

screenshot-20170118114715.png
</img>

0

Sortowanie przez wstawianie lub analizowanie cykli: https://en.wikipedia.org/wiki/Cycle_sort

0

Dziękuję za odpowiedź.
Piszę w Delphi, więc szukałem procedur delphi dla Cycle Sort, lecz nie znalazłem.
Znalazłem procedurę w kilku językach na:
https://rosettacode.org/wiki/Sorting_algorithms/Cycle_sort
Przerobiłem z procedurę C na delphi. Dla liczb podanych na stronie (0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6) sortuje w 10 zmianach, lecz dla moich losowań wypada kiepsko.
Moja procedura, którą uważam za nienajlepszą daje o wiele lepsze wyniki. Przy sortowaniach losowo przemieszanej tabeli 5x5, procedura ze strony sortuje w 22 do 24 zmian, przy czym ten sam układ moja procedura sortuje w 17-21 zmian.
Moja procedura najpierw szuka zamian bezpośrednich 2 elementów (czy jednym ruchem możemy ułożyć 2 pola), następnie w pętli próbuje ułożyć pierwszy nieułożony element i sprawdza ile powstało zamian bezpośrednich, zapamiętuje najwyższą możliwość i ją wykonuje, powtarza pętlę do ułożenia całej tabeli.
Nie sądzę aby była to najlepsza metoda, gdyż nie sprawdza wszystkich możliwości przestawień.
Czy zna ktoś inną niż Cycle Sort metodę, lub mógłby udostępnić jej kod w Delphi?
Zamieszczam moją przerobioną z C, może zrobiłem jakiś błąd, że daje tak marne wyniki:

function TForm1.Sortuj(var list:array of string):word;
var m,n,p,r:integer;
    s,tmp:string;
begin
   r:=0;
   for n:=0 to length(list)-1 do begin
      s:=list[n];
      p:=n;
      for m:=n+1 to length(list)-1 do if list[m]<s then inc(p);
      if p=n then continue;
      while s=list[p] do inc(p);
      tmp:=list[p];
      list[p]:=s;
      s:=tmp;
      inc(r);
      while p<>n do begin
         p:=n;
         for m:=n+1 to length(list)-1 do if list[m]<s then inc(p);
         while s=list[p] do inc(p);
         tmp:=list[p];
         list[p]:=s;
         s:=tmp;
         inc(r);
      end;
   end;
   Sortuj:=r;
end;

PS: Dlaczego tagi <delphi> nie działają?

0

Czy zna ktoś inną niż Cycle Sort metodę

Tak, napisałem w poprzedniej wiadomości o dwóch metodach i Tobie zostawiłem wybór, która jest dla Ciebie lepsza.

0

Tak, wiem, lecz sortowaniu przez wstawianie odrzuciłem na wstępie, gdyż z tego co wiem ma dużą liczbę operacji zamian. Z opisu Cycle Sort wynikało że będzie idealna, jednak jej wyniki u mnie wypadły słabo. Spróbuję ją jeszcze raz zrobić z innego przykładu, bo muszę mieć w niej błąd. Obecnie dla tabeli 100-elementowej Cycle sort wykonuje 99 zmian, gdy dla tego samego układu moje sortowanie robi to w 90 zmianach

screenshot-20170119141848.png

0

To szkoda, że odrzuciłeś, bo ma małą liczbę zamian: https://www.quora.com/Which-sorting-algorithm-requires-the-minimum-number-of-swaps

0

Dzięki za info. Spróbuję. Mój błąd.

PS. Znalazłem błąd w "kompilacji" z C do Delphi. Teraz jest znacznie lepiej, lecz zwykle o kilka ruchów gorzej od mojego pomysłu.
Dziękuję za pomoc.
Pozdrawiam,
Piotr.

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