Materiały pomocnicze

• Temat 1: algorytmy sortowania


• Temat 2: drzewa binarne


• Temat 3: algorytmy grafowe


• Temat 4: algorytmy z powracaniem


• Temat 5: problem plecakowy i dedykowane mu algorytmy

Temat 1: Algorytmy sortowania

1. Stabilność algorytmu sortowania
   Algorytm sortowania jest stabilny jeśli liczby o tych samych wartościach występują w tablicy wynikowej w takiej samej kolejności jak w tablicy początkowej [Cormen i in.].

2. Sortowanie w miejscu
   Algorytm sortuje w miejscu jeśli podczas działania algorytmu sortowane elementy są cały czas przechowywane w tej samej tablicy wejściowej z wyjątkiem stałej liczby elementów. Po zakończeniu działania algorytmu tablica wejściowa zawiera posortowany ciąg [Cormen i in.].

algorytm	sortuje w miejscu
Insertion Sort	TAK
Selection Sort	TAK
Bubble Sort	TAK
Heap Sort	TAK
Merge Sort	NIE
Quick Sort	TAK
Counting Sort	NIE

3. Złożoność obliczeniowa wybranych algorytmów sortowania
   
   

   	złożoność obliczeniowa
   algorytm	optymistyczna	średnia	pesymistyczna
   Insertion Sort	O(n)	O(n2)	O(n2)
   Selection Sort	O(n2)	O(n2)	O(n2)
   Bubble Sort	O(n)	O(n2)	O(n2)
   Heap Sort	O(n log2n)	O(n log2n)	O(n log2n)
   Merge Sort	O(n log2n)	O(n log2n)	O(n log2n)
   Quick Sort	O(n log2n)	O(n log2n)	O(n2)
   Counting Sort	O(n+k)	O(n+k)	O(n+k)

w górę