Algorytmy i struktury danych/Sortowanie - BubbleSort, SelectionSort, InsertionSort: Różnice pomiędzy wersjami

Aktualna wersja na dzień 10:28, 5 wrz 2023

Ten wykład poświęcimy prostym algorytmom sortowania. Zanalizujemy ich wady i zalety, co przygotuje nas do poszukiwania algorytmów lepszych. Zacznijmy od zdefiniowania problemu.

Definicja problemu

Niech $(U,\leq )$ będzie zbiorem liniowo uporządkowanym z relacją porządkującą $\leq$ i niech $c_{1},c_{2},\ldots ,c_{n}$ będzie ciągiem $n$ elementów z $U$ , dla pewnego całkowitego $n>0$ . Należy znaleźć permutację $c_{i_{1}},c_{i_{2}},\ldots ,c_{i_{n}}$ taką, że $c_{i_{1}}\leq c_{i_{2}}\leq \ldots \leq c_{i_{n}}$ .

Uwaga: dla pary elementów $x,y\in U$ będziemy pisali $x<y$ ( $x>y$ ), gdy $x\leq y$ ( $y\leq x$ ) oraz $x\neq y$ .

W tym wykładzie przyjmujemy, że elementy ciągu $c$ znajdują się w tablicy $a[1..n]$ , tzn. $a[1]=c_{1},a[2]=c_{2},\ldots ,a[n]=c_{n}$ . Będziemy także chcieli, żeby posortowany ciąg $c$ znajdował się nadal w tablicy $a$ , tzn. wynikiem sortowania ma być $a[1]=c_{i_{1}}\leq a[2]=c_{i_{2}}\leq \ldots \leq a[n]=c_{i_{n}}$ . Dla wygody dalszych rozważań przyjmijmy, że tablica $a$ jest indeksowana od $0$ , i że $a[0]$ zawiera element, który nie jest większy od żadnego elementu z $a[1..n]$ , tzn. dla każdego $i=1,2,\ldots ,n$ , $a[0]\leq a[i]$ .

Zauważmy, że w tak sformułowanym problemie sortowania nic nie wiemy o naturze elementów z $U$ . Na $U$ mogą składać się zarówno liczby całkowite lub rzeczywiste, jak i $U$ może być zbiorem rekordów, które należy posortować według ich kluczy. Jedynym sposobem ustalenie porządku w tablicy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle a} jest porównywanie jej elementów parami. Operacja porównania będzie operacją dominującą w naszych algorytmach. Ponieważ będziemy chcieli ustalić wynik także w tablicy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle a} , potrzebna nam jest jeszcze operacja zamiany dwóch elementów w tablicy. Operacją tą będzie operacja Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle Exchange(i,j)} polegająca na zamianie elementów w tablicy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle a} z pozycji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i} oraz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle j} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1\le i, j \le n} .

Sortowanie bąbelkowe (BubbleSort)

Jest to jeden z najprostszych algorytmów sortowania. Sortowanie bąbelkowe jest wykonywane w Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n-1} fazach. W fazie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i} -tej wyznaczany jest Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i} -ty najmniejszy element. Załóżmy, że po Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i-1} pierwszych fazach mamy wyznaczone i uporządkowane Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i-1} najmniejsze elementy, tzn. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle a[1]\le a[2]\le \ldots a[i-1]} i dla każdego Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle k = i, i+1, \ldots, n} mamy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle a[i-1] \le a[k]} . W fazie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i} -tej porównywane są kolejno elementy w parach Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (a[n], a[n-1])} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (a[n-1], a[n-2])} , ..., Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (a[i+1], a[i])} . Jeżeli elementy w parze nie są uporządkowane, dokonujemy ich zamiany. Oto algorytm sortowania bąbelkowego.

Algorytm Sortowanie bąbelkowe

 BubbleSort
 1  for Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i:=1}
 to Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n-1}
 do
 2    for  $j:=n$   downto  $i+1$  do
 3    if  $a[j-1]>a[j]$  then
 4       $Exchange(j-1,j)$ ;

Poniżej zilustrowano działanie sortowania bąbelkowego.

<applet code="SortItem" archive="images/a/a5/Sort2.jar" width="300" height="300"> alg=BubbleSort delay=1000 </applet>

Zaletą sortowania bąbelkowego jest jego prostota i bardzo krótki kod. Niestety jego główną wadą jest to, że zawsze, niezależnie od danych, wykonuje tyle samo porównań: $n-1$ w pierwszej fazie, $n-2$ w drugiej, ..., $1$ w fazie ostatniej, co daje łącznie $\sum _{i=1}^{n-1}(n-i)={\frac {n(n-1)}{2}}$ porównań. Liczba zamian może się zmieniać od $0$ do ${\frac {n(n-1)}{2}}$ . Zauważmy, że tak zapisany algorytm sortowania bąbelkowego zawsze wykonuje $n-1$ faz, nawet wtedy, gdy ciąg wejściowy jest już uporządkowany. Celem ćwiczenia 1 jest taka modyfikacja algorytmu, aby zakończyć jego działanie, kiedy tylko zostanie stwierdzone, że tablica $a$ jest już uporządkowana.

Ćwiczenie 1

Zmodyfikuj algorytm sortowania bąbelkowego w taki sposób, żeby jego wykonywanie kończyło się z chwilą stwierdzenia, że tablica $a$ jest już posortowana.

Odpowiedź do ćwiczenia 1

Algorytm BubbleSortBis

 1  for  $i:=1$  to  $n-1$  do
 2  begin
 3     $posortowana:=$  TRUE;
 4    for  $j:=n$   downto  $i+1$  do
 5    if  $a[j-1]>a[j]$  then
 6      begin  $exchange(j-1,j)$ ;  $posortowana:=$  FALSE end;
 7    if  $posortowana$  then
 8    //nie wykonano żadnych zamian;
 9    //koniec wykonywania zewnętrznej pętli for 
 10      EXIT
 11  end

Sortowanie przez wybór (SelectionSort)

