ALGORYTMY PRZESZUKIWANIA I SORTOWANIA

Algorytmy przeszukiwania

Algorytm przeszukiwania liniowego (sekwencyjnego)

Algorytm ten jest najprostszym algorytmem znalezienia pozycji jakiejś liczby w zbiorze. Polega na tym, że każdy element zbioru porównujemy z poszukiwanym elementem.

ZADANIE 1. (Przeszukiwanie zbioru nieuporządkowanego)

Dane są dowolne liczby całkowite umieszczone w przypadkowej kolejności, w kolejno ponumerowanych komórkach oraz poszukiwana liczba x. Polecenia:

1. Narysuj schemat blokowy algorytmu, który sprawdzi, czy jest wśród nich zadana liczba
   i wypisze numer jej komórki (komórek). W przeciwnym razie wypisze komunikat o braku poszukiwanej liczby w zbiorze.

2. Do powyższego algorytmu napisz program (przeszukiwania liniowego).

3. Określ złożoność obliczeniową algorytmu.

 

Algorytm przeszukiwania binarnego

Przeszukiwanie to jest o wiele szybsze niż przeszukiwanie liniowe. Jednak algorytm ten
(w przeciwieństwie do przeszukiwania liniowego) działa tylko na posortowanych danych. Polega na porównywaniu poszukiwanego elementu ze środkowym elementem zbioru (medianą), a następnie rozpatrzeniu 3 przypadków:

1. Mediana jest równa elementowi poszukiwanemu. Koniec działania algorytmu.

2. Mediana jest mniejsza od elementu poszukiwanego. Należy powtórzyć te same czynności dla połowy zbioru zawierającej elementy większe od mediany.

3. Mediana jest większa od elementu poszukiwanego. Należy powtórzyć te same czynności dla połowy zbioru zawierającej elementy mniejsze od mediany.

ZADANIE 2. (Przeszukiwanie zbioru uporządkowanego)

Dane są dowolne liczby całkowite umieszczone w kolejno ponumerowanych komórkach uporządkowane narastająco oraz poszukiwana liczba x. Polecenia:

1. Napisz program (przeszukiwania binarnego), który sprawdzi, czy jest wśród nich zadana liczba. Jeśli tak, wypisze jej numer komórki – jeśli nie: napis „nie ma” (schemat blokowy algorytmu podany niżej).

2. Określ złożoność obliczeniową algorytmu.

Algorytmy sortowania

Sortowanie bąbelkowe

Jest to najprostsza metoda sortowania, polegająca na porównywaniu dwóch kolejnych elementów
i zamianie ich kolejności w przypadku, gdy element poprzedni jest większy od elementu następnego – jest to tzw. „wypychanie bąbelka” (większy element zostaje ciągnięty na koniec zbioru). Złożoność obliczeniowa tego algorytmu wynosi O(n²), więc jest dosyć duża.

Schemat działania algorytmu:

• porównujemy element pierwszy i drugi (w razie potrzeby zamieniamy)

• porównujemy element drugi i trzeci (w razie potrzeby zamieniamy)

• ....

• porównujemy element (n-1)-szy i n-ty (w razie potrzeby zamieniamy)

Po tym przebiegu wiemy, że na n-tej pozycji znajduje się element największy, więc nie ma potrzeby porównywać już tego elementu z innymi. Dlatego też następny przebieg kończy się na porównaniu elementu (n-2)-go i (n-1)-szego. Podobnie będzie w kolejnych przebiegach. Dla każdego kolejnego przejścia zbiór porównywanych elementów będzie o 1 mniejszy, ponieważ końcowe elementy już będą posortowane i nie ma potrzeby ich już porównywać. Sortowanie kończy się, gdy w danym przebiegu nie wykonamy żadnej zamiany.

Przykład liczbowy:

Obieg 1:

|9|8|5|1|3| -> |8|9|5|1|3| -> |8|5|9|1|3| -> |8|5|1|9|3| -> |8|5|1|3|9|

^-^ ^-^ ^-^ ^-^

Obieg 2:

|8|5|1|3|9| -> |5|8|1|3|9| -> |5|1|8|3|9| -> |5|1|3|8|9|

^-^ ^-^ ^-^

Obieg 3:

|5|1|3|8|9| -> |1|5|3|8|9| -> |1|3|5|8|9|

^-^ ^-^

Obieg 4, (n-1)-ty:

