Studia informatyka – Sortowanie i wyszukiwanie

Sortowanie

Proces porządkowania elementów zbioru według określonego kryterium, np. rosnąco lub malejąco.

Algorytm sortowania

Sposób przekształcania nieuporządkowanego zbioru danych na zbiór uporządkowany. Przykłady: QuickSort, MergeSort.

Wyszukiwanie

Proces znajdowania określonego elementu lub grupy elementów w zbiorze danych.

Algorytm wyszukiwania binarnego

Algorytm do wyszukiwania w posortowanej liście, operujący na zasadzie dzielenia zbioru na pół.

Złożoność czasowa

Miara efektywności algorytmu, wyrażająca czas potrzebny na jego wykonanie w zależności od rozmiaru danych.

Złożoność przestrzenna

Miara efektywności algorytmu, wyrażająca ilość pamięci potrzebnej do jego wykonania.

QuickSort

Algorytm sortowania, który dzieli zbiór na podzbiory i sortuje je rekurencyjnie. Średnia złożoność: O(n log n).

MergeSort

Algorytm sortowania, który dzieli zbiór na dwa podzbiory, sortuje je, a następnie łączy. Złożoność: O(n log n).

BabelSort

Kreatywny, ale nieefektywny algorytm sortowania, który wykorzystuje losowość do określenia porządku.

HeapSort

Algorytm sortowania oparty na strukturze danych znanej jako kopiec. Złożoność: O(n log n).

Insertion Sort

Algorytm sortowania polegający na wstawianiu elementów do posortowanej części zbioru. Złożoność: O(n^2).

Selection Sort

Algorytm, który sortuje zbiór przez wielokrotne znajdowanie najmniejszego elementu. Złożoność: O(n^2).

Stabilność algorytmu

Właściwość algorytmu sortującego, która zapewnia, że równe elementy pozostają w tej samej kolejności.

Słownik

Struktura danych, która przechowuje pary klucz-wartość, umożliwiająca szybkie wyszukiwanie.

Lista

Struktura danych, która przechowuje uporządkowany zbiór elementów, z możliwością dodawania i usuwania.

Prawda czy fałsz: QuickSort jest zawsze szybszy niż Insertion Sort.

Fałsz, ponieważ QuickSort ma średnią złożoność O(n log n), ale w najgorszym przypadku O(n^2).

Różnica między sortowaniem a wyszukiwaniem

Sortowanie organizuje dane, podczas gdy wyszukiwanie znajduje konkretne dane w zbiorze.

Co to jest złożoność O(n^2)?

Oznacza, że czas wykonania algorytmu rośnie kwadratowo wraz z rozmiarem danych.

Co oznacza stabilny algorytm sortowania?

Algorytm, który zachowuje względną pozycję równych elementów w zbiorze.

Uzupełnij zdanie: MergeSort wykorzystuje ___ do łączenia posortowanych podzbiorów.

Metodę łączenia, która scalają dane w jedno.

Wyszukiwanie liniowe

Algorytm, który przeszukuje zbiór element po elemencie. Złożoność: O(n).

Co to jest złożoność O(n log n)?

Oznacza, że czas wykonania algorytmu rośnie proporcjonalnie do n log n, co jest typowe dla efektywnych algorytmów sortujących.

Funkcja hashująca

Funkcja przekształcająca dane wejściowe w unikalną wartość, co ułatwia szybkie wyszukiwanie w strukturach danych.

Różnica między wyszukiwaniem binarnym a liniowym

Wyszukiwanie binarne działa tylko na posortowanych zbiorach, jest bardziej efektywne.

Co to jest złożoność czasowa algorytmu?

To ilość czasu, jaką algorytm potrzebuje do zakończenia działania w zależności od wielkości danych wejściowych.

Przykład algorytmu wyszukiwania

Wyszukiwanie binarne, które dzieli zbiór na pół, aż znajdzie poszukiwany element.

Przykład danych uporządkowanych

Dane takie jak lista ocen w porządku rosnącym.

Wizualizacja algorytmu

Reprezentacja wizualna, która pomaga zrozumieć działanie algorytmu, np. wykresy.

Rodzaje struktur danych

Tablice, listy, stosy, kolejki, słowniki. Każda z nich ma swoje zastosowania w sortowaniu i wyszukiwaniu.

Zastosowanie sortowania

Umożliwia efektywne przeszukiwanie, organizację danych i poprawę wydajności aplikacji.