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

Odpowiedz Nowy wątek
2017-01-18 11:41
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>

edytowany 1x, ostatnio: Klakierus, 2017-01-18 11:47

Pozostało 580 znaków

2017-01-18 16:59
0

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

Pozostało 580 znaków

2017-01-19 09:11
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ą?

edytowany 6x, ostatnio: bogdans, 2017-01-19 13:05
Umieść kod w znacznikach formatowania. - Mokrowski 2017-01-19 09:22
@Klakierus: nie zgaduj jakie są znaczniki, kliknij w ostatni przycisk po prawej i wybierz z listy rozwijanej. - bogdans 2017-01-19 13:08

Pozostało 580 znaków

2017-01-19 10:41
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.

Pozostało 580 znaków

2017-01-19 14:18
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

Pozostało 580 znaków

2017-01-19 14:22
0

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

Pozostało 580 znaków

2017-01-19 14:39
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.

edytowany 1x, ostatnio: Klakierus, 2017-01-20 20:42

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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