Na sortowanie bąbelkowe można spojrzeć jeszcze inaczej. W każdej fazie przepychamy na pierwsze miejsce w nieuporządkowanej części tablicy element najmniejszy. Symetrycznie moglibyśmy sortować poczynając od elementów nawiększych. W sortowaniu przez wybór nie przepychamy elementu największego (najmniejszego) na jego miejsce w ciągu uporządkowanym, tylko znajdujemy jego pozycję, a następnie znaleziony element - największy w części nieuporządkowanej - zamieniamy z elementem, który znajduje się na docelowej pozycji elementu największego. Niech $Max(i)$ będzie funkcją, której wartością jest pozycja największego elementu w podtablicy $a[1..i]$ . Oto schemat algorytmu sortowania przez wybór:

Algorytm Schemat algorytmu sortowania przez wybór

 schemat SelectionSort 
 1  for  $i:=n$  downto  $2$  do
 2  begin
 3     $j:=Max(i)$ ;
 4     $Exchange(i,j)$ 
 5  end;

Dlaczego użyliśmy słowa schemat? Zauważmy, że do pełnego zdefinowania algorytmu, a także dla jego analizy, niezbędne jest zdefiniowanie funkcji $Max$ . W klasycznym sortowaniu przez wybór pozycję elementu największego w podtablicy $a[1..i]$ wyznaczamy przeszukując podtablicę od lewej do prawej, pamiętając w zmiennej pomocniczej pozycję dotychczas największego elementu i modyfikując wartość tej zmiennej każdorazowo po napotkaniu elementu większego od dotychczas największego. Oto pełny zapis algorytmu sortowania przez wybór - algorytmu SelectionSort.

Algorytm Sortowanie przez wybór

 SelectionSort
 1  for  $i:=n$  downto  $2$  do
 2  begin
 3     $j:=1$ ;
 4    for  $k:=2$  to  $i$  do
 5      if  $a[k]>a[j]$  then  $j:=k$ ;
 6     $Exchange(i,j)$ 
 7  end;

Nietrudno zauważyć, że algorytm SelectionSort wykonuje taką samą liczbę porównań, co algorytm bąbelkowy. Jednak w tym przypadku maksymalna liczba zamian wynosi tylko $n-1$ . Poniższa animacja ilustruje działanie algorytmu SelectionSort.

<applet code="SortItem" archive="images/a/a5/Sort2.jar" width="300" height="300"> alg=SelectionSort delay=1000 </applet>

Należy podkreślić, że w implementacji schematu sortowania przez wybór mamy swobodę w realizacji funkcji $Max$ . Wykorzystamy to w algorytmie sortowania z użyciem struktury danych zwanej kopcem.

Sortowanie przez wstawianie

Sortowanie przez wstawianie jest algorytmem szczególnie polecanym do sortowania krótkich ciągów. Jego złożoność pesymistyczna jest asymptotycznie taka sama jak dwóch poprzednich algorytmów, ale zachowuje się on znacznie lepiej dla ciągów "prawie" posortowanych. Co znaczy "prawie" wyjaśnimy w dalszej części wykładu.

Idea sortowania przez wstawianie jest następująca. Sortujemy w $n-1$ fazach, ponumerowanych dla wygody opisu od 2 do $n$ . Przed rozpoczęciem $i$ -tej fazy wiemy, że podtablica $a[1..i-1]$ jest już posortowana. Naszym celem jest uporządkowanie podtablicy $a[1..i]$ , co w rzeczywistości oznacza wstawienie na właściwe miejsce elementu $a[i]$ w uporządkowany ciąg $a[1..i-1]$ . W tym celu odkładamy element z pozycji $a[i]$ na bok (zapamiętujemy w pomocniczej zmiennej), a następnie przeglądamy elementy podtablicy $a[1..i-1]$ od prawej do lewej, przesuwając każdy element większy od odłożonego o jedną pozycję w prawo. Po napotkaniu w tablicy $a$ elementu nie większego od elementu odłożonego (nazwijmy go elementem blokującym), element odłożony wstawiany tuż przed element blokujący. Oto zapis sortowania przez wstawianie - algorytm InsertionSort.

Algorytm Sortowanie przez wstawianie

 InsertionSort
 1  for  $i:=2$  to  $n$  do
 2  begin
 3    // $a[1..i-1]$  jest już posortowana
 4     $x:=a[i]$ ; //odkładamy element z pozycji  $i$ 
 5     $j:=i$ ;
 6    while  $x<a[j-1]$  do
 7    begin
 8       $a[j]:=a[j-1]$ ; //przesuwamy element większy od  $x$  o jedną pozycję w prawo    
 9       $j:=j-1$ 
 10   end;
 11     $a[j]:=x$ 
 12 end;

Poniższa animacja ilustruje działanie sortowania przez wstawianie.

<applet code="SortItem" archive="images/e/ef/Sort.jar" width="300" height="300"> alg=InsertionSort delay=1000 </applet>

Dokonamy teraz wspólnie analizy przedstawionego algorytmu. W tym celu postaraj się drogi czytelniku samodzielnie wykonać następujące ćwiczenia.

Ćwiczenie 2

Jakie znaczenie dla poprawności algorytmu InsertionSort ma założenie z początku wykładu o tym, że $a[0]\leq a[i]$ , dla każdego $i=1,2,...,n$ ?

Odpowiedź do ćwiczenia 2

Pętla "while" kończy się poprawnie w przypadku, gdy $x$ jest mniejsze od wszystkich elementów z $a[1..i-1]$ .

Ćwiczenie 3

Załóżmy, że sortujemy permutację liczb $1,2,\ldots ,n$ . Podaj permutacje, dla których algorytm InsertionSort wykona odpowiednio najwięcej i najmniej porównań, a następnie wyznacz dokładne liczby porównań w najgorszym i najlepszym przypadku. Uwaga: pamiętaj o porównaniach z $a[0]$ .

Odpowiedź do ćwiczenia 3

Najwięcej porównań zostanie wykonanych dla ciągu $n,n-1,\ldots ,1$ . Liczba porównań w tym przypadku wynosi

2+3+\ldots +n={\frac {(n+2)(n-1)}{2}}

