Sortowanie Permutacji

Michał Boryczka
Informatyka Stosowana III rok
Wydział Fizyki Astronomii i Informatyki Stosowanej
Uniwersytet Jagielloński
Kraków 2011
Mathematica 7.0

Zadanie

Notebook prezentuje animację permutacji liczb {1,2,3,...,n} i jej sortowanie za pomocą trzech wybranych sposobów [1, 2].

Animacja permutacji

Wczytanie wartości n, generacja listy permutacji i wybór losowej permutacji.

ClearAll["Global`*"]

n=Input["Podaj wartość n"];
Lista =Range [1,n];

Tworzymy wszystkie możliwe permutacje ciagu liczb od 1 do n.

Permutacja =Permutations[Lista ];
dlugosc=Length[Permutacja]

Wybieramy losową permutację.

Losoj[zbior_]:=Block[{x=zbior},l=Random[Integer,{1,Length[x]}];tmp=x[[l]]]
tmp=Losoj[Permutacja]
tmp1=tmp2=tmp3=tmp;

Animacja permutacji.

A=Graphics[{AbsolutePointSize[6],Darker[Blue],Point[{0,0}]}];
Manipulate[ListPlot[Permutacja[[j]],PlotMarkers->{A},Joined->False,AxesLabel->{X,Y},Background->Green,DataRange->{1,Length[tmp]},Frame->ramka],{{j,1,"Numer permutacji"},1,Length[Permutacja],1},{ramka,{False,True}}]

Sortowania

Sortowanie bąbelkowe

Wstęp teoretyczny.

Algorytm sortowania bąbelkowego składa się z dwóch pętli For, z ich pomocą przechodzimy przez cały zbiór elementów porównując kolejne pary liczb. W przypadku, gdy pierwszy element pary jest większy od drugiego następuje zamiana porównywanych wartości. Algorytm zakończy się zwróceniem listy uporządkowanej rosnąco. Złożoność sortowania bąbelkowego wynosi  O((n^2)).

Kod.

BubleSort[end_]:=Block[{koniec=end},
For[j=1,j≤koniec,j++,
For[i=1,i≤koniec-1,i++,
If[tmp1[[i]]>tmp1[[i+1]],z=tmp1[[i]];tmp1[[i]]=tmp1[[i+1]];tmp1[[i+1]]=z]
]
];tmp1];

Graficzne przedstawienie sortowania bąbelkowego.

A=Graphics[{AbsolutePointSize[6],Darker[Blue],Point[{0,0}]}];
Manipulate[ListPlot[BubleSort[j],PlotMarkers->{A},Joined->False,AxesLabel->{X,Y},Background->Green,DataRange->{1,Length[tmp1]},Frame->ramka],{{j,1,"Krok"},1,Length[tmp1],1},{ramka,{False,True}}]

Sortowanie przez wstawianie

Wstęp teoretyczny.

Algorytm sortowania przez wstawianie składa się z dwóch pętli for. Pętla pierwsza, zewnętrzna pobiera elementy zbioru. Naszym celem jest utworzenie listy uporządkowanej zaczynającej się od końcu zbioru. Pętla druga, wewnętrzna dla danego elementu wyszukuje jego miejsce na liście uporządkowanej. Jeśli wartość danego elementu jest wartością pośrednią między dwoma już istniejącymi na liście  elementami, to są one rozsuwane i element, którym się aktualnie zajmujemy trafia w tak powstałe miejsce. Jeśli natomiast jest on większy od wszystkich już wstawionych elementów trafia na koniec listy. Tym prostym sposobem lista uporządkowana powiększa się, aż do momętu, gdy wszystkie dane z ciągu wejściowego zostaną umieszczone na liście wynikowej. Złożoność sortowania przez wstawianie wynosi O((n^2)).

Kod.

InsertionSort[end_]:=Block[{koniec=end},
For[z=koniec-1,z>=1,z--,
x=tmp2[[z]];
tmp2[[z]]="";
For[t=z,t≤Length[tmp2],t++,
If[tmp2[[t]]<x,tmp2[[t-1]]=tmp2[[t]];tmp2[[t]]=x;,tmp2[[t-1]]=x;Break[]];
];
];tmp2];

Graficzne przedstawienie sortowania przez wstawianie.

A=Graphics[{AbsolutePointSize[6],Darker[Blue],Point[{0,0}]}];
Manipulate[ListPlot[InsertionSort[j],PlotMarkers->{A},Joined->False,AxesLabel->{X,Y},Background->Green,DataRange->{1,Length[tmp2]},Frame->ramka],{{j,1,"Krok"},1,Length[tmp2]-1,1},{ramka,{False,True}}]

Sortowanie poprzez rosnące podciągi

Wstęp teoretyczny.

Algorytm sortowania przez wstawianie został napisany specjalnie dla danych jakie zostają wygenerowane podczas tworzenia permutacji ciągu liczb. Zasada jego działania jest następująca,z ciagu danych wybieramy wszystkie rosnące podciagi liczb. Z tak otrzymanych podciagów wybieramy najdłuższy, jeśli najdłuższy podciąg ma długość równą długości permutacji algorytm zakończy się. W przeciwnym wypadku uzupełniamy go o brakujące elementy. Elementy wstawiane pozyskujemy z listy równej różnicy listy wejściowej i wybranego najdłuższego podciągu.

Kod.

(* Znajduję rosnące podciągi permutacji *)
podciag=Table[0,{n},{1}];
For[j=1,j<=n,j++,
podciag[[j,1]]=tmp3[[j]];
For[i=j,i<=n,i++,
{If[tmp3[[j]]<tmp3[[i]]&&Last[podciag[[j]]]<tmp3[[i]],
AppendTo[podciag[[j]],tmp3[[i]]],

]
}
]
]
podciag;
(* Znajduję najdłuższy podciąg rosnący *)
licznik=Table[1,{n}];
For[j=1,j≤n,j++,
licznik[[j]]=Length[podciag[[j]]]
]
podciagMax=podciag[[First[Position[licznik,Max[licznik]][[1]]]]];
Print["Najdłuższy podciąg rosnący: ",podciagMax];
(* Reszta z permutacji (permutacja bez najdłuższego podciągu rosnącego)*)
reszta=Complement[tmp3,podciagMax];
Print["Reszta: ",reszta];

(* Scalenie reszty i najdłuższego podciągu rosnącego *)
SubsequenceSort[end_]:=Block[{koniec=end},
For[i=1,i≤ koniec,i++,

If[reszta=={},Break[]];
If[reszta[[1]]<podciagMax[[i]],podciagMax=Insert[podciagMax,reszta[[1]],i];reszta=Delete[reszta,1];];
If[reszta=={},Break[]];
If[reszta[[1]]>Max[podciagMax],podciagMax=AppendTo[podciagMax,reszta[[1]]];reszta=Delete[reszta,1];];
If[Length[podciagMax]==(koniec),Return[podciagMax];]

];podciagMax];

Graficzne przedstawienie sortowania przez rosnące podciągi.

A=Graphics[{AbsolutePointSize[6],Darker[Blue],Point[{0,0}]}];
Manipulate[ListPlot[SubsequenceSort[j],PlotMarkers->{A},Joined->False,AxesLabel->{X,Y},Background->Green,DataRange->{1,Length[tmp3]},Frame->ramka],{{j,1,"Krok"},1,Length[tmp3],1},{ramka,{False,True}}]

Literatura

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, CliffordStein Wprowadzenie do algorytmów (Wydawnictwa Naukowo Techniczne, Warszawa 2001)

[2] http://edu.i-lo.tarnow.pl/inf/alg/003_sort/index.php