Opole, dn. 25 marca 2004

Laboratorium Algorytmów i Struktur Danych

Temat:

Analiza algorytmów sortowania

Autor: Dawid Najgiebauer

Informatyka, sem. II, grupa lab. 11

czw. g. 16.20

Prowadzący: dr inż. Jan Sadecki

1. Temat

Przeanalizować i zbadać algorytmy sortowania przez wstawianie (ang. insert sort), przez wybieranie (selekcję; ang. select sort) oraz sortowania bąbelkowego (naiwnego; ang. bubble sort).

2. Analiza, projektowanie

Celem badania jest sprawdzenie praktycznego zastosowania i efektywności algorytmów sortujących.

Każdy z algorytmów będzie dokonywał modyfikacji na tej samej tablicy, jaka została mu zadana, a więc oryginalna tablica ulegnie zniszczeniu.

1. Sortowanie przez selekcję (wybieranie)

Metoda ta polega na wybieraniu z całego ciągu liczby najmniejszej oraz największej i wstawienie ich odpowiednio na lewy i prawy kraniec analizowanego podciągu. Po każdej takiej zmianie analizowany podciąg zostaje pomniejszony o 1 element z lewej i z prawej, które w danym momencie są już posortowane.

Przykład takiego sortowania przedstawiono poniżej:

Tabela 1. Przykład sortowania przez selekcję

12

9

16

7

1

0

18

9

3

8

0

9

16

7

1

12

8

9

3

18

0

1

3

7

9

12

8

9

16

18

0

1

3

7

9

9

8

12

16

18

0

1

3

7

8

9

9

12

16

18

0

1

3

7

8

9

9

12

16

18

Poniżej przedstawiono schemat algorytmu:

2. Sortowanie przez wstawianie

Sortowanie wg tego algorytmu powoduje pobieranie kolejnego elementu z analizowanego podciągu i wstawienie go w odpowiednie miejsce w podciągu posortowanym, który narasta od lewej strony analizowanego ciągu.

Przykład działania tego algorytmu przedstawiony jest poniżej:

Tabela 2. Przykład sortowania przez wstawianie

12

9

16

7

1

0

18

9

3

8

9

12

16

7

1

0

18

9

3

8

≤

9

12

16

7

1

0

18

9

3

8

7

9

12

16

1

0

18

9

3

8

1

7

9

12

16

0

18

9

3

8

0

1

7

9

12

16

18

9

3

8

≤

0

1

7

9

12

16

18

9

3

8

≤

0

1

7

9

9

12

16

18

3

8

≤

0

1

3

7

9

9

12

16

18

8

≤

0

1

3

7

8

9

9

12

16

18

Schemat 2 przedstawia budowę tego algorytmu.

3. Sortowanie bąbelkowe

Metoda ta opiera się na porównywaniu dwóch sąsiadujących ze sobą wartości i ustawieniu ich w odpowiednim porządku. Porównywanie wykonywane jest tak długo, aż nie zostanie wykonane żadne przestawienie. W przypadku dojścia z porównywaniem do końca ciągu, rozpoczyna się ono od początku. Dodatkowo wiemy, że gdy ostatnia zamiana nastąpiła na danym polu, to wszystkie pola znajdujące się za nim są już uporządkowane.

Przykład działania algorytmu ilustruje poniższa tabela:

Tabela 3. Przykład sortowania przez wstawianie

12

9

16

7

1

0

18

9

3

8

9

12

7

1

0

16

9

3

8

18

9

7

1

0

12

9

3

8

16

18

7

1

0

9

9

3

8

12

16

18

7

1

0

9

9

3

8

12

16

18

1

0

7

9

3

8

9

12

16

18

0

1

7

3

8

9

9

12

16

18

0

1

3

8

7

9

9

12

16

18

0

1

3

8

7

9

9

12

16

18

3. Implementacje i wykonanie badania algorytmów

1. Założenia

Badania zostaną wykonane dla ciągów o długości 100. Każda z metod będzie bazowała na identycznej tablicy. Posortowaniu poddane zostaną tablice:

1. nieposortowana,

2. posortowana rosnąco (tak, jak sortują algorytmy)

3. posortowana rosnąca z jednym wyjątkiem (w środek będzie wstawiona liczba burząca porządek)

4. posortowana malejąco.

Dla każdej z metod zostanie zliczona całkowita ilość porównań przeprowadzonych w celu posortowania tablicy oraz ilość przeprowadzonych zamian (przestawień).

1. Implementacja algorytmu sortowania przez selekcję

void SelectSort(long* tab, long n)