.

Najmniej porównań zostanie wykonanych dla permutacji $1,2,\ldots ,n$ - dokładnie $n-1$ .

Zastanówmy się, od czego zależy liczba porównań wykonywanych przez algorytm InsertionSort dla ustalonej permutacji $\pi =<p_{1},p_{2},\ldots ,p_{n}>$ . W tym celu zdefiniujmy pojęcie inwersji w permutacji. Inwersją w permutacji $\pi$ nazywamy każdą parę indeksów $1\leq i<j\leq$ takich, że $p_{i}>p_{j}$ .

Ćwiczenie 4

Zastanów się, jaka jest zależność pomiędzy liczbą porównań wykonywanych przez algorytm InsertionSort dla permutacji $\pi$ a liczbą inwersji w tej permutacji.

Odpowiedź do ćwiczenia 4

Niech $Inv(\pi )$ będzie liczbą inwersji w $\pi$ . Liczba porównań wykonywana przez InsertionSort dla $\pi$ wynosi $Inv(\pi )+n-1$ .

Jedną z miar uporządkowania ciągu elementów jest liczba inwersji w nim występujących. Permutacja rosnąca nie zawiera wcale inwersji, natomiast permutacja malejąca zawiera ${n(n-1)}/{2}$ inwersji. Na podstawie ćwiczenia 4 wnioskujemy, że jeżeli ciąg wejściowy zawiera liniową ze względu na $n$ liczbę inwersji, to dla takiego ciągu algorytm InsertionSort działa w czasie liniowym. Jeżeli jednak w ciągu wejściowym jest kwadratowa liczba inwersji, to algorytm InsertionSort działa w czasie kwadratowym. Może jednak takie dane są niesłychanie rzadkie, a dla "przeciętnych" danych algorytm InsertionSort zachowuje się zdecydowanie lepiej? Niestety, to nie jest prawda. Żeby to wykazać, obliczymy oczekiwaną liczbę porównań wykonywanych przez nasz algorytm dla "losowych" danych. Pisząc "losowych", musimy precyzyjnie określić, co mamy na myśli. Dla naszych rozważań przyjmiemy model losowej permutacji, w którym to zakłada się, że początkową zawartością sortowanej tablicy $a$ jest permutacja liczb $1,2,\ldots ,n$ i każda z $n!$ permutacji może pojawić się z tym samym prawdopodobieństwem ${\frac {1}{n!}}$ . Jeśli już ustaliliśmy model probabilistyczny, to możemy określić średnią liczbę porównań wykonywanych przez algorytm InsertionSort. Nietrudno zauważyć, że wynosi ona

n-1+{\frac {1}{n!}}\sum _{\{\pi :{\mbox{ permutacja liczb }}1,2,\ldots ,n\}}Inv(\pi )

.

W powyższym wzorze wartość wyrażenia ${\frac {1}{n!}}\sum _{\{\pi :{\mbox{ permutacja liczb }}1,2,\ldots ,n\}}Inv(\pi )$ jest równa oczekiwanej liczbie inwersji w losowej permutacji. Żeby policzyć oczekiwaną liczbę porównań wykonywaną przez algorytm InsertionSort, wystarczy więc wyznaczyć oczekiwaną liczbę inwersji w losowej permutacji.

Wektorem inwersji dla permutacji $\pi$ nazywamy ciąg liczb $w=[w_{1},w_{2},\ldots ,w_{n}]$ taki, że $w_{i}=|\{j:1\leq j<i{\mbox{ oraz }}p_{j}>p_{i}\}|$ , dla każdego $i=1,2,\ldots ,n$ . Innymi słowy, $w_{i}$ jest liczbą tych elementów permutacji $\pi$ , która znajdują się na lewo od elementu $p_{i}$ i są od niego większe.

Ćwiczenie 5

Podaj wektor inwersji dla permutacji $\pi =[7,8,2,4,6,1,5,3]$ .

Odpowiedź do ćwiczenia 5

$w=[0,0,2,2,2,5,3,5]$ .

Nietrudno jest pokazać, że dwóm różnym permutacjom odpowiadają różne wektory inwersji. __

Niech $\pi ',\pi ''$ będą różnymi $n$ -elementowymi permutacjami i niech $w',w''$ będą odpwiednio wektorami inwersji dla tych permutacji. Niech $i$ będzie największym takim indeksem, że $\pi '_{i}\neq \pi ''_{i}$ . Bez straty ogólności możemy przyjąć, że $\pi '_{i}<\pi ''_{i}$ . Wówczas $w'_{i}>w''_{i}$ . Dlaczego?

Zauważmy, że elementy każdego wektora inwersji $w$ muszą spełniać nierówności $0\leq w_{i}<i$ , dla $i=1,2,\ldots ,n$ . Oznaczmy zbiór wszystkich $n$ -elementowych wektorów o takich własnościach przez $W_{n}$ . Liczba elementów zbioru $W_{n}$ wynosi $n!$ . Z naszych dotychczasowych rozważań wynika, że istnieje wzajemnie jednoznaczna odpowiedniość pomiędzy permutacjami liczb $1,2,\ldots ,n$ , a wektorami z $W_{n}$ . Dlatego elementy tego zbioru będziemy nazywali po prostu wektorami inwersji.

Ćwiczenie 6

Podaj permutację o wektorze inwersji $w=[0,0,1,1,2,1,4,5]$ .

Odpowiedź do ćwiczenia 6

$\pi =[1,8,2,6,5,7,4,3]$ .

Ćwiczenie 7

Zaproponuj algorytm, który dla danego wektora inwersji $w=[w_{1},w_{2},\ldots ,w_{n}]$ znajdzie odpowiadającą mu permutację.

Wskazówka do ćwiczenia 7

Odpowiedź do ćwiczenia 7

Załóżmy, że wektor inwersji jest dany w tablicy $w[1..n]$ . Permutację budujemy w tablicy $p[1..n]$ . Zbiór $Wolne\subset \{1,2,\ldots ,n\}$ zawiera te elementy permutacji, których pozycja jest jeszcze nieokreślona. Oto schemat algorytmu:

