sortowania przez wstawianie i selekcję_29.11.2010.pdf

(142 KB) Pobierz

Microsoft Word - sortowania.doc

Sortowanie przez wstawianie:

Algorytm sortowania przez wstawianie naleŇy do klasy złoŇonoĻci obliczeniowej O(n 2 ) .

Przykład

9

5

6

3

1

Obieg

Zbiór

Opis wykonywanych operacji

1

Na koıcu zbioru tworzymy tzw. listħ uporzĢdkowanych elementów.

PoczĢtkowo lista ta zawiera tylko jeden, ostatni element zbioru.

9 5 6 3 1

3

9 5 6 1

Ze zbioru wyciĢgamy element leŇĢcy bezpoĻrednio przed listĢ

uporzĢdkowanĢ. Tutaj jest to liczba 3. Zajmowane przez niĢ

miejsce w zbiorze staje siħ wolne.

3

9 5 6 1

WyciĢgniħty element porównujemy kolejno z elementami listy, aŇ

napotkamy jej koniec lub element wiħkszy lub równy.

3

9 5 6 1

PoniewaŇ element listy jest mniejszy od bieŇĢcego elementu,

przesuwamy go w zbiorze na zwolnione miejsce. Puste miejsce

przemieszcza siħ wg łĢb listy uporzĢdkowanej.

9 5 6 1 3

Na liĻcie uporzĢdkowanej nie ma wiħcej elementów do porównania.

Zatem element bieŇĢcy umieszczamy w zbiorze na wolnym miejscu.

Zwróę uwagħ, iŇ przemieĻcił siħ on w stosunku do swojej pozycji

pierwotnej, a na koıcu zbioru powstała dwuelementowa lista

uporzĢdkowana.

2

6

9 5 1 3

Kolejnym elementem do wstawienia bħdzie liczba 6, która znajduje

siħ na pozycji przed listĢ uporzĢdkowanĢ.

6

9 5 1 3

Porównujemy 6 z 1. Element listy jest mniejszy, zatem przesuwamy

go na wolne miejsce.

6

9 5 1 3

Porównujemy 6 z 3. Znów element listy jest mniejszy - przesuwamy

go na wolne miejsce.

6

9 5 1 3

Na liĻcie uporzĢdkowanej nie ma juŇ dalszych elementów do

porównania - 6 wstawiamy na wolne miejsce.

9 5 1 3 6

Lista uporzĢdkowana zawiera juŇ 3 elementy.

3

5

9 1 3 6

Wybieramy ze zbioru kolejny element do wstawienia. Teraz jest to

liczba 5.

5

9 1 3 6

Szukamy dla niego miejsca na liĻcie uporzĢdkowanej. Liczba 1 jest

mniejsza od 5, zatem przesuwamy jĢ na wolnĢ pozycjħ.

5

9 1 3 6

To samo z liczbĢ 3.

5

9 1 3 6

Wreszcie napotkaliĻmy na liĻcie element, który jest wiħkszy od

bieŇĢcego. W takim przypadku koıczymy przeglĢdanie listy i

element bieŇĢcy wstawiamy na wolne miejsce, przed liczbħ 6.

9 1 3 5 6

Lista uporzĢdkowana zawiera juŇ cztery elementy.

427581962.111.png

427581962.122.png

427581962.133.png

427581962.144.png

4

9

1 3 5 6

W zbiorze pozostała do wstawienia liczba 9. Szukamy kolejno jej

pozycji na liĻcie uporzĢdkowanej porównujĢc jĢ z elementami tej

listy.

9

1 3 5 6

Nie tutaj

9

1 3 5 6

Nie tutaj

9

1 3 5 6

Nie tutaj

9

1 3 5 6

Tutaj teŇ nie.

9

1 3 5 6

Cała lista została przeglĢdniħta. Zatem 9 wstawiamy na wolne

miejsce.

1 3 5 6 9

Koniec, zbiór jest uporzĢdkowany.

WykonaliĻmy 4 obiegi, w których było 10 porównaı i 9 przesuniħę elementów zbioru.

Schemat blokowy

427581962.001.png

427581962.012.png

427581962.023.png

427581962.034.png

427581962.045.png

427581962.056.png

427581962.067.png

427581962.068.png

427581962.069.png

427581962.070.png

427581962.071.png

427581962.072.png

427581962.073.png

427581962.074.png

427581962.075.png

427581962.076.png

427581962.077.png

427581962.078.png

427581962.079.png

427581962.080.png

427581962.081.png

427581962.082.png

427581962.083.png

427581962.084.png

427581962.085.png

427581962.086.png

427581962.087.png

427581962.088.png

427581962.089.png

427581962.090.png

427581962.091.png

427581962.092.png

427581962.093.png

427581962.094.png

427581962.095.png

427581962.096.png

427581962.097.png

427581962.098.png

427581962.099.png

427581962.100.png

427581962.101.png