|1|3|5|8|9| (nie zamieniamy, bo kolejność jest dobra; żadnej zamiany w przebiegu –

^-^ koniec sortowania)

ZADANIE 3.

Uruchom i przeanalizuj poniższy program sortujący tablicę liczb całkowitych metodą bąbelkową.

1. Do powyższego algorytmu narysuj schemat blokowy.

2. Określ złożoność obliczeniową algorytmu.

#include <iostream>

using namespace std;

const int N=10;

int main()

{

int A[N],i,j,temp;

srand(time(NULL));

for(i=0;i<N;i++)

A[i]=rand()% 10;

for(i=0;i<N;i++)

cout<<A[i]<<"\t";

cout<<"\n";

for(j=N-1;j>0;j--)

{

for(i=0;i<j;i++)

if(A[i]>A[i+1])

{ //swap

temp=A[i];

A[i]=A[i+1];

A[i+1]=temp;

}

}

cout<<"Tablica posortowana:\n";

for(i=0;i<N;i++)

cout<<A[i]<<"\t";

cout<<"\n";

system("PAUSE");

return 0;

}

Sortowanie przez wstawianie

Algorytm dosyć efektywny dla zbiorów o niewielkiej liczebności. Metoda polega na usuwaniu pewnego elementu ze zbioru danych nie posortowanych i wstawianiu go na odpowiednie miejsce
w zbiorze danych posortowanych. Wybór następnego elementu z danych jest dowolny. Złożoność obliczeniowa tego algorytmu wynosi, podobnie jak w sortowaniu bąbelkowym, O(n²), jednakże jest metodą szybszą.

Schemat działania algorytmu:

1. Utwórz zbiór elementów posortowanych (pusty) i przenieś do niego dowolny element ze zbioru nieposortowanego.

2. Weź dowolny element ze zbioru nieposortowanego.

3. Wybrany element porównuj z kolejnymi elementami zbioru posortowanego dopóki nie napotkasz elementu niemniejszego lub nie znajdziesz się na końcu zbioru uporządkowanego i wstaw go w miejscu, w którym skończyłeś porównywać.

4. Jeżeli zbiór elementów nieuporządkowanych jest niepusty, to wróć do punktu 2.

Przykład liczbowy:

(za dowolny element przyjmuję ostatni element leżący tuż przed listą uporządkowaną).

Zbiór nieposortowany Zbiór posortowany

|9|8|5|1|3| | |

|9|8|5|1|3| |3|

^

|9|8|5|1| |1|3| -> |1|3|

^ ^-^

|9|8|5| |5|1|3| -> |1|5|3| -> |1|3|5|

^ ^-^ ^-^

|9|8| |8|1|3|5| -> |1|8|3|5| -> |1|3|8|5| -> |1|3|5|8|

^ ^-^ ^-^ ^-^

|9| |9|1|3|5|8| -> |1|9|3|5|8| -> |1|3|9|5|8| -> |1|3|5|9|8| -> |1|3|5|8|9|

^ ^-^ ^-^ ^-^ ^-^

| | |1|3|5|8|9|

ZADANIE 4.

Napisz program sortujący tablice liczb całkowitych stosując algorytm sortowania przez wstawianie (poniżej podano przykładowe rozwiązanie).

Sortowanie szybkie (ang. quick sort)

Algorytm sortowania szybkiego opiera się na strategii "dziel i zwyciężaj" (ang. divide and conquer), którą możemy krótko scharakteryzować w trzech punktach:

• Dziel - problem główny zostaje podzielony na podproblemy

• Zwyciężaj - znajdujemy rozwiązanie podproblemów

• Połącz - rozwiązania podproblemów zostają połączone w rozwiązanie problemu głównego

Idea sortowania szybkiego jest następująca:

1. najpierw sortowany zbiór dzielimy na dwie części w taki sposób, aby wszystkie elementy leżące w pierwszej części (zwanej lewą partycją) były mniejsze lub równe od wszystkich elementów drugiej części zbioru (zwanej prawą partycją) / Dziel

2. każdą z partycji sortujemy rekurencyjnie tym samym algorytmem / Zwyciężaj

3. połączenie tych dwóch partycji w jeden zbiór daje w wyniku zbiór posortowany / Połącz.

W przypadku typowym algorytm ten jest najszybszym algorytmem sortującym z klasy złożoności obliczeniowej O(n log n).

ZADANIE 5.

Przedstaw algorytm sortowania szybkiego i napisz program realizujący go.