Dr Oleksandr Klosov

Materiały dydaktyczne

Algorytmy i Struktury Danych

Wykład

ALGORYTMY SORTOWANIA

Definicja

- Sortowaniem nazywamy proces ustawiania zbioru obiektów

w określonym porządku.

Motywacja

• Ułatwić wyszukiwanie danych

Wymaganie

- Oszczędne korzystanie z pamięci

(n.p., sortując tablicę liczb nie można korzystać z dodatkowej tablicy)

1. Sortowanie w miejscu

2. Sortowanie plików

KLASYFIKACJA METOD SORTOWANIA

Sortowanie proste	Sortowanie szybkie
Proste wybieranie (selection sort) Proste wstawianie (insertion sort) Prosta zamiana (exchange sort)	Metoda Shell'a (malejących przyrostów) Scalanie ciągów Kopcowanie (stogowe, heap sort) Quicksort (sortowanie przez podział)

Zalety prostych metod:

1. Programy są krótkie, łatwe do zrozumienia, zajmują mniej pamięci

2. Są szybsze dla małej liczby elementów

3. Lepiej nadają się do wyjaśnienia zasad sortowania

SORTOWANIE metodą prostej zamiany

Bąbelkowe, O(n²)

1. Sprawdzamy całą tablicę od początku do końca, porównując zawsze dwa sąsiednie elementy

2. Jeżeli trafimy na parę elementów, w której większy poprzedza mniejszy to zamieniamy je miejscami.

3. Czynność powtarzamy tak długo aż podczas sprawdzania całej tablicy, nie zajdzie ani jedna zamiana elementów

SORTOWANIE metodą prostej zamiany

Realizacja klasyczna - C