427581962.102.png

427581962.103.png

427581962.104.png

427581962.105.png

427581962.106.png

427581962.107.png

427581962.108.png

427581962.109.png

427581962.110.png

427581962.112.png

427581962.113.png

427581962.114.png

427581962.115.png

427581962.116.png

427581962.117.png

427581962.118.png

427581962.119.png

427581962.120.png

427581962.121.png

427581962.123.png

427581962.124.png

427581962.125.png

427581962.126.png

427581962.127.png

427581962.128.png

427581962.129.png

427581962.130.png

427581962.131.png

D zbiór do posortowania

n liczba elementów w zbiorze D

i,j zmienne licznikowe pħtli

x zmienna pomocnicza przechowujĢca wybrany element

d i i-ty element zbioru D

f p ( ) funkcja porównujĢca dwa elementy zbioru D

PierwszĢ czynnoĻciĢ w algorytmie jest uzyskanie dostħpu do zbioru danych D , który naleŇy

posortowaę. Do zmiennej n wprowadzamy liczbħ elementów w tym zbiorze.

Sortowanie odbywa siħ w dwóch pħtlach - zewnħtrznej, która umieszcza wybrany element zbioru w

odpowiednim miejscu listy uporzĢdkowanej oraz wewnħtrznej, która znajduje pozycjħ na liĻcie

uporzĢdkowanej do wstawienia wybranego elementu. Pħtla zewnħtrzna jest typowĢ pħtlĢ iteracyjnĢ

FOR ze zmiennĢ licznikowĢ i , która zlicza obiegi wstecz od n -1 do 1. Pħtla wewnħtrzna jest typowĢ

pħtlĢ warunkowĢ WHILE .

Przed rozpoczħciem wykonywania pħtli zewnħtrznej do zmiennej i wprowadzamy numer

przedostatniego elementu zbioru, który jest indeksem elementu leŇĢcego bezpoĻrednio przed listĢ

uporzĢdkowanĢ.

W pħtli sprawdzamy warunek zakoıczenia. Zwróę uwagħ, iŇ pħtla ta nie wykona siħ ani razu, jeĻli na

poczĢtku i bħdzie równe lub mniejsze od 0. Taki przypadek moŇe wystĢpię, gdy zbiór D zawiera jeden

element - i = n - 1 = 0 - lub jest pusty i = n - 1 = -1. Zakoıczenie tej pħtli oznacza posortowanie zbioru

D .

W zmiennej x zapamiħtujemy i -ty element zbioru D . Jest to odpowiednik operacji wyjħcia elementu ze

zbioru. Nastħpnie rozpoczynamy pħtlħ wewnħtrznĢ, w której wybrany element bħdzie porównywany z

kolejnymi elementami na liĻcie uporzĢdkowanej. Indeks tych elementów przechowuje zmienna j , która

na poczĢtku pħtli wewnħtrznej przyjmuje wartoĻę o 1 wiħkszĢ od i . Ma to sens, poniewaŇ i wskazuje

zawsze element znajdujĢcy siħ bezpoĻrednio przed listĢ uporzĢdkowanĢ.

W pħtli wewnħtrznej wykonujemy dwa testy kontynuacji, które oba muszĢ byę spełnione, aby pħtla siħ

wykonywała. Pierwszy z nich sprawdza, czy zostały juŇ przeglĢdniħte wszystkie elementy na liĻcie

uporzĢdkowanej. Drugi sprawdza, czy wyjħty element jest w złej kolejnoĻci z aktualnie porównywanym

elementem na liĻcie. JeĻli oba testy dadzĢ wynik pozytywny, to przesuwamy aktualny element listy na

wolne miejsce i przesuwamy siħ do kolejnego elementu listy kontynuujĢc pħtlħ.

JeĻli którykolwiek z testów nie da wyniku pozytywnego, to pħtla zostanie przerwana. W takim

przypadku indeks j pomniejszony o 1 zawsze wskazuje na wolne miejsce w zbiorze D , gdzie

umieszczamy element wybrany przechowywany w zmiennej pomocniczej. Lista rozrasta siħ o 1 nowy

element. Zmniejszamy i o 1, aby wskazywało indeks nowego elementu przed listĢ uporzĢdkowanĢ i

kontynuujemy pħtlħ zewnħtrznĢ.

Sortowanie przez selekcj ħ

Algorytm sortowania przez selekcj ħ nale Ň y do klasy złoŇonoĻci obliczeniowej O(n 2 ) . .

Przykład

9

5

6

3

1

Zbiór

Opis wykonywanych operacji

Znajdujemy najmniejszy element w zbiorze. Jest nim liczba 1.

9 5 6 3 1

1 5 6 3 9

Element ten wymieniamy z pierwszym elementem zbioru. Element ten

jest juŇ na swojej właĻciwej pozycji. Za nowy zbiór przyjmujemy zbiór

bez pierwszego elementu