Algorytm Wektor inwersji --> permutacja

 1   $Wolne:=\{1,2,\ldots ,n\}$  
 2  for  $i:=n$  downto  $1$  do
 3  begin
 4     $k:=w[i]+1;$ 
 5    //W zbiorze  $Wolne$ ,  $i$ -ty element permutacji jest  $k$ -tym co do wartości, 
 6    //licząc od największego 
 7     $x:=k{\mbox{-ty co do wartości element w }}Wolne$ ;
 8     $Wolne:=Wolne-\{x\};$  //usuń  $x$  z  $Wolne$ 
 9     $p[i]:=x$   
 10 end;

Sumą wektora inwersji nazwiemy sumę jego elementów. Z dotychczasowych rozważań wynika, że suma wektora inwersji jest równa liczbie inwersji w odpowiadającej temu wektorowi permutacji. Losowy wektor inwersji można otrzymać losując każdy jego element niezależnie w ten sposób, że na pozycji $i$ -tej może pojawić się każda z wartości $0,1,\ldots ,i-1$ z jednakowym prawdopodobieństwem ${\frac {1}{i}}$ . Tak więc oczekiwana wartość $i$ -tego elementu w losowym wektorze inwersji wynosi ${\frac {0+1+\ldots +i-1}{i}}={\frac {i-1}{2}}$ . Z liniowości wartości oczekiwanej otrzymujemy, że oczekiwana suma losowego wektora inwersji wynosi $0+{\frac {1}{2}}+\ldots +{\frac {n-1}{2}}={\frac {n(n-1)}{4}}$ . Zatem taka jest też oczekiwana liczba inwersji w losowej permutacji. Wynika stąd, że algorytm sortowania przez wstawianie zachowuje się dla "przeciętnych" danych podobnie, jak dla danych "najgorszych" i działa w czasie kwadratowym.

@@ Linia 3: / Linia 3: @@
 == Definicja problemu ==
-Niech <math>(U,\le)</math> będzie zbiorem liniowo uporządkowanym z relacją porzadkującą <math>\le</math> i niech <math>c_1, c_2, \ldots, c_n</math> będzie ciągiem <math>n</math> elementów z <math>U</math>, dla pewnego całkowitego <math>n > 0</math>.
+Niech <math>(U,\le)</math> będzie zbiorem liniowo uporządkowanym z relacją porządkującą <math>\le</math> i niech <math>c_1, c_2, \ldots, c_n</math> będzie ciągiem <math>n</math> elementów z <math>U</math>, dla pewnego całkowitego <math>n > 0</math>.
 Należy znaleźć permutację <math>c_{i_1}, c_{i_2},\ldots,c_{i_n}</math> taką, że <math>c_{i_1}\le c_{i_2}\le \ldots \le c_{i_n}</math>.
@@ Linia 9: / Linia 9: @@
-W tym wykładzie przyjmujemy, że elementy ciągu <math>c</math> znajdują się w tablicy <math>a[1..n]</math>, tzn. <math>a[1] = c_1, a[2] = c_2, \ldots, a[n] = c_n</math>. Będziemy także chcieli, żeby posortowany ciąg <math> c </math> znajdował się nadal w tablicy <math>a</math>, tzn. wynikiem sortowania ma być <math>a[1] = c_{i_1} \le a[2] = c_{i_2} \le \ldots \le a[n] = c_{i_n}</math>. Dla wygody dalszych rozważań przyjmijmy, że tablica <math>a</math> jest indeksowana od <math>0</math> i że <math> a[0] </math> zawiera element, który nie jest większy od żadnego elementu z <math>a[1..n]</math>, tzn. dla każdego <math>i = 1,2, \ldots, n</math>, <math> a[0] \le a[i]</math>.
+W tym wykładzie przyjmujemy, że elementy ciągu <math>c</math> znajdują się w tablicy <math>a[1..n]</math>, tzn. <math>a[1] = c_1, a[2] = c_2, \ldots, a[n] = c_n</math>. Będziemy także chcieli, żeby posortowany ciąg <math>c</math> znajdował się nadal w tablicy <math>a</math>, tzn. wynikiem sortowania ma być <math>a[1] = c_{i_1} \le a[2] = c_{i_2} \le \ldots \le a[n] = c_{i_n}</math>. Dla wygody dalszych rozważań przyjmijmy, że tablica <math>a</math> jest indeksowana od <math>0</math>, i że <math>a[0]</math> zawiera element, który nie jest większy od żadnego elementu z <math>a[1..n]</math>, tzn. dla każdego <math>i = 1,2, \ldots, n</math>, <math>a[0] \le a[i]</math>.
-Zauważmy, że w tak sformułowanym problemie sortowania nic nie wiemy o naturze elementów z <math>U</math>. Na <math>U</math> mogą składać się zarówno liczby całkowite lub rzeczywiste, jak i <math>U</math> może być zbiorem rekordów, które należy posortować według ich kluczy. Jedynym sposobem ustalenie porządku w tablicy <math>a</math> jest porównywanie jej elementów parami. Operacja porówniania będzie operacją dominującą w naszych algorytmach. Ponieważ będziemy chcieli ustalić wynik także w tablicy <math>a</math>, to potrzebna nam jest jeszcze operacja zamiany dwóch elementów w tablicy. Tą operacją będzie operacja <math>Exchange(i,j)</math> polegająca na zamianie elementów w tablicy <math>a</math> z pozycji <math>i</math> oraz <math> j </math>, <math> 1\le i, j \le n</math>.
+Zauważmy, że w tak sformułowanym problemie sortowania nic nie wiemy o naturze elementów z <math>U</math>. Na <math>U</math> mogą składać się zarówno liczby całkowite lub rzeczywiste, jak i <math>U</math> może być zbiorem rekordów, które należy posortować według ich kluczy. Jedynym sposobem ustalenie porządku w tablicy <math>a</math> jest porównywanie jej elementów parami. Operacja porównania będzie operacją dominującą w naszych algorytmach. Ponieważ będziemy chcieli ustalić wynik także w tablicy <math>a</math>, potrzebna nam jest jeszcze operacja zamiany dwóch elementów w tablicy. Operacją tą będzie operacja <math>Exchange(i,j)</math> polegająca na zamianie elementów w tablicy <math>a</math> z pozycji <math>i</math> oraz <math>j</math>, <math>1\le i, j \le n</math>.
 ==Sortowanie bąbelkowe (BubbleSort)==