void bubble_sort(int *tab, int n) { int i, j; int tmp; for(i=1;i<n; i++) for(j=n-1;j>=i; j=j-1) if(tab[j-1]>tab[j]) { // zamiana sąsiednich elementów tmp=tab[i-1]; tab[i-1] = tab[i]; tab[i] = tmp; } }

SORTOWANIE metodą prostej zamiany

Realizacja ze znacznikiem - C

void bubble_sort(int *tab, int n) { int zmiana; // znacznik do { zmiana = 0; // brak zmian for(int i=1;i<n; i++) if(tab[i-1]>tab[i]) { // zamiana sąsiednich elementów int tmp=tab[i-1]; tab[i-1] = tab[i]; tab[i] = tmp; zmiana = 1; // jest zmiana } } while(zmiana); }

SORTOWANIE metodą prostej zamiany

Analiza złożoności - przykład wyliczenia, przypadek najgorszy

1	void bubble_sort(int *tab, int n)
2	{ int i, j;
3	int tmp;
4	for(i=1;i<n; i++)	1+N
5	for(j=n-1;j>=i; j--)	(N-1)(1+(N+2)/2)	0.5N^2+1.5N-2
6	if(tab[j-1]>tab[j])	(N-1+1)(N-1) 0.5	0.5N^2-0.5N
7	{
8	int tmp=tab[i-1];		0.5N^2-0.5N
9	tab[i-1] = tab[i];		0.5N^2-0.5N
10	tab[i] = tmp;		0.5N^2-0.5N
11	}
12	}	T(N) = ∑ = 2.5N^2+0.5N-1
		O(N^2)

JAK POLICZYĆ ZŁOŻONOŚĆ PRAKTYCZNĄ?

void bubble_sort(int *tab, int n) { int zmiana; int po=0, pr=0; do { pr++, zmiana = 0; for(pr++, int i=1; po++, i<n; i++) if(po++, tab[i-1]>tab[i]) { pr+=4; int tmp=tab[i-1]; tab[i-1] = tab[i]; tab[i] = tmp; zmiana = 1; } } while(po++, zmiana); }

SORTOWANIE metodą prostego wybierania

SelectionSort, O(n²)

1. Wybieramy najmniejszy element tablicy

2. Wymieniamy go z pierwszym elementem

3. Powtarzamy operacje 1-2 dla pozostałych n-1 elementów, następnie dla n-2 i t.d. aż pozostanie 1 element.

SORTOWANIE metodą prostego wybierania

void proste_wybieranie(int t[], int n) { int i,j,k,min; for( i=0; i<n-1; i++) { k=i; // pozycja najmniejszego elementu min=t[i]; // najmniejszy element for( j=i+1;j<n;j++) // pętla wyznaczająca najmniejszy element if(t[j]<min) // czy kolejny element tablicy jest mniejszy? { k=j; // pamiętaj pozycję najmniejszego elementu min=t[j]; // pamiętaj wartość najmniejszego elementu } t[k]=t[i]; // wymiana pierwszego z najmniejszym t[i]=min; } }

SORTOWANIE metodą prostego wstawiania

InsertionSort, O(n²)

1. Elementy są podzielone umownie na ciąg wynikowy oraz ciąg źródłowy

2. W każdym kroku począwszy od i=2 i zwiększając i o jeden, i-ty element ciągu źródłowego przenosi się do ciągu wynikowego, wstawiając go w odpowiednie miejsce.

3. Proces przenoszenia i-go elementu kończy się kiedy:

1. znaleziono j-ty element mniejszy niż i-ty element

2. osiągnięto lewy koniec ciągu wynikowego

SORTOWANIE metodą prostego wstawiania

Realizacja - C

void proste_wstawianie(int t[], int n) { int i,j,tmp; for(i=1; i<n; i++) { j=i; // elementy 0...i-1 są posortowane tmp=t[j]; // sortowany element while((j>0) && (t[j-1]>tmp)) { t[j]=t[j-1]; // przesunięcie w prawo j--; // następny element } t[j]=tmp; // wstawienie elementu } }

DEFINCIJA FUNKCJI ZŁOŻONOŚCI ALGORYTMÓW

W przypadku danej funkcji złożoności f(n) zapis O(f(n)) znacza zbiór funkcji złożoności g(n), dla których istnieje pewna dodatnia stała rzeczywista C, oraz pewna nieujemna wartość całkowita N taka, że dla wszystkich n ≥ N zachodzi związek: g(n) ≤ C ⋅ f(n)

g(n) ∈ O(f(n) oznacza, że g(n) jest dużym O z f(n) i nazywana jest asymptotycznym ograniczeniem górnym 2n ∈ n^2 ∈ n^3 ∈ n!

Wykres funkcji o mniejszej złożoności znajduje się pod wykresem funkcji o większej złożoności przy dostatecznie dużym n

KLASYFIKACJA FUNKCJI ZŁOŻONOŚCI ALGORYTMÓW

O()	Typ złożoności	Przykłady
N	Liniowa	10n+100, 0.5n-k | k<<n
N^2	Kwadratowa	5n^2+1000n+2000
lgN	Logarytmiczna	lg(n-1)
N lg N	Liniowo - logarytmiczna	10n ln (n)
N^k	Wielomianowa	n^m+n^2+100n+10, m>2
2^n	Wykładnicza	2^n+n^2
lg ^(*) N	Logarytmiczno-iteracyjna	ln ^(3) n = ln (ln (ln n))

ZADANIE

Uporządkować roznąco następujące funkcję złożoności:

2n(ln n), n!, 1, 0.5n, (lg n)², eⁿ, 10ⁿ+n¹⁰, 2ⁿ, 2^n!, lg ⁽³⁾ n

Pokazać przykłady następujących funkcji złożoności: O(n^O(1)), O(O(n^O(1)))

WŁAŚCIWOŚCI FUNKCJI ZŁOŻONOŚCI

1	c⋅O(f(n)) = O(f(n))
2	O(f(n)) + O(f(n)) = O(f(n))
3	O(O(f(n))) = O(f(n))
4	O(f(n)) ⋅ O(g(n)) = O(f(n)⋅g(n))
5	O(f(n) ⋅ g(n)) = f(n) ⋅ O(g(n))
6	O(f(n)+g(n)) = O(max(f,g))

Jaką złożoność posiada Algorytm1 ?

Algorytm1(int n) { for(int i=0;i<n;i++) { Algorytm2(); // O(n^2) Algorytm3(); // O(ln n) } }

O(n^3)

Algorytm1(int n) { Algorytm2(); // O(n^2) for(int i=0;i<n;i++) for(int j=0;j<n;j++) Algorytm3(); // O(n) }

O(n^3)

---