{

long porownan=0,przestawien=0;

long i,start,stop;

long min,max, mini, maxi;

long pom;

for(start=0,stop=n-1;porownan++,start<=stop;start++,stop--)

{

min=max=tab[start];

mini=maxi=start;

for(i=start+1;porownan++,i<=stop;i++)

{

if (porownan++,tab[i]>max) {max=tab[i]; maxi=i;}

if (porownan++,tab[i]<min) {min=tab[i]; mini=i;}

}

pom=tab[start];

tab[start]=min;

tab[mini]=pom;

przestawien++;

pom=tab[stop];

tab[stop]=max;

tab[maxi]=pom;

przestawien++;

}

cout<<"SelectSort.Por.="<<porownan<<"; Przest.="<<przestawien<<endl;

}

2. Implementacja algorytmu sortowania przez wstawianie

void InsertSort(long* tab, long n)

{

long porownan=0,przestawien=0;

long i,j,x;

for(i=1;porownan++,i<n;i++)

{

x=tab[i];

for(j=i-1;porownan++,j>=0;j--)

{

porownan++;

if(tab[j]>x)

{

przestawien++;

tab[j+1]=tab[j];

}

else

break;

}

tab[j+1]=x;

}

cout<<"InsertSort.Por.="<<porownan<<"; Przest.="<<przestawien<<endl;

}

3. Implementacja algorytmu sortowania bąbelkowego

void BubbleSort(long* tab, long n)

{

long porownan=0,przestawien=0;

long i,stop;

long pom;

long ostzam;

for(stop=n-1;porownan++,stop>0;stop=ostzam)

{

ostzam=0;

for(i=0;porownan++,i<stop;i++)

{

if (porownan++,tab[i]>tab[i+1])

{

ostzam=i;

przestawien++;

pom=tab[i];

tab[i]=tab[i+1];

tab[i+1]=pom;

}

}

}

cout<<"BubbleSort.Por.="<<porownan<<"; Przest.="<<przestawien<<endl;

}

4. Wyniki badania

Średnie rezultaty badań przedstawiono w tabelce:

Tabela 4. Średnie rezultaty sortowania tablicy 100-elementowej.

Rodzaj tablicy	Sortowanie przez selekcję		Sortowanie przez wstawianie		Sortowanie bąbelkowe
		Porównań	Przestawień	Porównań	Przestawień	Porównań	Przestawień
Nieposortowana	7601	100	5501	2687	9479	2687
Posortowana rosnąco	7601	100	298	0	201	0
Posortowana z wyjątkiem	7601	100	410	53	3061	53
Posortowana malejąco	7601	100	10075	4931	10099	4931

5. Uwagi i wnioski z testowania i uruchamiania

1. Sortowanie przez selekcję zawsze wykonuje tyle samo porównań i przestawień niezależnie od porządku sortowanych danych.

2. Algorytmy sortowania przez wstawianie oraz bąbelkowego najlepiej sprawdzają się, gdy zadana tablica jest już posortowana lub jest już w dużej mierze wysortowana.

3. W przypadku, gdy tablica posortowana jest malejąco, algorytmy sortowania przez wstawianie oraz bąbelkowego są najbardziej pracochłonne.

4. Generalnie najlepszym z algorytmów wydaje się być algorytm sortowania przez wstawianie; najgorszym - sortowania bąbelkowego, z wyjątkiem sytuacji, gdzie dane są już w uporządkowane.

12 Dawid Najgiebauer

Implementacje i wykonanie badania algorytmów 11

Temat 3

tab[j+1]=x

N

j--

tab[j+1]=tab[j]

T

tab[j]>x

T

j≥0

j=i-1

pom=tab[start];

tab[start]=min;

tab[mini]=pom;

N

i++

min=tab[i]

mini=i

T

tab[i]<min

N

max=tab[i]

maxi=i

T

tab[i]>max

T

i≤stop

i=start+1

min=max=tab[start]

mini=maxi=start

T

N

STOP

x=tab[i]

T

STOP

N

i<n

i=1

tab[], n

Schemat 2. Sortowanie przez wstawianie.

stop--

pom=tab[stop];

tab[stop]=max;

tab[maxi]=pom;

i++

start=0

stop=N-1

start≤stop

Tab[], N

Schemat 1. Schemat algorytmu sortowania przez selekcję.

Schemat 3. Sortowanie bąbelkowe

tab[], n

stop=n-1

stop>0

N

STOP

T

ostzam=0

i=0

i<stop

N

stop=ostzam

T

tab[i]>tab[i+1]

T

ostzam=i

pom=tab[i]

tab[i]=tab[i+1]

tab[i+1]=pom

N

i++

---