-Jest to jeden z najprostszych algorytmów sortowania. Sortowanie bąbelkowe jest wykonywane w <math> n-1 </math> fazach. W fazie <math>i</math>-tej wyznaczany jest element <math>i</math>-ty co do wielkości. Załóżmy, że po <math>i-1</math> pierwszych fazach mamy wyznaczone i uporządkowane <math>i-1</math> najmniejsze elementy, tzn. <math>a[1]\le a[2]\le \ldots a[i-1]</math> i dla każdego <math>k = i, i+1, \ldots, n</math>, mamy <math>a[i-1] \le a[k]</math>. W fazie <math>i</math>-tej porównywane są kolejno elementy w parach <math>(a[n], a[n-1])</math>, <math>(a[n-1], a[n-2])</math>, ..., <math>(a[i+1], a[i])</math>. Jeżeli elementy w parze nie są uporządkowane, to dokonujemy ich zamiany. Oto algorytm sortowania bąbelkowego.
+Jest to jeden z najprostszych algorytmów sortowania. Sortowanie bąbelkowe jest wykonywane w <math>n-1</math> fazach. W fazie <math>i</math>-tej wyznaczany jest <math>i</math>-ty najmniejszy element. Załóżmy, że po <math>i-1</math> pierwszych fazach mamy wyznaczone i uporządkowane <math>i-1</math> najmniejsze elementy, tzn. <math>a[1]\le a[2]\le \ldots a[i-1]</math> i dla każdego <math>k = i, i+1, \ldots, n</math> mamy <math>a[i-1] \le a[k]</math>. W fazie <math>i</math>-tej porównywane są kolejno elementy w parach <math>(a[n], a[n-1])</math>, <math>(a[n-1], a[n-2])</math>, ..., <math>(a[i+1], a[i])</math>. Jeżeli elementy w parze nie są uporządkowane, dokonujemy ich zamiany. Oto algorytm sortowania bąbelkowego.
 {{algorytm|Sortowanie bąbelkowe|algorytm_sortowanie_bąbelkowe|
    BubbleSort
   '''for''' <math>i:=1</math> '''to''' <math>n-1</math> '''do'''
-    '''for''' <math> j:=n </math>  '''downto''' <math> i+1 </math> '''do'''
+    '''for''' <math>j:=n</math>  '''downto''' <math>i+1</math> '''do'''
-    '''if''' <math>a[j-1] > a[j] </math> '''then'''
+    '''if''' <math>a[j-1] > a[j]</math> '''then'''
       <math>Exchange(j-1,j)</math>;
 }}
@@ Linia 27: / Linia 27: @@
 Poniżej zilustrowano działanie sortowania bąbelkowego.
-<applet code="SortItem" archive="images/e/ef/Sort.jar" width="300" height="300">
+<applet code="SortItem" archive="images/a/a5/Sort2.jar" width="300" height="300">
 alg=BubbleSort
 delay=1000
@@ Linia 35: / Linia 35: @@
 ----
-Zaletą sortowania bąbelkowego jest jego prostota i bardzo krótki kod. Niestety jego główną wadą jest to, że zawsze, niezależnie od danych, wykonuje tyle samo porównań: <math>n-1</math> w pierwszej fazie, <math>n-2</math> w drugiej, ..., <math> 1 </math> w fazie ostatniej, co daje łącznie <math>\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2}</math>
+Zaletą sortowania bąbelkowego jest jego prostota i bardzo krótki kod. Niestety jego główną wadą jest to, że zawsze, niezależnie od danych, wykonuje tyle samo porównań: <math>n-1</math> w pierwszej fazie, <math>n-2</math> w drugiej, ..., <math>1</math> w fazie ostatniej, co daje łącznie <math>\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2}</math>
-porównań. Liczba zamian może się zmieniać od <math>0</math> do <math>\frac{n(n-1)}{2}.</math> Zauważmy, że tak zapisany algorytm sortowania bąbelkowego zawsze wykonuje <math>n-1</math> faz, nawet wtedy, gdy ciąg wejściowy jest już uporządkowany. Celem ćwiczenia 1 będzie taka modyfikacja algorytmu, aby zakończyć jego działanie, jeśli tylko zostanie stwierdzone, że tablica <math>a</math> jest już uporządkowana.
+porównań. Liczba zamian może się zmieniać od <math>0</math> do <math>\frac{n(n-1)}{2}</math>. Zauważmy, że tak zapisany algorytm sortowania bąbelkowego zawsze wykonuje <math>n-1</math> faz, nawet wtedy, gdy ciąg wejściowy jest już uporządkowany. Celem ćwiczenia 1 jest taka modyfikacja algorytmu, aby zakończyć jego działanie, kiedy tylko zostanie stwierdzone, że tablica <math>a</math> jest już uporządkowana.
 ----
@@ Linia 51: / Linia 51: @@
   '''for''' <math>i:=1</math> '''to''' <math>n-1</math> '''do'''
   '''begin'''
-    <math> posortowana := </math> TRUE;
+    <math>posortowana :=</math> TRUE;
-    '''for''' <math> j:=n </math>  '''downto''' <math> i+1 </math> '''do'''
+    '''for''' <math>j:=n</math>  '''downto''' <math>i+1</math> '''do'''
-    '''if''' <math>a[j-1] > a[j] </math> '''then'''
+    '''if''' <math>a[j-1] > a[j]</math> '''then'''
-      '''begin''' <math>exchange(j-1,j)</math>; <math>posortowana := </math> FALSE '''end''';
+      '''begin''' <math>exchange(j-1,j)</math>; <math>posortowana :=</math> FALSE '''end''';
     '''if''' <math>posortowana</math> '''then'''
     //nie wykonano żadnych zamian;
@@ Linia 73: / Linia 73: @@
   '''begin'''
     <math>j := Max(i)</math>;
-    <math> Exchange(i,j)</math>
+    <math>Exchange(i,j)</math>
   '''end''';
 }}
@@ Linia 88: / Linia 88: @@
 }}
-Nietrudno zauważyć, że algorytm SelectionSort wykonuje taką zamą liczbę porównań, co algorytm bąbelkowy. Jednak w tym przypadku maksymalna liczba zamian wynosi tylko <math>n-1</math>. Poniższa animacja ilustruje działanie algorytmu SelectionSort.
+Nietrudno zauważyć, że algorytm SelectionSort wykonuje taką samą liczbę porównań, co algorytm bąbelkowy. Jednak w tym przypadku maksymalna liczba zamian wynosi tylko <math>n-1</math>. Poniższa animacja ilustruje działanie algorytmu SelectionSort.
-<applet code="SortItem" archive="images/e/ef/Sort.jar" width="300" height="300">
+<applet code="SortItem" archive="images/a/a5/Sort2.jar" width="300" height="300">
 alg=SelectionSort
 delay=1000
@@ Linia 131: / Linia 131: @@
 ----
-Dokonamy teraz wspólnie analizy przedstawionego algorytmu. W tym celu postaraj się '''drogi czytelniku''' samodzielnie wykonać następujące ćwiczenia.
+Dokonamy teraz wspólnie analizy przedstawionego algorytmu. W tym celu postaraj się drogi czytelniku samodzielnie wykonać następujące ćwiczenia.
 ----
@@ Linia 137: / Linia 137: @@
 '''Ćwiczenie 2'''
-Jakie znaczenie dla poprawności algorytmu InsertionSort ma założenie z początku wykładu o tym, że <math>a[0] \le a[i]</math>, dla każdego <math> i = 1, 2, ..., n </math>?
+Jakie znaczenie dla poprawności algorytmu InsertionSort ma założenie z początku wykładu o tym, że <math>a[0] \le a[i]</math>, dla każdego <math>i = 1, 2, ..., n</math>?
 <div class="mw-collapsible mw-made=collapsible mw-collapsed">
@@ Linia 148: / Linia 148: @@
 '''Ćwiczenie 3'''
-Załóżmy, że sortujemy permutację liczb <math>1, 2, \ldots, n</math>. Podaj permutacje, dla których algorytm InsertionSort wykona odpowiednio najwięcej i najmniej porównań, a następnie wyznacz dokładne liczby porównań w najgorszym i najlepszym przypadku. Uwaga: pamiętaj o porównaniach z <math>a[0] </math>.
+Załóżmy, że sortujemy permutację liczb <math>1, 2, \ldots, n</math>. Podaj permutacje, dla których algorytm InsertionSort wykona odpowiednio najwięcej i najmniej porównań, a następnie wyznacz dokładne liczby porównań w najgorszym i najlepszym przypadku. Uwaga: pamiętaj o porównaniach z <math>a[0]</math>.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed">
 '''Odpowiedź do ćwiczenia 3'''
 <div class="mw-collapsible-content" style="display:none">
-Najwięcej porównań zostanie wykonanych dla ciągu <math> n, n-1, \ldots, 1</math>. Liczba porównań w tym przypadku wynosi
+Najwięcej porównań zostanie wykonanych dla ciągu <math>n, n-1, \ldots, 1</math>. Liczba porównań w tym przypadku wynosi
 <center><math>2 + 3 + \ldots + n = \frac{(n+2)(n-1)}{2}</math>.</center>
 Najmniej porównań zostanie wykonanych dla permutacji <math>1,2, \ldots, n</math> - dokładnie <math>n-1</math>.
@@ Linia 159: / Linia 159: @@
 </div>
-Zastanówmy się od czego zależy liczba porównań wykonywanych przez algorytm InsertionSort dla ustalonej permutacji <math>\pi = <p_1, p_2, \ldots, p_n> </math>. W tym celu zdefiniujmy pojęcie inwersji w permutacji.
+Zastanówmy się, od czego zależy liczba porównań wykonywanych przez algorytm InsertionSort dla ustalonej permutacji <math>\pi = <p_1, p_2, \ldots, p_n></math>. W tym celu zdefiniujmy pojęcie inwersji w permutacji.
-'''Inwersją''' w permutacji <math>\pi</math> nazywamy każdą parę indeksów <math>1\le i < j \le </math> takich, że <math>p_i > p_j</math>.
+'''Inwersją''' w permutacji <math>\pi</math> nazywamy każdą parę indeksów <math>1\le i < j \le</math> takich, że <math>p_i > p_j</math>.
 '''Ćwiczenie 4'''
-Zastanów się, jaka jest zależność pomiędzy liczbą porównań wykonywanych przez algorytm InsertionSort dla permutacji <math>\pi </math>, a liczbą inwersji w tej permutacji.
+Zastanów się, jaka jest zależność pomiędzy liczbą porównań wykonywanych przez algorytm InsertionSort dla permutacji <math>\pi</math> a liczbą inwersji w tej permutacji.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed">
 '''Odpowiedź do ćwiczenia 4'''
 <div class="mw-collapsible-content" style="display:none">
-Niech <math>Inv(\pi)</math> będzie liczbą inwersji w <math>\pi </math>. Liczba porównań wykonywana przez InsertionSort dla <math>\pi </math> wynosi <math>Inv(\pi) + n-1</math>.
+Niech <math>Inv(\pi)</math> będzie liczbą inwersji w <math>\pi</math>. Liczba porównań wykonywana przez InsertionSort dla <math>\pi</math> wynosi <math>Inv(\pi) + n-1</math>.
 </div>
 </div>