1 5 6 3 9

W nowym zbiorze znajdujemy najmniejszy element - liczbħ 3.

1 3 6 5 9

Znaleziony element wymieniamy z pierwszym elementem nowego

zbioru.

1 3 6 5 9

Znajdujemy najmniejszy element.

1 3 5 6 9

I wymieniamy go z pierwszym.

1 3 5 6 9

Znajdujemy najmniejszy element.

1 3 5 6 9

Wymieniamy z pierwszym elementem - element zostaje wymieniony z

samym sobĢ.

1 3 5 6 9

Pozostał zbiór jednoelementowy, a zatem elementy pierwotnego zbioru

zostały w całoĻci uporzĢdkowane.

Wyszukanie najmniejszego elementu w zbiorze

W podanym algorytmie wystħpuje problem znalezienia najmniejszego elementu w zbiorze według

zadanej funkcji porównujĢcej . Element najmniejszy zdefiniujmy nastħpujĢco:

Element a Î D jest najmniejszy,

jeĻli dla kaŇdego b Î D i b ¬ a

zachodzi f p (a,b) = true .

Z definicji tej moŇna wywnioskowaę, iŇ najmniejszy element nie jest poprzedzony Ňadnym innym

elementem zbioru, który siħ od niego róŇni. Jest to dosyę istotne spostrzeŇenie, poniewaŇ zbiory mogĢ

posiadaę elementy o identycznej zawartoĻci. Funkcja porównujĢca nie okreĻla kolejnoĻci wzglħdem

siebie elementów identycznych, tzn. poniewaŇ elementy te sĢ sobie równe, wiħc ich kolejnoĻę jest

zwykle nieistotna.

427581962.132.png

427581962.134.png

427581962.135.png

Schemat blokowy

D sortowany zbiór

n liczba elementów w zbiorze D

i,j zmienne licznikowe pħtli

m przechowuje indeks elementu minimalnego

f p ( ) funkcja porównujĢca dwa elementy ze zbioru D

x zmienna pomocnicza, uŇywana przy wymianie zawartoĻci elementów

d i i-ty element zbioru D

Na poczĢtku algorytmu uzyskujemy dostħp do zbioru D , który ma zostaę posortowany. W zmiennej n

umieszczamy iloĻę elementów w tym zbiorze.

Algorytm zawiera dwie pħtle. Pħtla zewnħtrzna wymienia kolejne najmniejsze elementy zbioru z

kolejnymi elementami poczĢwszy od pierwszego, a skoıczywszy na przedostatnim. Zadaniem pħtli

wewnħtrznej jest wyszukanie tego najmniejszego elementu. Pħtle te sĢ typowymi pħtlami iteracyjnymi

typu FOR . Zewnħtrzna sterowana jest zmiennĢ licznikowĢ i , która wskazuje kolejne elementy zbioru

do wymiany z elementem najmniejszym. Pħtla wewnħtrzna sterowana jest zmiennĢ j , która wskazuje

427581962.136.png

427581962.137.png

427581962.138.png

427581962.139.png

427581962.140.png

427581962.141.png

427581962.142.png

427581962.143.png

427581962.145.png

427581962.146.png

427581962.147.png

427581962.148.png

427581962.149.png

427581962.150.png

427581962.151.png

427581962.152.png

427581962.153.png

427581962.154.png

427581962.002.png

427581962.003.png

427581962.004.png

427581962.005.png

427581962.006.png

427581962.007.png

427581962.008.png

427581962.009.png

427581962.010.png

427581962.011.png

427581962.013.png

427581962.014.png

427581962.015.png

427581962.016.png

427581962.017.png

427581962.018.png

427581962.019.png

427581962.020.png

427581962.021.png

427581962.022.png

427581962.024.png

427581962.025.png

427581962.026.png

427581962.027.png

427581962.028.png

427581962.029.png

427581962.030.png

427581962.031.png

427581962.032.png

427581962.033.png

427581962.035.png

427581962.036.png

427581962.037.png

427581962.038.png

427581962.039.png

427581962.040.png

427581962.041.png

427581962.042.png

427581962.043.png

427581962.044.png

427581962.046.png

427581962.047.png

427581962.048.png

427581962.049.png

427581962.050.png

427581962.051.png

427581962.052.png

427581962.053.png

427581962.054.png

427581962.055.png

427581962.057.png

427581962.058.png

427581962.059.png

427581962.060.png

427581962.061.png

427581962.062.png

427581962.063.png

427581962.064.png

427581962.065.png

427581962.066.png

Plik z chomika:

Inne pliki z tego folderu:

sortowanie kubełkowe_17.11.2010.doc (2003 KB)
sortowanie bąbelkowe_15.11.2010.doc (837 KB)
sortwybor_program.pdf (23 KB)
sortowanie przez wybór_08.11.2010.doc (580 KB)
sortwstaw_program.pdf (39 KB)

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin