sortowania

Sortowanie B

belkowe

Bubble Sort

Jest to prosty algorytm sortuj

cy o zło

ono

ci obliczeniowej O(n

Pomimo swojej prostoty nie nadaje si

do sortowania du

ych zbiorów

danych (za górn

granic

przyj

to około 5000 elementów). Algorytm

opiera si

na kolejnych porównaniach dwóch s

siednich elementów za

pomoc

funkcji porównuj

cej. Je

li porównywane elementy s

w dobrej

kolejno

ci, to nast

puje przej

cie do nast

pnego elementu. W przeciwnym

razie elementy s

zamieniane miejscami. Działanie to jest kontynuowane,

wszystkie pary s

siednich elementów w zbiorze b

uło

one we

wła

ciwej kolejno

ci.

Przykład

Posortujemy metod

belkow

zbiór pi

ciu liczb: { 9 5 6 3 1 } w porz

dku

rosn

cym. Porz

dek rosn

cy oznacza, i

element poprzedzaj

cy jest

zawsze mniejszy lub równy od elementu le

Ŝą

cego dalej w zbiorze. Nasza

funkcja porównuj

ca przyjmie zatem posta

relacji mniejszy lub równy.

Algorytm sortowania b

belkowego nie jest zbytnio efektywny dla

nieuporz

dkowanych zbiorów danych. Jednak je

li zbiór jest w wi

kszo

uporz

dkowany (tylko kilka elementów znajduje si

na niewła

ciwym

miejscu), to zło

ono

ść

obliczeniowa zbli

a si

do klasy O(n), a wi

c czas

sortowania zale

y liniowo od liczby elementów, co powoduje, i

wci

ąŜ

na go zastosowa

w niektórych przypadkach.

Schemat blokowy

Dany jest zbiór { a

...a

n-2

n-1

}, który nale

y posortowa

zgodnie z funkcj

porównuj

fp(...). W algorytmie zastosowano nast

puj

ce zmienne:

liczba elementów w zbiorze

a[...] element zbioru o numerze od 1 do n, podanym w klamrach kwadratowych

i , j

zmienne u

ywane na liczniki p

tli

zmienna logiczna u

ywana do sprawdzenia, czy cały zbiór jest ju

posortowany

zmienna tymczasowa u

ywana przy wymianie zawarto

ci elementów tablicy

Algorytm rozpoczynamy nadaj

c zmiennej i warto

ść

0. Zmienna ta pełni funkcj

: licznika elementów,

które zostały ju

uporz

dkowane na ko

cu zbioru - patrz przykład. Poniewa

jeszcze nie

uporz

dkowano

adnych elementów, dlatego i przyjmuje warto

ść

W p

tli wewn

trznej porównujemy ze sob

kolejne elementy zbioru z elementem nast

pnym. Zmienna

p jest znacznikiem uporz

dkowania zbioru. Przed wej

ciem do p

tli ustawiana jest na warto

ść

logiczn

true. Je

li wewn

trz p

tli elementy nie s

uporz

dkowane, tzn. funkcja porównuj

fp( a[j] , a[j+1] ) daje w wyniku warto

ść

logiczn

false, porównywane elementy s

ze sob

zamieniane i znacznik p przyjmuje warto

ść

false. Spowoduje to nast

pny obieg p

tli zewn

trznej,

która wykonuje si

do momentu, a

p b

dzie miało warto

ść

logiczn

true, czyli nie wyst

piła

adna

zamiana elementów zbioru, co oznacza jego uporz

dkowanie.

Po porównaniu elementów i ewentualnej zamianie ich miejsc nast

puje zwi

kszenie indeksu j. Je

li w

zbiorze pozostały jeszcze jakie

elementy do porównania, to wykonywany jest nast

pny obieg p

tli

wewn

trznej.

W przeciwnym razie p

tla wewn

trzna jest ko

czona i nast

puje zwi

kszenie o 1 licznika p

tli

zewn

trznej. Powoduje to zmniejszenie o 1 liczby elementów do porównania w zbiorze - ka

dy obieg

tli zewn

trznej ustala pozycj

ostatniego elementu zbioru - w nast

pnym obiegu nie musimy go ju

sprawdza

, co przy du

ej liczbie elementów znacznie zmniejsza ilo

ść

wykonywanych porówna

li znacznik uporz

dkowania zbioru p ma warto

ść

false, to nast

puje kolejny obieg p

tli

zewn

trznej. Jest to konieczne, poniewa

zbiór mo

e by

nieuporz

dkowany. Sortowanie ko

czymy

dopiero wtedy, gdy wszystkie pary kolejnych elementów s

we wła

ciwym porz

dku i w trakcie

przegl

dania zbioru nie wyst

piło

adne przestawienie elementów. Zwró

my uwag

, i

li zbiór jest

w du

ej mierze uporz

dkowany, to algorytm zako

czy si

po kilku obiegach p

tli zewn

trznej, a wi

jest dosy

efektywnym rozwi

zaniem.

Poni

ej przedstawiamy realizacj

opisanego algorytmu sortowania w ró

nych j

zykach

programowania. Program tworzy dwie tablice o identycznej zawarto

ci, wypełnione przypadkowymi

liczbami. Nast

pnie jedn

z tych tablic sortuje i wy

wietla obie dla zobrazowania efektu posortowania

danych.

Przykład w C++

#include <stdlib.h>
#include <time.h>
#include <iostream.h>

const int n = 10; // liczba elementów w sortowanym zbiorze

// funkcja porównująca

int fp(int x, int y)
{
return (x <= y);
}

int main()
{
int i,j,t,p,a[n],b[n];

// tworzymy tablicę z przypadkową zawartością.
// tablica b[] słuŜy do zapamiętania stanu a[]

    srand( (unsigned)time( NULL ) );
    for(i = 0; i < n; i++ )
        a[i] = b[i] = 1 + rand() % (n + n);

// sortowanie bąbelkowe

    i = 0;
    do
    {
        p = 1;
        for(j = 0; j < n - i - 1; j++)
            if(!fp(a[j],a[j+1]))

            {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                p = 0;
            };
            i++;
    }
    while(p == 0);

// wyświetlamy wyniki

    cout << "Sortowanie babelkowe" << endl
         << "(C)2003 mgr Jerzy Walaszek" << endl << endl
         << "  lp    przed       po" << endl
         << "------------------------" << endl;
    for(i = 0; i < n; i++)
    {
        cout.width(4); cout << i;
        cout.width(9); cout << b[i];
        cout.width(9); cout << a[i] << endl;
    };
    cout << endl;
    cout.flush();
    system("pause");
    return 0;

Sortowanie przez Wstawianie

Insertion Sort

Algorytm sortowania przez wstawianie nale

y równie

do klasy

zło

ono

ci obliczeniowej

O(n

), lecz w

porównaniu do opisanego wcze

niej algorytmu

sortowania b

belkowego

jest du

o szybszy i bardziej

efektywny, lecz oczywi

cie bardziej zło

ony koncepcyjnie. Zasada działania tego algorytmu

przypomina układanie w r

ce kart pobieranych z talii. W skrócie mo

emy opisa

go tak:

Na ko

cu (lub na pocz

tku) zbioru tworzymy uporz

dkowan

list

elementów. Najpierw lista ta składa

z ostatniego elementu. Ze zbioru wyci

gamy przedostatni element. Miejsce, które zajmował staje

puste. Sprawdzamy, czy wyci

gni

ty element jest w dobrej kolejno

ci z elementem ostatnim. Je

tak, to wstawiamy go z powrotem do zbioru. Je

li nie, to na jego miejsce przesuwamy element ostatni,

a na miejsce elementu ostatniego wstawiamy wyci

gni

ty element. W efekcie na ko

cu zbioru mamy

dwa elementy w dobrej kolejno

ci. Teraz kolejno wybieramy elementy od ko

ca zbioru i

wstawiamy je w odpowiednie miejsce tworzonej na ko

cu listy. Elementy wcze

niejsze s

przesuwane

na li

cie o jedn

pozycj

w lewo. Operacje te s

kontynuowane a

do wstawienia pierwszego

elementu. W efekcie otrzymujemy posortowany zbiór.

Wstawianie elementu do listy uporz

dkowanej

Prezentowany algorytm sortowania przez wstawianie wymaga wstawiania elementu zbioru do listy
uporz

dkowanej. Mamy element wybrany ze zbioru. Naszym zadaniem jest przeszukanie listy

uporz

dkowanej i znalezienie pozycji, na której ma si

znale

źć

wybrany element. Zadanie to

wykonamy najpro

ciej rozpoczynaj

c przegl

danie od pocz

tku listy uporz

dkowanej. Je

funkcja

porównuj

przyjmuje warto

ść

false dla elementu wybranego i

elementu z listy, to element z listy uporz

dkowanej przenosimy na

poprzedni

pozycj

i przechodzimy do sprawdzenia kolejnego elementu

na li

cie. Je

li funkcja porównuj

ca przyjmie warto

ść

true, to element

wybrany umieszczamy na poprzednim miejscu na li

cie uporz

dkowanej

(poprzednie miejsce w stosunku do aktualnie testowanego jest zawsze
wolne!).

W przykładzie przedstawionym poni

ej wstawiamy liczb

6 do lity {2 4 5

7 9}. Funkcja porównuj

ca wyznacza porz

dek rosn

cy (ma warto

ść

true, je

li kolejne argumenty s

w porz

dku rosn

cym).

Schemat blokowy

Dany jest zbiór { a

...a

n-2

n-1

}, który nale

y posortowa

zgodnie

funkcj

porównuj

fp(...). Do opisu algorytmu stosujemy nast

puj

zmienne:

liczba elementów w zbiorze

a[...] element zbioru o numerze od 1 do n, podanym w klamrach kwadratowych

i , j

zmienne u

ywane na liczniki p

tli

zmienna tymczasowa u

ywana do przechowania wstawianego elementu

tla zewn

trzna wykona n-1 obiegów. Na pocz

tku zmienn

licznikow

tej p

tli ustawiamy na

warto

ść

n-1. Wskazuje ona przedostatni element zbioru. Element ten wybieramy do wstawiania.

Najpierw zapami

tujemy go w zmiennej tymczasowej t. Dzi

ki temu pozycja zajmowana przez ten

element zostaje zwolniona.

W p

tli wewn

trznej sterowanej zmienn

j przeszukujemy tworzon

na ko

cu zbioru list

uporz

dkowan

w poszukiwaniu pozycji wstawienia wybranego wcze

niej elementu. Wszystkie

elementy mniejsze na li

cie uporz

dkowanej s

przesuwane o jedn

pozycj

wstecz. Przeszukiwanie

listy uporz

dkowanej ko

czy si

w dwóch przypadkach:

1. Osi

gni

to koniec listy - wybrany element jest wi

kszy wg funkcji porównuj

cej od wszystkich

elementów

cie

uporz

dkowanej.

2. Funkcja porównuj

ca przyjmuje warto

ść

true, co oznacza, i

wybrany element powinien by

umieszczony przed testowanym elementem listy uporz

dkowanej.

Gdy p

tla wewn

trzna zako

czy swoje działanie, to w obu mo

liwych przypadkach zmienna j zawiera

pozycj

o 1 wi

ksz

od pozycji wstawiania. Dlatego element wybrany wpisujemy na pozycj

a[j - 1].

Zmniejszamy licznik p

tli zewn

trznej, sprawdzamy, czy nie osi

ł on warto

ci ko

cowej. Je

li nie,

to kontynuujemy z nast

pnym elementem zbioru. W przeciwnym wypadku ko

czymy wykonywanie

algorytmu

sortowania.

Poni

ej przedstawiamy realizacj

opisanego algorytmu sortowania w ró

nych j

zykach

programowania. Program tworzy dwie tablice o identycznej zawarto

ci, wypełnione przypadkowymi

liczbami. Nast

pnie jedn

z tych tablic sortuje i wy

wietla obie dla zobrazowania efektu posortowania

danych.

Sortowanie przez Selekcj

Selection Sort

Algorytm sortowania przez selekcj

nale

y do algorytmów sortuj

cych o klasie

zło

ono

obliczeniowej

O(n

). Nie jest on cz

sto stosowany, poniewa

opisany w poprzednim rozdziale

algorytm

sortowania przez wstawianie

ma t

sam

zło

ono

ść

, a jest nieco szybszy. Zasada działania

jest bardzo prosta. Najpierw szukamy w zbiorze elementu najmniejszego. Gdy zostanie znaleziony,

wymieniamy

go z pierwszym elementem zbioru. Nast

pnie zbiór pomniejszamy o ten pierwszy

element, który ustawiony został ju

na wła

ciwej pozycji. W tak pomniejszonym zbiorze znów szukamy

elementu najmniejszego i wstawiamy go na drug

pozycj

. Zbiór pomniejszamy i kontynuujemy te

same operacje wyszukiwa

i wstawie

, a

wszystkie elementy zbioru zostan

posortowane.

Przykład

Posortujemy t

metod

zbiór pi

ciu liczb: { 9 5 6 3 1 } w porz

dku rosn

cym. Nasza

funkcja

porównuj

przyjmie wi

c posta

relacji mniejszy lub równy.

{ 9 5 6 3

}

W zbiorze szukamy najmniejszego elementu. Jest nim liczba

{

5 6 3

}

Poniewa

najmniejszy element nie jest na pierwszej pozycji, wi

c wymieniamy go z

elementem pierwszym, czyli

{ 5 6

9 }

W pomniejszonym zbiorze szukamy elementu najmniejszego. Jest nim liczba

{

9 }

Znaleziony element najmniejszy wymieniamy z pierwszym elementem.

{ 6

9 }

Na wła

ciwym miejscu s

dwa elementy zbioru. W

ród pozostałych elementów

znajdujemy element najmniejszy.

{

9 }

Wymieniamy go z pierwszym elementem zbioru

1 3 5

{

9 }

Na wła

ciwym miejscu s

trzy elementy. Poniewa

pozostały zbiór posiada

cej ni

jeden element, dalej szukamy elementu najmniejszego. Poniewa

element najmniejszy jest ju

na pierwszym miejscu, nie wykonujemy

adnych

przestawie

{ 1 3 5 6 9 }

Po wykonaniu ostatniej operacji wszystkie elementy zostały posortowane.

Wyszukanie najmniejszego elementu w zbiorze

W podanym algorytmie wyst

puje problem znalezienia najmniejszego elementu w zbiorze wzgl

dem

zadanej

funkcji porównuj

cej

. Element najmniejszy zdefiniujmy nast

puj

co:

∈

D jest najmniejszy, je

li dla ka

dego b

∈

D i a

≠

b zachodzi fp(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.

Element najmniejszy znajdujemy nast

puj

co: za tymczasowy element najmniejszy przyjmujemy

pierwszy element zbioru. Nast

pnie porównujemy go kolejno ze wszystkimi pozostałymi elementami

za pomoc

funkcji porównuj

cejj

. Je

li dla jakiego

elementu funkcja ta przyjmie warto

ść

logiczn

false, to element ten b

dzie mniejszy od tymczasowego i zast

pimy nim najmniejszy element

tymczasowy.

Oto odpowiedni przykład: naszym zadaniem jest wyszukanie najmniejszego elementu w zbiorze { 4 7
3 2 5 1 }. Niech funkcja porównuj

ca ustala porz

dek rosn

cy.

{

7 3 2 5 1 }

Za tymczasowy najmniejszy element przyjmujemy pierwszy element zbioru, czyli

{

3 2 5 1 }

Nast

pnie porównujemy go kolejno z pozostałymi elementami zbioru:

fp(4,7) = true - dobra kolejno

ść

, pozostawiamy element tymczasowy bez zmian

{

2 5 1 }

fp(4,3) = false - znale

my element mniejszy, wi

c za nowy element

najmniejszy przyjmujemy warto

ść

{ 4 7

5 1 }

Kontynuujemy przegl

danie

znalezionym

najmniejszym

elementem

tymczasowym:
fp(3,2) = false - nowy element najmniejszy

{ 4 7 3

1 }

fp(2,5) = true - dobra kolejno

ść

, liczba

pozostaje elementem najmniejszym

{ 4 7 3

}

fp(2,1) = false - zła kolejno

ść

, znale

my nowy element najmniejszy -

{ 4 7 3 2 5

}

Poniewa

przegl

my wszystkie elementy zbioru, to warto

ść

jest

najmniejsza wg funkcji porównuj

cej ten zbiór.

Schemat blokowy

Dany jest zbiór { a

...a

n-2

n-1

}, który nale

y posortowa

zgodnie z

funkcj

porównuj

cej

fp(...). Do opisu algorytmu stosujemy nast

puj

ce zmienne:

liczba elementów w zbiorze

a[...]

element zbioru o numerze od 1 do
n

podanym

klamrach

kwadratowych

i , j

zmienne u

ywane na liczniki p

tli

zmienna przechowuj

ca indeks

elementu najmniejszego

zmienna pomocnicza

Zmienna i otrzymuje na pocz

tku warto

ść

1. Pełni ona rol

licznika obiegów p

tli zewn

trznej oraz

elementów posortowanych - znajduj

cych si

na wła

ciwej pozycji.

Zmienna t zawiera indeks najmniejszego elementu. Na pocz

tku p

tli wewn

trznej przyjmuje ona

numer pierwszego elementu w zbiorze, czyli i-ty. Nast

pnie przeszukujemy pozostał

ęść

zbioru w

poszukiwaniu elementów mniejszych. Je

li takie zostan

znalezione, to ich indeksy b

wprowadzone do zmiennej t. Kryterium znajdowania elementu najmniejszego ustala funkcja
porównuj

ca dla tego zbioru.

Po przeszukaniu całego zbioru w t mamy indeks najmniejszego elementu. Wymieniamy pierwszy
element zbioru (i-ty) z elementem najmniejszym. Dzi

ki tej operacji na pocz

tek zbioru trafia element

najmniejszy, który znajduje si

na wła

ciwej pozycji.

Zmienna i zostaje zwi

kszona o 1, co powoduje zmniejszenie zbioru do posortowania i przej

cie do

kolejnego elementu. P

tla jest kontynuowana, a

wszystkie elementy zbioru zostan

posortowane.

Poni

ej przedstawiamy realizacj

opisanego algorytmu sortowania w ró

nych j

zykach

programowania. Program tworzy dwie tablice o identycznej zawarto

ci, wypełnione przypadkowymi

liczbami. Nast

pnie jedn

z tych tablic sortuje i wy

wietla obie dla zobrazowania efektu posortowania

danych.

#include <stdlib.h>

#include <time.h>

#include <iostream.h>

const int n = 10; // liczba elementów w sortowanym zbiorze

// funkcja porównuj

int fp(int x, int y)

{

return (x <= y);

}

int main()

{

int i,j,t,x,a[n],b[n];

};

cout << endl;

cout.flush();

system("pause");

return 0;

}

Sortowanie Metod

Shella

Shell Sort

Algorytm ten został zaproponowany przez Donalda Shella w 1959 roku. Jest to najszybszy algorytm
sortuj

cy w klasie O(n

). Idea jest nast

puj

ca: Shell zauwa

ył, i

algorytm

sortowania przez

wstawianie

(insertion sort) jest bardzo efektywny, gdy zbiór jest ju

w du

ej cz

ęś

ci uporz

dkowany.

Wtedy zło

ono

ść

obliczeniowa jest prawie liniowa - O(n). Jednak

e algorytm ten nieefektywnie

przestawia elementy w trakcie sortowania - poniewa

porównywane s

kolejne elementy na li

cie

uporz

dkowanej, to ulegaj

one przesuni

ciu tylko o jedn

pozycj

przy ka

dym obiegu p

tli

wewn

trznej. Shell wpadł na pomysł modyfikacji algorytmu sortowania przez wstawianie tak, aby

porównywane były na pocz

tku elementy odległe od siebie, a pó

niej ta odległo

ść

malała i w ko

cowej

fazie powstawałby zwykły algorytm sortowania przez wstawianie, lecz ze zbiorem jest ju

w du

stopniu uporz

dkowanym.

Osi

ł to dziel

c w ka

dym obiegu zbiór na odpowiedni

liczb

podzbiorów, których elementy s

siebie odległe o stał

odległo

ść

g. Nast

pnie ka

dy z podzbiorów jest sortowany za pomoc

sortowania przez wstawianie. Powoduje to cz

ęś

ciowe uporz

dkowanie zbioru. Dalej odległo

ść

g jest

zmniejszana (najcz

ęś

ciej o połow

), znów s

tworzone podzbiory (jest ich teraz mniej) i nast

puje

kolejna faza sortowania. Operacje te kontynuujemy a

do momentu, gdy odległo

ść

g osi

gnie warto

ść

0. Wtedy zbiór wyj

ciowy b

dzie uporz

dkowany.

Zasadniczym czynnikiem wpływaj

cym na efektywno

ść

algorytmu sortowania metod

Shella jest

odpowiedni dobór ci

gu kolejnych odst

pów. Shell zaproponował przyj

cie na pocz

tku odst

równego połowie liczby elementów w zbiorze, a nast

pnie zmniejszanie tego odst

pu o połow

przy

dym obiegu p

tli. Nie jest to najbardziej efektywne rozwi

zanie, jednak najprostsze w

implementacji. Dlatego b

dziemy z niego korzysta

Przykład

Posortujemy metod

Shella zbiór o

miu liczb: { 4 2 9 5 6 3 8 1 } w porz

dku rosn

cym. Nasza

funkcja

porównuj

przyjmie wi

c posta

relacji mniejszy lub równy. Zbiór posiada osiem elementów, zatem

przyjmiemy na wst

pie odst

p g równy 4. Taki odst

p podzieli zbiór na 4 podzbiory, których elementy

elementami zbioru wej

ciowego odległymi od siebie o 4 pozycje:

{

}

zbiór

podstawowy

{

}

pierwszy

podzbiór,

elementy

{

}

drugi

podzbiór,

elementy

{

}

trzeci

podzbiór,

elementy

{ 4 6 }

- czwarty podzbiór, elementy a

i a

Teraz ka

dy z otrzymanych podzbiorów sortujemy algorytmem sortowania przez wstawianie.

Poniewa

zbiory te s

dwuelementowe, to sortowanie p

dzie polegało na porównaniu pierwszego

elementu podzbioru z elementem drugim i ewentualn

zamian

ich miejsc, je

li b

w niewła

ciwym

porz

dku okre

lonym

funkcj

porównuj

{

5 1

}

{ 1 5 }

Podzbiór pierwszy. Niewła

ciwa kolejno

ść

, zamieniamy miejscami

{

9 8

}

{ 8 9 }

Podzbiór drugi. Niewła

ciwa kolejno

ść

, zamieniamy miejscami

{ 2 3 }

Podzbiór trzeci. Kolejno

ść

dobra, pozostawiamy bez zmian.

{ 4 6 }

Podzbiór czwarty. Kolejno

ść

dobra, pozostawiamy bez zmian

Po pierwszym obiegu otrzymujemy nast

puj

cy wynik uporz

dkowania zbioru:

{

}

pierwszy

podzbiór,

elementy

{

}

drugi

podzbiór,

elementy

{

}

trzeci

podzbiór,

elementy

{

}

czwarty

podzbiór,

elementy

{ 4 2 8 1 6 3 9 5 }

- zbiór podstawowy

Zmniejszamy odst

p g o połow

, wi

c g = 2. Zbiór podstawowy zostanie podzielony na dwa

podzbiory:

{

}

zbiór

podstawowy

{

}

pierwszy

podzbiór,

elementy

{

}

drugi

podzbiór,

elementy

dy z tych podzbiorów sortujemy przez wstawianie:

{ 2 5 3 1 }

Na ko

cu tworzymy list

uporz

dkowan

, a kolejne elementy wstawiamy na t

list

pocz

wszy od przedostatniego i sko

czywszy na pierwszym.

{ 2 5

}

{ 2 5

1 3

}

1 przesuwamy na puste miejsce, a 3 umieszczamy na zwolnionej pozycji. Lista
uporz

dkowana zawiera ju

2 elementy.

{ 2

1 3

}

{ 2

1 3 5

}

1 i 3 przesuwamy o jedn

pozycj

w lewo, a 5 umieszczamy na zwolnionej pozycji.

Lista uporz

dkowana ma ju

3 elementy

{

1 3 5

}

{

1 2 3 5

}

1 przesuwamy na wolne miejsce, a 2 wstawiamy na zwolnion

pozycj

pomi

dzy 1 a

3. Podzbiór pierwszy został uporz

dkowany

{ 4 9 6 8 }

W taki sam sposób porz

dkujemy podzbiór drugi

{ 4 9

}

{ 4 9

6 8

}

Poniewa

6 jest w dobrym porz

dku z 8, to nie dokonujemy wymiany elementów.

{ 4

6 8

}

{ 4

6 8 9

}

6 i 8 przesuwamy o jedn

pozycj

w lewo, a 9 wstawiamy na koniec listy

uporz

dkowanej.

{

6 8 9

}

{

4 6 8 9

}

4 jest w dobrej kolejno

ci, wi

c nie dokonujemy wstawiania wewn

trz listy.

Po drugim obiegu otrzymujemy nast

puj

cy wynik uporz

dkowania zbioru wej

ciowego:

{

}

pierwszy

podzbiór,

elementy

{

}

drugi

podzbiór,

elementy

{ 4 1 6 2 8 3 9 5 }

- zbiór podstawowy

Zmniejszamy odst

p g o połow

, g = 1. Taki odst

p nie dzieli zbioru wej

ciowego na podzbiory, wi

teraz b

dzie sortowany przez wstawianie cały zbiór. Jednak algorytm sortuj

cy ma ułatwion

prac

poniewa

dzi

ki poprzednim dwóm obiegom zbiór został cz

ęś

ciowo uporz

dkowany - elementy małe

zbli

yły si

do pocz

tku zbioru, a elementy du

e do ko

ca.

{ 4 1 6 2 8 3 9 5 }

Na ko

cu tworzymy list

uporz

dkowan

, a kolejne elementy wstawiamy

na t

list

pocz

wszy od przedostatniego i sko

czywszy na pierwszym.

{ 4 1 6 2 8 3

}

{ 4 1 6 2 8 3

5 9

}

5 przesuwamy na woln

pozycj

, a 9 wstawiamy na koniec listy.

{ 4 1 6 2 8

5 9

}

{ 4 1 6 2 8

5 9

}

3 pozostawiamy na miejscu

{ 4 1 6 2

3 5 9

}

{ 4 1 6 2

5 8 9

}

3 i 5 przesuwamy o 1 pozycj

w lewo, a 8 wstawiamy na zwolnione miejsce

pomi

dzy 5 i 9

{ 4 1 6

3 5 8 9

}

{ 4 1 6

2 3 5 8 9

}

2 pozostawiamy na miejscu.

{ 4 1

2 3 5 8 9

}

{ 4 1

2 3 5 6 8 9

}

2, 3 i 5 przesuwamy o 1 pozycj

w lewo. Na zwolnione miejsce wstawiamy

{ 4

2 3 5 6 8 9

}

{ 4

1 2 3 5 6 8 9

}

1 pozostawiamy na swoim miejscu.

{

1 2 3 5 6 8 9

}

{

1 2 3 4 5 6 8 9

}

1, 2 i 3 przesuwamy o 1 pozycj

w lewo. Na zwolnione miejsce pomi

dzy 3

a 5 wstawiamy 4. Zbiór jest uporz

dkowany.

Zaleta algorytmu sortuj

cego metod

Shella ujawni si

przy du

ej liczbie elementów. W takim

przypadku zbiór zostaje najszybciej posortowany ze wszystkich algorytmów sortuj

cych klasy O(n

Algorytm mo

na jeszcze bardziej zoptymalizowa

dobieraj

c odpowiednio ci

g odst

pów g, lecz tym

zagadnieniem nie b

dziemy si

tutaj zajmowa

Schemat blokowy

Dany jest zbiór { a

...a

n-2

n-1

}, który nale

y posortowa

zgodnie z

funkcj

porównuj

fp(...). Do opisu algorytmu stosujemy nast

puj

ce zmienne:

liczba elementów w zbiorze

a[...] element zbioru o numerze od 1 do n, podanym w klamrach kwadratowych

i , j

zmienne u

ywane na liczniki p

tli

zmienna przechowuj

ca odst

p pomi

dzy sortowanymi elementami.

zmienna tymczasowa u

ywana przy wymianie zawarto

ci elementów tablicy

Algorytm sortuj

cy Shella

Algorytm sortowania przez wstawianie

W celach porównawczych rozmy

lnie umie

cili

my powy

ej schematy blokowe algorytmu sortowania

metod

Shella oraz

przez wstawianie

. Zwró

cie uwag

na ich podobie

stwo. Algorytm Shella jest

modyfikacj

algorytmu sortowania przez wstawianie polegaj

na tym, i

nie jest sortowany od razu

cały zbiór, lecz jego podzbiory. Do tego celu słu

y wła

nie odst

p g, który w algorytmie Shella jest

zmienny, a w sortowaniu przez wstawianie jest stały i wynosi 1. Dodatkowa oprawa algorytmu Shella
zawiera wi

c obsług

zmian odst

pu g. Pozostała cz

ęść

jest praktycznie taka sama jak w algorytmie

sortowania przez wstawianie.

Poni

ej przedstawiamy realizacj

opisanego algorytmu sortowania w ró

nych j

zykach

programowania. Program tworzy dwie tablice o identycznej zawarto

ci, wypełnione przypadkowymi

liczbami. Nast

pnie jedn

z tych tablic sortuje i wy

wietla obie dla zobrazowania efektu posortowania

danych.

liczby sortowanych elementów. Przy du

ej ich liczbie (si

gaj

cej dziesi

tków lub setek tysi

cy)

sortowanie mo

e zaj

ąć

nawet najszybszemu komputerowi du

Ŝą

ilo

ść

czasu (nawet wiele wieków!).

Zachodzi wi

c naturalne pytanie, czy nie da si

tego zrobi

szybciej? Odpowied

jest pozytywna.

Wymy

lono wiele algorytmów sortuj

cych, które nale

Ŝą

do klasy zło

ono

ci obliczeniowej O(n log

n) -

liniowo logarytmicznej. Poniewa

logarytm z n jest zawsze mniejszy od n (dla n >= 1), to ich iloczyn

jest mniejszy od n

, co zapisujemy:

n log

n < n

Wobec tego algorytm o zło

ono

ci obliczeniowej klasy O(n log

n) wykona si

o wiele szybciej od

algorytmu klasy O(n

). Ró

nica ta jest szczególnie drastyczna dla du

ych warto

ci n. Dzi

ki temu

algorytmy sortuj

ce klasy O(n log

n) nadaj

szczególnie do sortowania du

ych ilo

ci elementów,

gdzie wyra

nie korzystamy z ich zalet. Wad

tych algorytmów jest wi

ksza zło

ono

ść

w stosunku do

opisanych metod sortowania zbiorów danych. Z drugiej strony nic nie przychodzi darmo.

Pierwszy z szybkich algorytmów sortuj

cych wykorzystuje specjaln

struktur

danych, zwan

kopcem

(ang. Heap). Przed opisem samego algorytmu zajmiemy si

własno

ciami kopca oraz sposobami jego

tworzenia i pobierania z niego danych.

Drzewo binarne

Drzewo binarne (ang. binary tree - Btree) jest
hierarchiczn

struktur

danych, w której elementy nosz

nazw

złów. Ka

dy w

zeł mo

e si

czy

z dwoma

kolejnymi w

złami. Na przykład w

zeł b ł

czy si

złami d i e. W

zły d i e nosz

nazw

złów

potomnych w

zła b lub potomków w

zła b. W

zeł b jest

dla w

złów d i e w

złem rodzicielskim lub przodkiem.

zły posiadaj

ce potomków nazywamy gał

ziami - np.

a, b, c, d. W

zły nie posiadaj

ce potomków nosz

nazw

ci - e, f, g, h, i. Pierwszy w

zeł, z którego wyrasta całe

drzewo nazywa si

złem głównym lub korzeniem - jest

to w

zeł a.

Nazwa drzewa pochodzi od własno

ci posiadania przez

dy w

zeł do dwóch potomków. W j

zyku angielskim słówko binary oznacza dwójkowy -

binary tree - drzewo dwójkowe.

Drzewa binarne da si

w prosty sposób

odwzorowa

pami

komputera,

tworz

ce je elementy b

umieszczone w tej

pami

ci obok siebie - tak dzieje si

w tablicach.

Rozwa

my poni

sze drzewo binarne:

zeł tworzony przez element a

posiada

dwóch potomków - a

oraz a

. W

zeł a

posiada

równie

dwóch potomków - a

i a

. Je

dokładnie przyjrzymy si

indeksom elementów

tworz

cych drzewo binarne, to musimy doj

ść

nast

puj

cego wniosku:

li w

zeł utworzony przez element a

potomków, to musz

to by

elementy a

2 x i

oraz

2 x i + 1

. Innymi słowy indeksy potomków w

zła

i-tego maj

warto

ść

2 x i - lewy potomek w

zła i-tego

2 x i + 1 - prawy potomek w

zła i-tego.

Teraz rozwa

my przodków danego w

zła. Tutaj równie

przyjrzenie si

indeksom da nam szybk

odpowied

- przodkiem w

zła i-tego (i musi by

ksze od 1, poniewa

korze

drzewa nie posiada

przodka) jest w

zeł o indeksie równym |i / 2| (cz

ęść

całkowita z dzielenia).

Wzory te pozwalaj

odwzorowa

liniowy ci

g elementów (tablic

) w drzewo binarne i na odwrót. Na

rysunku poni

ej drzewa binarnego widzimy powi

zania poszczególnych elementów w takiej strukturze.

Przykład

Przedstawi

w postaci drzewa binarnego nast

puj

cy ci

g elementów { 3 1 6 8 9 4 }

Tworzenie drzewa rozpoczynamy od korzenia, którym jest pierwszy element ci

gu,

czyli 3.

Do korzenia doł

czamy w

zły potomne, s

to kolejne dwa elementy - 1 i 6

Przechodzimy na nast

pny poziom struktury drzewa i do lewego w

zła [1] doł

czamy

jego w

zły potomne - kolejne dwa elementy ze zbioru, czyli 8 i 9.

Pozostał nam ostatni element, który jest potomkiem w

zła [6].

Kopiec

Kopiec jest drzewem binarnym, w którym istniej

zale

ci pomi

dzy w

złami potomnymi a ich

przodkiem wyznaczone przez

funkcj

porównuj

w sposób nast

puj

cy:

Dla ka

dego w

zła posiadaj

cego potomków zachodzi

fp(potomek,przodek) = true

Innymi słowy, je

li funkcja porównuj

ca wyznacza porz

dek rosn

cy, to w strukturze kopca ka

przodek ma warto

ść

ksz

lub równ

warto

ci swoich potomków. Korze

kopca ma najwi

ksz

warto

ść

- jest elementem maksymalnym.

To drzewo binarne nie tworzy
struktury kopca, poniewa

np. w

zeł

główny [3] nie jest wi

kszy od w

zła

[6], który jest jego potomkiem.
Równie

warunek kopca nie jest

spełniony dla w

zła [1].

W tym drzewie binarnym wyst

puj

identyczne elementy. Jednak teraz
warunek kopca jest spełniony -
ka

dy w

zeł potomny jest mniejszy

(lub równy) od swojego przodka.

Zwró

uwag

, i

uporz

dkowanie elementów w kopcu nie gwarantuje uporz

dkowania w

odwzorowuj

cym go zbiorze. Przykładowo podany kopiec ma w tablicy reprezentacj

{ 9 8 6 1 3 4 } i

nie jest uporz

dkowany.

Tworzenie kopca

Kopiec tworzymy podobnie jak zwykłe

drzewo binarne

- doł

czamy elementy na ko

cu struktury.

Jednak tutaj musimy sprawdza

, czy po doł

czeniu kolejnego li

cia zostaje zachowana struktura

kopca. Je

li po doł

czeniu elementu jest on wi

kszy od swojego przodka, to musimy elementy te

zamieni

miejscami

. Nast

pnie przenosimy si

na wy

szy poziom struktury drzewa i sprawdzamy, czy

wymieniony przodek jest mniejszy od swojego przodka. Je

li nie, to znów wymieniamy elementy i

przechodzimy na poziom wy

szy. Działanie te kontynuujemy, a

do momentu spełnienia warunku

kopca (przodek wi

kszy od potomka ze wzgl

du na funkcj

porównuj

) lub po osi

gni

ciu korzenia

kopca. Poni

ej prezentujemy odpowiedni przykład.

Przykład

Utworzymy kopiec z nast

puj

cego zbioru elementów: { 3 2 7 4 9 5 }. W kopcu okre

limy porz

dek

rosn

cy - przodek ma warto

ść

ksz

lub równ

warto

ci ka

dego ze swoich potomków.

Korzeniem kopca b

dzie pierwszy element zbioru - liczba

Do korzenia doł

czamy nast

pny element - liczb

. Poniewa

potomek jest mniejszy

od swojego przodka, wi

c warunek kopca został zachowany po doł

czeniu i nie

musimy wymienia

elementów.

Pobieramy kolejny element ze zbioru - liczb

i doł

czamy go na ko

cu kopca. Po

doł

czeniu warunek kopca nie jest spełniony - potomek wi

kszy od przodka. Musimy

dokona

wymiany elementów

Po wymianie otrzymujemy drzewo trójelementowe. w którym spełniony jest warunek
kopca.

Doł

czamy kolejny element - liczb

. Warunek kopca nie jest spełniony, wi

wymieniamy go z jego przodkiem.

spełnia warunek kopca.

Doł

czamy na spodzie kopca kolejny element zbioru - liczb

. Warunek kopca nie

jest spełniony, musimy dokona

wymiany potomka z przodkiem, czyli liczb

Po wymianie przesuwamy si

na wy

szy poziom i sprawdzamy warunek kopca. Nie

jest spełniony, wymieniamy potomka z przodkiem, czyli liczby

Po tej zamianie warunek kopca jest spełniony we wszystkich w

złach.

Doł

czamy na spodzie kopca nast

pny element ze zbioru - liczb

. Warunek kopca

nie jest spełniony, wymieniamy potomka z przodkiem.

Po wymianie warunek kopca jest spełniony dla ka

dego w

zła. Poniewa

wyczerpali

my wszystkie elementy zbioru wej

ciowego, kopiec jest gotowy. Je

odwzorujemy go w ci

g elementów, otrzymamy zbiór { 9 7 5 2 4 3 }.

Tworzenie kopca jest operacj

zło

ono

ci obliczeniowej

klasy O(n). Oznacza to, i

np.

dziesi

ciokrotny wzrost liczby elementów powoduje dziesi

ciokrotny wzrost czasu budowania kopca.

Zwró

cie uwag

, i

przy wstawianiu nowych elementów wykonujemy niewiele operacji porówna

przestawie

- maksymalnie tyle, ile wynosi liczba poziomów drzewa binarnego, która wyra

a si

prostym wzorem:

liczba poziomów = [log

(n)], n - liczba elementów-w

złów kopca.

Schemat blokowy tworzenia kopca

Kopiec zostanie utworzony poprzez odpowiednie przegrupowanie elementów zbioru. Taki sposób
działania nazywamy tworzeniem kopca na miejscu - operacja ta nie wymaga dodatkowych zasobów
komputera, wykorzystujemy obszar zaj

ty przez elementy zbioru.

Naszym zadaniem jest utworzenie kopca ze zbioru elementów { a

, a

, ..., a

n-1

, a

}, które nie s

posortowane w

adnym porz

dku. Kolejno

ść

elementów w w

złach kopca definiujemy za pomoc

funkcji porz

dkowej

. Problem mo

na rozwi

na dwa sposoby - rekurencyjnie lub iteracyjnie. Ja

wybrałem rozwi

zanie iteracyjne - czytelnik niech zastanowi si

nad sposobem rekurencyjnym.

liczba elementów w zbiorze

a[...] element zbioru o numerze od 1 do n, podanym w klamrach kwadratowych

i , j

zmienne u

ywane na liczniki p

tli

zmienna tymczasowa u

ywana przy wymianie zawarto

ci elementów tablicy

Tworzenie kopca rozpoczynamy od elementu drugiego. Pierwszy element zbioru

automatycznie jest korzeniem kopca i nie musimy go nigdzie przemieszcza

Zmienna i wskazuje kolejne elementy umieszczane w kopcu. Zmienna j

przechowuje indeksy kolejno sprawdzanych w

złów.

Po wstawieniu elementu do kopca na pozycji j-tej,
sprawdzamy, czy w

zeł ten ma przodka. Sytuacja

taka wyst

pi dla wszystkich w

złów o indeksie

kszym od 1. Indeks 1 wskazuje korze

, który nie

posiada przodka i w takim przypadku wychodzimy z
p

tli.

li w

zeł posiada przodka, to sprawdzamy, czy

zachodzi pomi

dzy potomkiem a przodkiem warunek

kopca: fp(potomek,przodek)=true. Je

li tak, to

wychodzimy z p

tli i wstawiamy kolejny element a

wyczerpania zbioru. Je

li warunek kopca nie jest

spełniony, to musimy wymieni

ze sob

potomka i

przodka, a nast

pnie przej

ść

na wy

szy poziom

struktury do w

zła przodka i dokona

znów

sprawdzenia warunku kopca. Operacje te wykonuje p

tla

lewa. P

tla prawa wstawia do kopca kolejne elementy.

Rozbiór kopca

W poprzednim rozdziale pokazali

my sposób tworzenia kopca ze zbioru ponumerowanych

elementów. Teraz zajmiemy si

drug

bardzo wa

operacj

- rozbiorem kopca. Rozbiór kopca

rozpoczynamy od jego korzenia, który zast

pujemy ostatnim elementem w kopcu. Operacja ta

powoduje zaburzenie struktury kopca, któr

musimy odtworzy

. Dokonujemy tego porównuj

c nowo

utworzony w

zeł z najwi

kszym potomkiem. Je

li warunek kopca nie jest zachowana, to dokonujemy

zamiany przodka z potomkiem. Nast

pnie przechodzimy na miejsce zamienionego potomka i

kontynuujemy porównywanie, a

dojdziemy do spodu kopca lub stwierdzimy zachowanie warunku

kopca. Poni

ej przedstawiamy odpowiedni przykład:

Przykład

Naszym zadaniem jest rozebranie kopca przez kolejne pobieranie korzenia. Po pobraniu struktura
kopca musi by

przywrócona. Oto nasz kopiec do rozbioru:

Usuwamy z kopca korze

- liczb

9. Na to miejsce wstawiamy ostatni

element - liczb

3. Technicznie operacj

tak

realizujemy wymieniaj

miejscami korze

z ostatnim li

ciem kopca i zmniejszaj

c o 1 jego długo

ść

Po wstawieniu do korzenia ostatniego li

cia struktura kopca jest zaburzona

- korze

nie jest ju

najwi

kszym elementem. Musimy wi

c odtworzy

kopiec. Korze

porównujemy z jego potomkami - liczby 7 i 5. Dokonujemy

wymiany z najwi

kszym w

złem potomnym, czyli liczb

Po dokonaniu wymiany przenosimy si

do zmienionego w

zła i dalej

sprawdzamy warunek kopca - nie zachodzi, wi

c wymieniamy przodka

(liczba 3) z najwi

kszym potomkiem (liczba 4).

Po tej operacji kopiec został zrekonstruowany i wszystkie w

zły spełniaj

jego warunek.

Usuwamy korze

zast

puj

c go najmłodszym li

ciem.

Warunek kopca nie jest spełniony - wymieniamy korze

z najwi

kszym

potomkiem. Poniewa

wymieniony w

zeł nie ma ju

potomków, operacja

odtwarzania warunków kopca została zako

czona.

7 9

Usuwamy korze

i zast

pujemy go ostatnim li

ciem kopca.

Warunek kopca nie jest spełniony - wymieniamy przodka z najwi

kszym

potomkiem.

5 7 9

Usuwamy korze

, zast

pujemy go ostatnim li

ciem.

4 5 7 9 Usuwamy korze

, zast

pujemy go ostatnim li

ciem.

3 4 5 7 9 Usuwamy ostatni w

zeł kopca - rozbiór zako

czony.

Zwró

uwag

na usuwane z kopca elementy. Je

li ustawimy je w odwrotnej kolejno

ci, to utworz

posortowany zgodnie z kryterium

funkcji porównuj

cej

Schemat blokowy rozbioru kopca

Zakładamy, i

kopiec jest utworzony w zbiorze

ponumerowanych elementów { a

, ... ,a

}. W wyniku

działania algorytmu usuwane z kopca elementy b

wstawiane na kolejne od ko

ca pozycje w zbiorze.

Pozycje te s

zajmowane przez najmłodszy li

ść

kopca,

który przenosimy do korzenia, wi

c zajmowane miejsce

ulega zwolnieniu. Po wykonaniu wszystkich operacji
rozbioru elementy zbioru b

posortowane rosn

zgodnie z kryterium

funkcji porównuj

cej

liczba elementów w zbiorze

a[...] element zbioru o numerze od 1 do n, podanym w klamrach kwadratowych

i , j, k zmienne u

ywane na liczniki p

tli

zmienna tymczasowa u

ywana przy wymianie zawarto

ci elementów tablicy

Zmienna i b

dzie wskazywa

miejsce w zbiorze, do którego wstawiamy pobrany z kopca element.

Dodatkowa funkcja tej zmiennej to okre

lanie długo

ci kopca, która jest zawsze o 1 mniejsza od

aktualnej zawarto

ci zmiennej i.

Rozpoczynamy od ostatniego miejsca w zbiorze. Element z tej pozycji zostaje wymieniony z
korzeniem kopca. Poniewa

korze

kopca zawiera najwi

kszy element, to na ko

cu zbioru b

dzie

tworzony ci

g posortowanych elementów.

Po wymianie sprawdzamy warunek kopca. Najpierw znajdujemy najwi

kszego potomka - wskazuje go

zmienna k. Je

li potomek istnieje i jest wi

kszy od przodka, to zamieniamy ze sob

te w

zły i

przechodzimy do sprawdzania warunku kopca dla wymienionego potomka i jego w

złów potomnych.

li w

zeł nie posiada potomków lub jest dla nich spełniony warunek kopca, to wychodzimy z p

tli

wewn

trznej i przechodzimy do pobrania z kopca kolejnego elementu.

Operacje te s

kontynuowane a

cały kopiec zostanie rozebrany. Wtedy zbiór b

dzie posortowany

rosn

co zgodnie z kryterium

funkcji porównuj

cej

Poni

ej przedstawiamy realizacj

opisanego algorytmu sortowania w ró

nych j

zykach

programowania. Program tworzy dwie tablice o identycznej zawarto

ci, wypełnione przypadkowymi

liczbami. Nast

pnie jedn

z tych tablic sortuje i wy

wietla obie dla zobrazowania efektu posortowania

danych.

Sortowanie z wykorzystaniem kopca

li prze

ledzili

cie dokładnie opisane powy

ej rozdziały, to powinni

cie ju

bez trudu poda

zasad

sortowania z wykorzystaniem struktury kopca. Algorytm jest wr

cz banalny i opiszemy go słownie tak:

Utwórz kopiec z elementów zbioru, który chcesz posortowa

Rozbierz kopiec wstawiaj

c elementy do sortowanego zbioru

Zbiór jest posortowany.

Algorytm sortowania poprzez kopcowanie (ang. Heap Sort) nale

y do klasy zło

ono

ci obliczeniowej

O(n log

n), co oznacza, i

nadaje si

on do porz

dkowania du

ych zbiorów danych. Sortowanie jest

wykonywane nieporównywalnie szybciej w stosunku do opisanych poprzednio algorytmów sortuj

cych

klasy O(n

). Drug

jego zalet

jest to, i

jak widzieli

my, nie wymaga on stosowania dodatkowych

struktur danych - kopiec tworzony jest w miejscu zajmowanym przez sortowany zbiór - jest to bardzo
istotna zaleta ze wzgl

du na zaj

ść

pami

ci operacyjnej komputera.

Przykład w C++

Wszystkie prezentowane tutaj przykłady zostały uruchomione w

DevC++

, który mo

na darmowo i

legalnie pobra

poprzez sie

Internet.

#include <stdlib.h>

#include <time.h>
#include <iostream.h>

    };

// wyświetlamy wyniki

    cout << "Sortowanie przez kopcowanie" << endl
         << "(C)2003 mgr Jerzy Walaszek" << endl << endl
         << "  lp    przed       po" << endl
         << "------------------------" << endl;
    for(i = 0; i < n; i++)
    {
        cout.width(4); cout << i + 1;
        cout.width(9); cout << b[i];
        cout.width(9); cout << a[i] << endl;
    };
    cout << endl;
    cout.flush();
    system("pause");
    return 0;
}

Sortowanie Szybkie

Quick Sort

Sortowanie szybkie jest najszybszym z algorytmów sortuj

cych nale

Ŝą

cych do klasy

zło

ono

obliczeniowej

O( n log

n), chocia

w pewnych niekorzystnych przypadkach, algorytm ten mo

e sta

niestabilny. Zasada jego działania jest bardzo prosta, lecz trudna w implementacji. Ze zbioru

wej

ciowego wybieramy jeden element, który dalej b

dziemy nazywa

elementem

rodkowym.

Nast

pnie reszt

elementów dzielimy na dwa podzbiory - w lewym b

wszystkie elementy równe lub

mniejsze od

rodkowego, a w prawym wszystkie elementy wi

ksze od

rodkowego. Kolejno

ść

elementów wyznacza oczywi

cie

funkcja porównuj

wg nast

puj

cej reguły:

D - zbiór sortowany
L - podzbiór lewy
P - podzbiór prawy
p - element

rodkowy nale

Ŝą

cy do D

a - dowolny element zbioru D, ró

ny od p

D = L

∪

{ p }

∪

∈

⇔

fp(a,p) = true

∈

⇔

fp(p,a) = true

li element a jest równy p (co mo

e si

zdarzy

w zbiorach dopuszczaj

cych identyczne elementy),

to nie ma znaczenia, w którym z podzbiorów go umie

cimy (zwykle b

dzie to lewy podzbiór).

W nast

pnym kroku identycznie sortujemy ka

dy z podzbiorów L i P otrzymuj

c kolejne podzbiory.

Operacj

wykonuje si

rekurencyjnie wywołuj

c procedur

szybkiego sortowania z danym

podzbiorem. Sortowanie jest kontynuowane, a

sortowany podzbiór jest pusty lub zawiera tylko jeden

element. Po zło

eniu wszystkich podzbiorów w jeden otrzymujemy zbiór posortowany zgodnie z

kryterium funkcji porównuj

cej.

Przy sortowaniu bardzo istotny jest wybór elementu

rodkowego, który posłu

y do podzielenia zbioru

na dwa podzbiory. Je

li element ten b

dzie wybrany nieprawidłowo, to efektywno

ść

algorytmu

spadnie, nawet do poziomu O(n

) dla niektórych typów danych wej

ciowych - nale

y sobie zdawa

tego spraw

przy stosowaniu algorytmu szybkiego sortowania. Zwykle zaleca si

przypadkowy wybór

jednego z elementów zbioru, jednak taka implementacja algorytmu jest nieco kłopotliwa dla
pocz

tkuj

cych adeptów sztuk programowania. My zastosujemy inny sposób - jako element

rodkowy

dziemy wybiera

ostatni element sortowanego zbioru - jest to dobre rozwi

zanie, o ile zbiór

wej

ciowy nie jest wst

pnie posortowany w kolejno

ci odwrotnej, wtedy mog

kłopoty!. Podzbiory

budowane w zbiorze sortowanym, co znakomicie zaoszcz

dzi wykorzystywan

przez algorytm

pami

ęć

operacyjn

komputera.

Przykład

Posortujemy t

metod

zbiór dziesi

ciu liczb: { 9 7 4 5 0 6 3 2 1 8 } w porz

dku rosn

cym. Nasza

funkcja porównuj

przyjmie wi

c posta

relacji mniejszy lub równy.

{ 9 7 4 5 0 6 3 2 1

}

Na element

rodkowy wybieramy ostatni element zbioru

- liczb

{ 7 4 5 0 6 3 2 1 }

{

}

Zbiór

dzielimy

dwa

podzbiory

zawieraj

odpowiednio

elementy

mniejsze

ksze

wybranego elementu

rodkowego. Prawy podzbiór jest

posortowany, poniewa

zawiera tylko jeden element

- liczb

9. Przechodzimy do sortowania lewego zbioru.

{ 7 4 5 0 6 3 2

}{

8 9

}

Wybieramy ostatni element - liczb

{

}

{7 4 5 6 3 2 }{

8 9

}

Dzielimy zbiór wg wybranego elementu

rodkowego na

dwa podzbiory. Podzbiór lewy jest ju

posortowany,

poniewa

zawiera tylko jeden element - liczb

{

0 1

}{7 4 5 6 3

}{

8 9

}

Wybieramy w podzbiorze prawym element

rodkowy -

liczb

{

0 1

}{ }

{ 7 4 5 6 3 }{

8 9

}

Dokonujemy podziału zbioru na dwa podzbiory

wzgl

dem wybranego elementu. Lewy podzbiór jest

teraz pusty.

{

0 1 2

}{ 7 4 5 6

}{

8 9

}

Wybieramy element

rodkowy.

{

0 1 2

}{ }

{ 7 4 5 6 }{

8 9

}

Lewy podzbiór znów pusty.

{

0 1 2 3

}{ 7 4 5

}{

8 9

}

Wybieramy element

rodkowy

{

0 1 2 3

}{ 4 5 }

{

}{

8 9

}

Prawy podzbiór jest posortowany, poniewa

zawiera

tylko jeden element.

{

0 1 2 3

}{ 4

}{

6 7 8 9

}

Wybieramy element

rodkowy

{

0 1 2 3

}{

}

{ }{

6 7 8 9

}

Lewy i prawy podzbiór posortowany.

{ 0 1 2 3 4 5 6 7 8 9 }

Poniewa

nie ma wi

cej podzbiorów, zbiór wej

ciowy

został w cało

ci posortowany.

Dzielenie zbioru na dwa podzbiory

Kluczowym elementem szybkiego sortowania jest podział zbioru na dwa podzbiory. Sprecyzujmy
zadanie nast

puj

co:

Mamy zbiór elementów { a

, a

m+1

, a

m+2

, ... , a

n-1

, a

}, gdzie indeks m okre

la pierwszy element, a

indeks n ostatni i oczywi

cie m < n. Takie okre

lenie elementów pozwoli nam w dalszej cz

ęś

opracowania sortowa

wybran

ęść

zbioru wej

ciowego. Jako element

rodkowy przyjmujemy

pocz

tkowo element ostatni o indeksie n, czyli p = n. Element ten posłu

y do wyznaczenia dwóch

podzbiorów - lewego o indeksach mniejszych od p z elementami mniejszymi od

rodkowego oraz

prawego o indeksach wi

kszych od p z elementami wi

kszymi. Celem naszego algorytmu b

dzie

uzyskanie takiego podziału zbioru wej

ciowego.

Umówmy si

co do sposobu oznaczania tych podzbiorów. Zrobimy to przy pomocy trzech liczb

okre

laj

cych indeksy:

indeks

pierwszego

elementu

warto

ść

stała

indeks

ostatniego

element

warto

ść

stała

p - indeks elementu

rodkowego - warto

ść

zmienna

Przy tej umowie elementy nale

Ŝą

ce do lewego podzbioru (elementy mniejsze od

rodkowego) b

miały indeksy od m do p-1. Zbiór ten jest pusty, je

li m = p. Indeksy prawego podzbioru (elementy

ksze od

rodkowego) b

miały indeksy od p+1 do n. Zbiór ten jest pusty, gdy p = n:

{

m+1

...,

p-2

p-1

gdy

L = { }, gdy m = p

{

p+1

p+2

...

n-1

gdy

P = { }, gdy p = n

Podział zbioru rozpoczynamy od elementu przedostatniego o indeksie n-1 (element ostatni jest
elementem

rodkowym). Element ten wyjmujemy ze zbioru (zapami

tujemy go w zmiennej

pomocniczej). Jego pozycja jest teraz zwolniona (tzn. mo

e zosta

zapisana bez utraty poprzedniej

zawarto

ci, któr

przechowuje zmienna pomocnicza). Nast

pnie porównujemy wyj

ty element z

elementem

rodkowym. Je

li jest on mniejszy lub równy elementowi

rodkowemu wg

funkcji

porównuj

cej

, to wstawiamy go z powrotem do zbioru (innymi słowy nic z nim nie robimy). W

przeciwnym przypadku przesuwamy w lewo o 1 pozycj

wszystkie elementy pocz

wszy od

nast

pnego i sko

czywszy na elemencie

rodkowym. W wyniku tej operacji po prawej stronie

elementu

rodkowego zwalnia si

miejsce, w którym umieszczamy element wybrany (przepisujemy go

ze zmiennej pomocniczej). Indeks elementu

rodkowego zmniejszamy o 1. Nad kolejnymi w dół

elementami zbioru wykonujemy identyczne operacje a

dojdziemy do elementu o indeksie m. Wtedy

zbiór wej

ciowy zostanie podzielony na dwa podzbiory. Oto odpowiedni przykład:

Przykład

Podzielimy zbiór wej

ciowy { 3 2 8 6 4 7 5 } na dwa podzbiory - lewy z liczbami mniejszymi od

elementu ostatniego - 5 oraz prawego z liczbami wi

kszymi od tej warto

ci.

{ 3 2 8 6 4 7

}

Elementem

rodkowym podziału jest ostatni element zbioru wej

ciowego -

liczba 5.

{ 3 2 8 6 4 ^

}

Ze zbioru wyjmujemy przedostatni element - liczb

7 i porównujemy j

elementem

rodkowym.

{ 3 2 8 6 4

^ }

Poniewa

liczba ta jest wi

ksza od elementu

rodkowego, dokonujemy

przesuni

cia o 1 pozycj

w lewo wszystkich elementów pocz

wszy od

nast

pnego (tutaj nie wyst

puje) a sko

czywszy na elemencie

rodkowym.

Indeks p jest zmniejszany o 1, aby wskazywał now

pozycj

elementu

rodkowego w zbiorze. Po prawej stronie utworzyło si

w wyniku przesuni

cia

puste miejsce.

{ 3 2 8 6 4

}

W miejsce to wstawiamy wybrany poprzednio element - liczb

{ 3 2 8 6 ^

}

Wybieramy kolejny w dół element zbioru - liczb

4 i porównujemy j

elementem

rodkowym. Poniewa

liczba 4 jest mniejsza od 5, pozostawiamy

na swoim miejscu.

{ 3 2 8 ^

}

Wybieramy kolejny w dół element i porównujemy go z elementem

rodkowym.

{ 3 2 8

}

Poniewa

6 jest wi

ksze od elementu

rodkowego, przesuwamy w lewo o 1

pozycj

wszystkie elementy nast

pne do elementu

rodkowego wł

cznie.

Indeks p jest zmniejszany o 1.

{ 3 2 8

6 7

}

Na zwolnionym miejscu po prawej stronie elementu

rodkowego wstawiamy

liczb

{ 3 2 ^

6 7

}

Przechodzimy do nast

pnego w dół elementu zbioru - liczby 8 i porównujemy

z elementem

rodkowym - liczb

{ 3 2

6 7

}

Poniewa

8 jest wi

ksze od 5, przesuwamy w lewo o 1 pozycj

elementy od

nast

pnego do

rodkowego wł

cznie. Indeks p jest zmniejszany o 1.

{ 3 2

8 6 7

}

Na zwolnione miejsce wstawiamy liczb

{ 3 ^

8 6 7

}

Liczb

2 pozostawiamy na swojej pozycji, poniewa

jest mniejsza od

elementu

rodkowego.

{ ^

8 6 7

}

To samo dotyczy liczby 3.

{

3 2 4

8 6 7

}

Zbiór wej

ciowy został podzielony na dwa podzbiory : L = { 3 2 4 } z

elementami mniejszymi od 5 oraz P = { 8 6 7 } z elementami wi

kszymi od 5.

Z podobnymi operacjami spotkali

my si

w algorytmie

sortowania przez wstawianie

Schemat blokowy podziału podziału zbioru na dwa podzbiory

Dany jest zbiór { a

m+1

m+2

...a

n-2

n-1

}, który nale

y podzieli

na dwa podzbiory wzgl

dem

elementu

rodkowego a

. Porz

dek wyznacza

funkcja porównuj

fp(...). Do opisu algorytmu

stosujemy nast

puj

ce zmienne:

indeks pierwszego elementu zbioru wej

ciowego

indeks ostatniego elementu zbioru wej

ciowego

indeks elementu

rodkowego

zmienna pomocnicza do przechowywania warto

ci tymczasowych

i,j

zmienne liczników p

tli

a[...] element zbioru o podanym indeksie

Punkt podziałowy p znajduje si

na ko

cu zbioru. Do zmiennej p

wprowadzamy wi

c indeks ostatniego elementu zbioru. Nast

pnie

dziemy przegl

kolejno w dół wszystkie elementy o indeksach od

n-1 do m i porównywa

je z elementem

rodkowym a[p]. Je

li b

one wi

ksze ze wzgl

du na

funkcj

porównuj

, to dokonamy

odpowiedniego przesuni

cia elementów w lewo i wstawienia

porównywanego

elementu

element

rodkowy.

Indeks

porównywanych elementów przechowuje zmienna i. Na pocz

tku

wpisujemy do niej indeks przedostatniego elementu, czyli n-1.

Przed wykonaniem kolejnego obiegu p

tli zewn

trznej sprawdzamy,

czy indeks mie

ci si

w zakresie. Je

li nie, to ko

czymy.

li indeks i mie

ci si

w zakresie (jest wi

kszy lub równy m), to

sprawdzamy funkcj

porównuj

kolejno

ść

elementów a[i] oraz a[p].

li a[i] ma by

po prawej stronie a[p], to zawarto

ść

elementu a[i]

trafia do zmiennej pomocniczej t, a wszystkie elementy od indeksu i +
1 do p wł

cznie zostaj

przesuni

te o 1 pozycj

w lewo. Dzi

ki tej

operacji element o indeksie p zostaje zwolniony - oryginalny element

rodkowy a[p] jest teraz na pozycji o 1 mniejszej, czyli a[p-1].

Do zwolnionego elementu a[p] wpisujemy zawarto

ść

zmiennej

pomocniczej, czyli oryginalny element a[i].

Indeks p zmniejszamy o 1, aby prawidłowo wskazywał pozycj

elementu

rodkowego.

Przechodzimy do kolejnego w dół elementu zbioru i kontynuujemy p

zewn

trzn

Algorytm Sortowania Szybkiego

Procedura sortowania szybkiego jest procedur

rekurencyjn

z parametrami okre

laj

cymi zakres

indeksów sortowanego zbioru. Rekurencja ma to do siebie, i

procedura (lub funkcja) wywołuje sam

siebie. Takie wywołanie powoduje przesłanie na stos wszystkich argumentów procedury podanych w
wywołaniu. Nowy egzemplarz tej procedury b

dzie wi

c pracował z niezale

nym zestawem danych.

Algorytm sortuj

cy mo

emy opisa

słownie tak:

1. Procedura QSrt(ip,ik) - parametry ip i ik okre

laj

indeksy pierwszego i ostatniego

elementu do sortowania w zbiorze wej

ciowym i s

przekazywane poprzez stos.

2. Podziel zadany zbiór wej

ciowy na dwa podzbiory wzgl

dem ostatniego elementu,

który b

dzie elementem

rodkowym podziału. W lewym podzbiorze umie

ść

wszystkie

elementy mniejsze lub równe elementowi

rodkowemu. W prawym podzbiorze umie

ść

wszystkie elementy wi

ksze od elementu

rodkowego.

3. Je

li lewy podzbiór ma wi

cej ni

jeden element, to wywołaj procedur

QSrt(ip,p-1).

Nowy egzemplarz procedury b

dzie pracował z parametrami ip' = ip oraz ik' = p-1

4. Je

li prawy podzbiór ma wi

cej ni

jeden element, to wywołaj procedur

QSrt(p+1,ik).

Nowy egzemplarz procedury b

dzie pracował z parametrami ip' = p + 1 oraz ik' = ik.

5. Zako

cz działanie procedury

li chcemy posortowa

cały zbiór { a

... a

n-1

}, to w programie nale

y wywoła

procedur

jako

QuickSort(1,n). Wywołanie to zainicjuje kolejne podziały zbioru a

do jego posortowania.

Poni

ej przedstawiamy realizacj

opisanego algorytmu sortowania w ró

nych j

zykach

programowania. Program tworzy dwie tablice o identycznej zawarto

ci, wypełnione przypadkowymi

liczbami. Nast

pnie jedn

z tych tablic sortuje i wy

wietla obie dla zobrazowania efektu posortowania

danych.

    for(i = 0; i < n; i++ ) a[i] = b[i] = 1 + rand() % (n + n);

// wywołujemy funkcję szybkiego sortowania z pełnym zakresem indeksów

    qsrt(0,n-1,&a[0]);

// wyświetlamy wyniki

    cout << "Sortowanie szybkie" << endl
         << "(C)2003 mgr Jerzy Walaszek" << endl << endl
         << "  lp    przed       po" << endl
         << "------------------------" << endl;
    for(i = 0; i < n; i++)
    {
        cout.width(4); cout << i + 1;
        cout.width(9); cout << b[i];
        cout.width(9); cout << a[i] << endl;
    };
    cout << endl;
    cout.flush();
    system("pause");
    return 0;
}

Wyszukiwanie Binarne

Binary Search

Wyszukiwanie danych jest zagadnieniem spokrewnionym z sortowaniem. Je

li zbiór nie jest

posortowany i chcemy w nim znale

źć

element spełniaj

cy okre

lone kryterium, to musimy przegl

kolejne elementy a

natrafimy na wła

ciwy. Je

li danego elementu w zbiorze nie ma, odpowied

otrzymamy dopiero po przegl

dni

ciu całego zbioru. Przy du

ym zbiorze mo

e zaj

ąć

to nam sporo

czasu. Taki rodzaj przeszukiwania nosi nazw

liniowego i ma zło

ono

ść

obliczeniow

klasy O(n).

o efektywniejsze jest przeszukiwanie zbiorów posortowanych, gdy

wtedy nie musimy sprawdza

wszystkich elementów, lecz mo

emy skorzysta

z własno

ci tej, i

kolejne elementy zbioru s

umieszczone w nim zgodnie z okre

lonym porz

dkiem (zdefiniowanym np. przez

funkcj

porównuj

). Dla takich zbiorów mo

na zastosowa

algorytm wyszukiwania binarnego. Zasada jest

nast

puj

ca. W zbiorze wybieramy element

rodkowy. Poniewa

zbiór jest posortowany, to mamy

pewno

ść

, i

na lewo s

elementy mniejsze (lub równe), a na prawo s

elementy wi

ksze wg funkcji

porównuj

cejj. Sprawdzamy, czy element ten spełnia kryteria poszukiwa

. Je

li tak, to ko

czymy

(tylko jedno porównanie!). Je

li nie, to sprawdzamy, czy element

rodkowy jest wi

kszy lub mniejszy

od poszukiwanego. Je

li jest wi

kszy, to poszukiwany element znajduje si

w lewej połówce.

Analogicznie je

li element

rodkowy jest mniejszy, to poszukiwany element b

dzie si

znajdował w

prawej połówce. Wybieramy wi

c jedn

z połówek za nowy zbiór do przeszukania. Jest on o połow

mniej liczny od zbioru wyj

ciowego. Cał

operacj

powtarzamy z połówk

zbioru. Je

li nie znajdziemy

poszukiwanego elementu, to znów dostaniemy dwie połówki - czterokrotnie mniejsze od zbioru
wyj

ciowego. Wybieramy jedn

z nich zgodnie z podan

reguł

i kontynuujemy a

do znalezienia

elementu lub otrzymania połówek, których ju

dalej nie mo

na dzieli

- wtedy wiemy,

poszukiwanego elementu w zbiorze nie ma.

Zwró

uwag

, i

po ka

dym porównaniu liczebno

ść

zbioru maleje o połow

. Umo

liwia to szybkie i

efektywne wyszukanie elementu nawet w olbrzymim zbiorze danych. Oto odpowiedni przykład.

Przykład

Chcemy wyszuka

za pomoc

opisanego algorytmu liczb

14 w zbiorze { 2 3 5 6 7 9 10 14 16 25 30 }.

1 2 3 4 5

7 8 9 10 11

{ 2 3 5 6 7

10 14 16 25 30 }

Najpierw znajdujemy element

rodkowy. Mo

emy obliczy

jego indeks jako

redni

arytmetyczn

indeksu pierwszego i

ostatniego elementu zbioru. Oczywi

cie wynik zaokr

glamy

do warto

ci całkowitej. (1+11)/2 = 6. Szóstym elementem

jest liczba 9, któr

oznaczyli

my na czerwono.

1 2 3 4 5

7 8 9 10 11

{ 2 3 5 6 7

10 14 16 25 30 }

14...............

Teraz sprawdzamy, czy element

rodkowy jest równy

poszukiwanemu. U nas nie jest. Skoro nie jest równy, to
musi by

kszy lub mniejszy od poszukiwanego. U nas

jest mniejszy, wi

c dalsze poszukiwania b

dziemy

prowadzi

w prawej połówce.

1 2 3 4 5 6 7 8

10 11

{

2 3 5 6 7 9

10 14

25 30 }

Obliczamy nowy indeks elementu

rodkowego, który jest

równy: (7+11)/2 = 9. Element

rodkowy zaznaczyli

my na

czerwono. Jest to liczba 16.

1 2 3 4 5 6 7 8

10 11

{

2 3 5 6 7 9

10 14

25 30 }

.......

Sprawdzamy, czy poszukiwany element jest równy
elementowi

rodkowemu. Nie jest. Element

rodkowy jest

kszy, wi

c przenosimy si

do lewej połowy.

1 2 3 4 5 6

8 9 10 11

{

2 3 5 6 7 9

16 25 30

}

Indeks elementu

rodkowego = (7+8)/2 = 7. Jest to liczba

10 zaznaczona na czerwono.

1 2 3 4 5 6

8 9 10 11

{

2 3 5 6 7 9

16 25 30

}

14....

Porównujemy. Element

rodkowy jest mniejszy, przenosimy

do prawej połówki.

1 2 3 4 5 6 7

9 10 11

{

2 3 5 6 7 9 10

16 25 30

}

Znajdujemy element

rodkowy - (8+8)/2 = 8. Jest to liczba

14. Porównanie da teraz wynik pozytywny.

Ile operacji porówna

wykonano? Cztery. A wi

c bardzo szybko znale

my pozycj

elementu w

zbiorze posortowanym. Teraz zobaczmy, co si

dzieje, gdy poszukiwanego elementu w zbiorze nie

ma. Spróbujemy znale

źć

w tym samym zbiorze danych liczb

1 2 3 4 5 6 7 8 9 10 11

{ 2 3 5 6 7

10 14 16 25 30 }

Znajdujemy

element

rodkowy.

Indeks = (1+11)/2 = 6

1 2 3 4 5 6 7 8 9 10 11

{ 2 3 5 6 7

10 14 16 25 30 }

...........

Element

rodkowy wi

kszy od poszukiwanej liczby,

przenosimy si

do lewej połówki zbioru.

1 2 3 4 5 6 7 8 9 10 11

{ 2 3

6 7

9 10 14 16 25 30

}

Znajdujemy

element

rodkowy.

Indeks = (1+ 5)/2 = 3

1 2 3 4 5 6 7 8 9 10 11

{ 2 3

6 7

9 10 14 16 25 30

}

.....

Element

rodkowy wi

kszy. Wybieramy lew

połówk

1 2 3 4 5 6 7 8 9 10 11

{

5 6 7 9 10 14 16 25 30

}

Znajdujemy

element

rodkowy.

Indeks = (1+2)/2 = 1

1 2 3 4 5 6 7 8 9 10 11

{

5 6 7 9 10 14 16 25 30

}

4...

Element

rodkowy mniejszy od poszukiwanego. Wybieramy

praw

połówk

1 2 3 4 5 6 7 8 9 10 11

{

5 6 7 9 10 14 16 25 30

}

Znajdujemy

element

rodkowy:

Indeks = (2+2)/2 = 2.

1 2 3 4 5 6 7 8 9 10 11

{

5 6 7 9 10 14 16 25 30

}

Element

rodkowy mniejszy od poszukiwanego. Poniewa

zbiór jest jednoelementowy, to nie mo

na go ju

podzieli

na dwie rozł

czne połowy. Przeszukanie zostaje wi

zako

czone z wynikiem negatywnym - poszukiwanego

elementu w zbiorze nie ma.

Ile wykonano porówna

? Cztery. Poniewa

zbiór po ka

dym porównaniu jest dzielony na coraz

mniejsze podzbiory, to maksymalna liczba porówna

w n-elementowym zbiorze posortowanym

wyniesie nie wi

cej ni

|log

n|+1. Wobec tego mo

emy oszacowa

zło

ono

ść

obliczeniow

algorytmu

wyszukiwania binarnego na O(log

n). Jest to zło

ono

ść

mniejsza od liniowej O(n), a wi

c bardzo

korzystna (np. szesnastokrotny wzrost liczby danych powoduje jedynie czterokrotny wzrost czasu
wyszukiwania).

Schemat blokowy

Dany jest zbiór { a

...a

n-2

n-1

} oraz element x, który nale

y w zbiorze odszuka

. Zbiór jest

posortowany zgodnie z kryterium zdefiniowanym przez

funkcj

porównuj

. Do opisu algorytmu

stosujemy nast

puj

ce zmienne:

liczba elementów w zbiorze

a[...] element zbioru o numerze od 1 do n podanym w klamrach kwadratowych

zmienna logiczna informuj

ca o wyniku poszukiwa

. Warto

ść

true oznacza znalezienie

elementu, warto

ść

false informuje, i

poszukiwanego elementu w zbiorze nie ma

zmienna przechowuj

ca indeks elementu

rodkowego. Po zako

czeniu działania algorytmu w

zmiennej tej znajdzie si

indeks poszukiwanego elementu, je

li f=true

poszukiwany element

ip,ik zmienne przechowuj

indeksy elementu pocz

tkowego i ko

cowego przeszukiwanych zbiorów

Zakres poszukiwa

definiuj

dwie zmienne - ip

zawieraj

ca indeks pierwszego elementu oraz ik

zawieraj

ca indeks ostatniego elementu zbioru. Na

pocz

tku algorytmu inicjujemy je odpowiednio na

pierwszy i ostatni element w zbiorze wej

ciowym.

li w trakcie działania algorytmu dojdzie do

sytuacji, gdy indeks pocz

tkowy jest wi

kszy od

cowego, to oznacza to zbiór pusty. W takim

przypadku

czymy

działanie

algorytmu

wynikiem negatywnym - poszukiwanego elementu w
zbiorze wej

ciowym nie ma - zmienna f przyjmie

warto

ść

false.

li zakres jest w porz

dku, to obliczamy indeks

elementu

rodkowego, który wyznaczy dwie połówki

zbioru.

Indeks

ten

obliczamy

jako

redni

arytmetyczn

indeksów ip oraz ik, zaokr

glon

warto

ci całkowitej.

Sprawdzamy, czy element

rodkowy o indeksie p

jest poszukiwanym elementem. Je

li tak, to

czymy z wynikiem pozytywnym - zmienna p zawiera pozycj

odszukanego elementu.

W przypadku, gdy poszukiwany element nie jest równy elementowi

rodkowemu, musi si

znajdowa

w jednej z dwóch połówek, które wyznacza element

rodkowy. Dalsze poszukiwania

dziemy prowadzi

w lewej połówce, je

li ze wzgl

du na kolejno

ść

wyznaczon

przez

funkcj

porównuj

poszukiwany element jest przed elementem

rodkowym (czyli fp(x,a[p]) = true) lub w

połówce prawej w sytuacji przeciwnej. Przy przej

ciu do połówki lewej indeks ko

cowy ustawiamy na

warto

ść

o jeden mniejsz

od indeksu p, a w prawej połówce indeks pocz

tkowy ip ustawiamy na

warto

ść

o jeden wi

ksz

od p. Eliminuje to z połówek element

rodkowy, który ju

nie musi by

brany

pod uwag

. Równie

w sytuacji, gdy która

z połówek jest zbiorem pustym, powoduje to, i

wyra

enie

ip > ik stanie si

prawdziwe i algorytm zako

czy si

z wynikiem negatywnym.

Poni

ej przedstawiamy realizacj

opisanego algorytmu wyszukiwania binarnego w ró

nych j

zykach

programowania. Przedstawiony program najpierw tworzy tablic

n przypadkowych liczb. Nast

pnie

sortuje j

metod

przez wstawianie. W wyniku posortowania w pierwszym elemencie znajduje si

warto

ść

najmniejsza, a w ostatnim najwi

ksza. Na podstawie tych dwóch warto

ci program generuje

liczb

przypadkow

wpadaj

w zakres liczb w tablicy. Za pomoc

algorytmu wyszukiwania

binarnego zostaje znaleziona pozycja wygenerowanej liczby i wyniki s

wietlane na ekranie.

Przykład w C++

Wszystkie prezentowane tutaj przykłady zostały uruchomione w

DevC++

, który mo

na darmowo i

legalnie pobra

poprzez sie

Internet.

#include <stdlib.h>

#include <time.h>

#include <iostream.h>

const int n = 10; // liczba elementów w sortowanym zbiorze

// funkcja porównuj

int fp(int x, int y)

{

return (x <= y);

}

int main()

{

int i,j,ip,ik,p,t,x,a[n];