-Jedną z miar uporządkowania ciągu elementów jest liczba inwersji w nim występujących. Permutacja rosnąca nie zawiera wcale inwersji, natomiast permutacja malejąca zawiera <math>\frav{n(n-1)}/{2}</math> inwersji. Na podstawie ćwiczenia 4 wnioskujemy, że jeżeli ciąg wejściowy zawiera liniową ze względu na <math> n </math> liczbę inwersji, to dla takiego ciągu algorytm InsertionSort działa w czasie liniowym. Jeżeli jednak w ciągu wejściowym jest kwadratowa liczba inwersji, to algorytm InsertionSort działa w czasie kwadratowym. Może jednak takie dane są niesłychanie rzadkie, a dla "przeciętnych" danych algorytm InsertionSort zachowuje się zdecydowanie lepiej. Niestety to nie jest prawda. Żeby to wykazać policzymy oczekiwaną liczbę porównań wykonywanych przez nasz algorytm dla "losowych" danych. Pisząc "losowych" musimy precyzyjnie okreslić, co mamy na myśli. Dla naszych rozważań przyjmiemy '''model losowej permutacji''', w którym to zakłada się, że początkową zawartością sortowanej tablicy <math>a</math> jest permutacja liczb <math>1, 2,\ldts, n</math> i każda z <math>n!</math> permutacji może pojawić się z tym samym prawdopodobieństwem <math>\frac{1}{n!}</math>. Jeśli już ustaliliśmy model probabilistyczny, to możemy określić średnią liczbę porównań wykonywanych przez algorytm InsertionSort. Nietrudno zauważyć, że wynosi ona
+Jedną z miar uporządkowania ciągu elementów jest liczba inwersji w nim występujących. Permutacja rosnąca nie zawiera wcale inwersji, natomiast permutacja malejąca zawiera <math>{n(n-1)}/{2}</math> inwersji. Na podstawie ćwiczenia 4 wnioskujemy, że jeżeli ciąg wejściowy zawiera liniową ze względu na <math>n</math> liczbę inwersji, to dla takiego ciągu algorytm InsertionSort działa w czasie liniowym. Jeżeli jednak w ciągu wejściowym jest kwadratowa liczba inwersji, to algorytm InsertionSort działa w czasie kwadratowym. Może jednak takie dane są niesłychanie rzadkie, a dla "przeciętnych" danych algorytm InsertionSort zachowuje się zdecydowanie lepiej? Niestety, to nie jest prawda. Żeby to wykazać, obliczymy oczekiwaną liczbę porównań wykonywanych przez nasz algorytm dla "losowych" danych. Pisząc "losowych", musimy precyzyjnie określić, co mamy na myśli. Dla naszych rozważań przyjmiemy '''model losowej permutacji''', w którym to zakłada się, że początkową zawartością sortowanej tablicy <math>a</math> jest permutacja liczb <math>1, 2,\ldots, n</math> i każda z <math>n!</math> permutacji może pojawić się z tym samym prawdopodobieństwem <math>\frac{1}{n!}</math>. Jeśli już ustaliliśmy model probabilistyczny, to możemy określić średnią liczbę porównań wykonywanych przez algorytm InsertionSort. Nietrudno zauważyć, że wynosi ona
 ----
-<center><math> n-1 + \frac{1}{n!}\sum_{\{\pi: \mbox{ permutacja liczb } 1,2, \ldots, n\}}Inv(\pi).</math></center>
+<center><math>n-1 + \frac{1}{n!}\sum_{\{\pi: \mbox{ permutacja liczb } 1,2, \ldots, n\}}Inv(\pi)</math>.</center>
 ----
-W powyższym wzorze wartość wyrażenia <math>\frac{1}{n!}\sum_{\{\pi: \mbox{ permutacja liczb } 1,2, \ldots, n\}}Inv(\pi)</math> jest równa oczekiwanej liczbie inwersji w losowej permutacji. Tak więc, żeby policzyć oczekiwaną liczbę porównań wykonywaną przez algorytm InsertionSort, wystarczy wyznaczyć oczekiwaną liczbę inwersji w losowej permutacji.
+W powyższym wzorze wartość wyrażenia <math>\frac{1}{n!}\sum_{\{\pi: \mbox{ permutacja liczb } 1,2, \ldots, n\}}Inv(\pi)</math> jest równa oczekiwanej liczbie inwersji w losowej permutacji. Żeby policzyć oczekiwaną liczbę porównań wykonywaną przez algorytm InsertionSort, wystarczy więc wyznaczyć oczekiwaną liczbę inwersji w losowej permutacji.
-'''Wektorem inwersji''' dla permutacji <math>\pi</math> nazywamy ciąg liczb <math>w = [w_1, w_2, \ldots, w_n] </math> taki, że <math>w_i = |\{j: 1 \le j < i \mbox{ oraz } p_j > p_i \}|</math>, dla każdego <math>i = 1,2, \ldots, n</math>. Innymi słowy, <math>w_i</math> jest liczbą tych elementów permutacji <math>\pi</math>, która znajdują się na lewo od elementu <math>\p_i</math> i są od niego większe.
+'''Wektorem inwersji''' dla permutacji <math>\pi</math> nazywamy ciąg liczb <math>w = [w_1, w_2, \ldots, w_n]</math> taki, że <math>w_i = |\{j: 1 \le j < i \mbox{ oraz } p_j > p_i \}|</math>, dla każdego <math>i = 1,2, \ldots, n</math>. Innymi słowy, <math>w_i</math> jest liczbą tych elementów permutacji <math>\pi</math>, która znajdują się na lewo od elementu <math>p_i</math> i są od niego większe.
 '''Ćwiczenie 5'''
@@ Linia 200: / Linia 200: @@
 Nietrudno jest pokazać, że dwóm różnym permutacjom odpowiadają różne wektory inwersji. __
 <div class="mw-collapsible-content" style="display:none">
-Niech <math>\pi', \pi"</math> będą różnymi <math>n</math>-elementowymi permutacjami i niech <math>w', w"</math> będą odpwiednio wektorami inwersji dla tych permutacji. Niech <math>i</math> będzie największym takim indeksem, że <math>\pi'_i \ne \pi"_i</math>. Bez straty ogólności możemy przyjąć, że <math>\pi'_i < \pi"_i</math>. Wówczas <math>w'_i > w"_i</math>. Dlaczego?
+Niech <math>\pi', \pi''</math> będą różnymi <math>n</math>-elementowymi permutacjami i niech <math>w', w''</math> będą odpwiednio wektorami inwersji dla tych permutacji. Niech <math>i</math> będzie największym takim indeksem, że <math>\pi'_i \ne \pi''_i</math>. Bez straty ogólności możemy przyjąć, że <math>\pi'_i < \pi''_i</math>. Wówczas <math>w'_i > w''_i</math>. Dlaczego?
 </div>
 </div>
-Zauważmy, że elementy każdego wektora inwersji <math>w</math> muszą spełniać nierówności <math>0 \le w_i < i</math>, dla <math>i=1, 2, \ldots, n</math>. Oznaczmy zbiór wszystkich <math>n</math>-elementowych wektorów o takich własnościach przez <math>\calc{W}_n</math>. Liczba elementów zbioru <math>\calc{W}_n</math> wynosi <math>n!</math>. Z naszych dotychczasowych rozważań wynika, że istnieje wzajemnie jednoznaczna odpowiedniość pomiędzy permutacjami liczb <math>1,2,\ldots, n</math>, a wektorami z   <math>\calc{W}_n</math>. Dlatego elementy tego zbioru będziemy nazywali po prostu wektorami inwersji.
+Zauważmy, że elementy każdego wektora inwersji <math>w</math> muszą spełniać nierówności <math>0 \le w_i < i</math>, dla <math>i=1, 2, \ldots, n</math>. Oznaczmy zbiór wszystkich <math>n</math>-elementowych wektorów o takich własnościach przez <math>W_n</math>. Liczba elementów zbioru <math>W_n</math> wynosi <math>n!</math>. Z naszych dotychczasowych rozważań wynika, że istnieje wzajemnie jednoznaczna odpowiedniość pomiędzy permutacjami liczb <math>1,2,\ldots, n</math>, a wektorami z   <math>W_n</math>. Dlatego elementy tego zbioru będziemy nazywali po prostu wektorami inwersji.
 '''Ćwiczenie 6'''
@@ Linia 224: / Linia 224: @@
 '''Wskazówka do ćwiczenia 7'''
 <div class="mw-collapsible-content" style="display:none">
-Należy budować permutację od końca, wyznaczjąc najpierw jej ostatni element, potem przedostatni, a na końcu element pierwszy.
+Należy budować permutację od końca, wyznaczając najpierw jej ostatni element, potem przedostatni, a na końcu element pierwszy.
 </div>
 </div>
@@ Linia 241: / Linia 241: @@
     //W zbiorze <math>Wolne</math>, <math>i</math>-ty element permutacji jest <math>k</math>-tym co do wartości,
     //licząc od największego
-    <math> x := k\mbox{-ty co do wartości element w } Wolne </math>;
+    <math>x := k\mbox{-ty co do wartości element w } Wolne</math>;
-    <math> Wolne := Wolne - \{x\};</math> //usuń <math>x</math> z <math>Wolne</math>
+    <math>Wolne := Wolne - \{x\};</math> //usuń <math>x</math> z <math>Wolne</math>
-    <math> p[i] := x</math>
+    <math>p[i] := x</math>
 '''end''';
 }}
@@ Linia 249: / Linia 249: @@
 </div>
-'''Sumą''' wektora inwersji nazwiemy sumę jego elementów. Z dotychczasowych rozważań wynika, że suma wektora inwersji jest równa liczbie inwersji w odpowiadającej temu wektorowi permutacji. Losowy wektor inwersji można otrzymać losując każdy jego element niezależnie w ten sposób, że na pozycji <math>i</math>-tej może pojawić się każda z wartości <math>0, 1, \ldots, i-1</math> z jednakowym prawdopodobieństwem <math>\frac{1}{i}</math>. Tak więc oczekiwana wartość <math>i</math>-tego elementu w losowym wektorze inwersji wynosi <math>\frac{0+1+\ldots+i-1}{i} = \frac{i-1}{2}</math>. Z liniowości wartości oczekiwanej otrzymujemy, że oczekiwana suma losowego wektora inwersji wynosi <math>0+\frac{1}{2}+\ldost + \frac{n-1}{2} = \frac{n(n-1)}{4} </math>. Zatem taka jest też oczekiwana liczba inwersji w losowej permutacji. Wynika stąd, że algorytm sortowania przez wstawianie zachowuje się dla "przeciętnych" danych podobnie jak dla danych "najgorszych" i działa w czasie kwadratowym.
+'''Sumą''' wektora inwersji nazwiemy sumę jego elementów. Z dotychczasowych rozważań wynika, że suma wektora inwersji jest równa liczbie inwersji w odpowiadającej temu wektorowi permutacji. Losowy wektor inwersji można otrzymać losując każdy jego element niezależnie w ten sposób, że na pozycji <math>i</math>-tej może pojawić się każda z wartości <math>0, 1, \ldots, i-1</math> z jednakowym prawdopodobieństwem <math>\frac{1}{i}</math>. Tak więc oczekiwana wartość <math>i</math>-tego elementu w losowym wektorze inwersji wynosi <math>\frac{0+1+\ldots+i-1}{i} = \frac{i-1}{2}</math>. Z liniowości wartości oczekiwanej otrzymujemy, że oczekiwana suma losowego wektora inwersji wynosi <math>0+\frac{1}{2}+\ldots + \frac{n-1}{2} = \frac{n(n-1)}{4}</math>. Zatem taka jest też oczekiwana liczba inwersji w losowej permutacji. Wynika stąd, że algorytm sortowania przez wstawianie zachowuje się dla "przeciętnych" danych podobnie, jak dla danych "najgorszych" i działa w czasie kwadratowym.

Algorytmy i struktury danych/Sortowanie - BubbleSort, SelectionSort, InsertionSort: Różnice pomiędzy wersjami

Aktualna wersja na dzień 10:28, 5 wrz 2023

Spis treści

Definicja problemu

Sortowanie bąbelkowe (BubbleSort)

Sortowanie przez wybór (SelectionSort)

Sortowanie przez wstawianie

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia