logo

TechCodeview

Algorytmy sortowania

A Algorytm sortowania służy do zmiany układu danej tablicy lub listy elementów zgodnie z operatorem porównania na elementach. Operator porównania służy do decydowania o nowej kolejności elementów w odpowiedniej strukturze danych.

Na przykład: Poniższa lista znaków jest posortowana w kolejności rosnącej według ich wartości ASCII. Oznacza to, że znak o mniejszej wartości ASCII zostanie umieszczony jako pierwszy niż znak o wyższej wartości ASCII.



Spis treści

Co to jest sortowanie?

Sortowanie odnosi się do przegrupowania danej tablicy lub listy elementów zgodnie z operatorem porównania na elementach. Operator porównania służy do decydowania o nowej kolejności elementów w odpowiedniej strukturze danych. Sortowanie oznacza zmianę kolejności wszystkich elementów w kolejności rosnącej lub malejącej.



Terminologia sortowania:

  • Sortowanie na miejscu: Wykorzystuje algorytm sortowania w miejscu stała przestrzeń do tworzenia danych wyjściowych (modyfikuje tylko podaną tablicę). Sortuje listę jedynie poprzez zmianę kolejności elementów na liście. Przykłady: sortowanie przez wybór, sortowanie bąbelkowe, sortowanie przez wstawianie i sortowanie na stercie.
  • Sortowanie wewnętrzne: Sortowanie wewnętrzne ma miejsce, gdy wszystkie dane są umieszczane w pliku pamięć główna Lub pamięć wewnętrzna . W przypadku sortowania wewnętrznego problem nie może wymagać danych wejściowych przekraczających jego rozmiar. Przykład: sortowanie na stercie, sortowanie bąbelkowe, sortowanie przez zaznaczenie, sortowanie szybkie, sortowanie powłokowe, sortowanie przez wstawianie.
  • Sortowanie zewnętrzne: Sortowanie zewnętrzne ma miejsce, gdy nie można jednocześnie umieścić w pamięci wszystkich danych wymagających posortowania. Sortowanie nazywa się sortowaniem zewnętrznym. Sortowanie zewnętrzne jest stosowane w przypadku ogromnych ilości danych. Przykłady: sortowanie przez scalanie, sortowanie według znaczników, sortowanie wielofazowe, sortowanie na czterech taśmach, sortowanie według zewnętrznej podstawy itp.
  • Stabilne sortowanie: Kiedy w To samo zamówienie w posortowanych danych bez zmiany ich położenia nazywa się sortowaniem stabilnym. Przykłady: sortowanie przez scalanie, sortowanie przez wstawianie, sortowanie bąbelkowe.
  • Niestabilne sortowanie: Kiedy w różny zamówienie w przypadku posortowanych danych nazywa się to sortowaniem niestabilnym. Przykłady: sortowanie szybkie, sortowanie stertowe, sortowanie skorupowe .

Charakterystyka algorytmów sortowania:

  • Złożoność czasowa: Złożoność czasowa, miara czasu potrzebnego na wykonanie algorytmu, służy do kategoryzowania algorytmów sortowania. Do ilościowego określenia złożoności czasowej procesu można wykorzystać wydajność algorytmu sortowania w najgorszym, średnim i najlepszym przypadku.
  • Złożoność przestrzeni: Algorytmy sortujące mają również złożoność przestrzenną, czyli ilość pamięci wymaganej do wykonania algorytmu.
  • Stabilność: Algorytm sortowania nazywa się stabilnym, jeśli po sortowaniu zachowana jest względna kolejność równych elementów. Jest to ważne w niektórych zastosowaniach, w których należy zachować pierwotną kolejność równych elementów.
  • Sortowanie na miejscu: Algorytm sortowania w miejscu to taki, który nie wymaga dodatkowej pamięci do sortowania danych. Jest to ważne, gdy dostępna pamięć jest ograniczona lub gdy nie można przenieść danych.
  • Zdolność do adaptacji: Algorytm sortowania adaptacyjnego to taki, który wykorzystuje istniejący wcześniej porządek danych w celu poprawy wydajności.

Zastosowania algorytmów sortowania:

  • Algorytmy wyszukiwania: Sortowanie jest często kluczowym krokiem w algorytmach wyszukiwania, takich jak wyszukiwanie binarne czy wyszukiwanie trójskładnikowe, gdzie dane muszą zostać posortowane przed wyszukaniem określonego elementu.
  • Zarządzanie danymi: Sortowanie danych ułatwia wyszukiwanie, pobieranie i analizowanie.
  • Optymalizacja bazy danych: Sortowanie danych w bazach danych poprawia wydajność zapytań.
  • Nauczanie maszynowe: Sortowanie służy do przygotowywania danych do uczenia modeli uczenia maszynowego.
  • Analiza danych: Sortowanie pomaga w identyfikowaniu wzorców, trendów i wartości odstających w zbiorach danych. Odgrywa kluczową rolę w analizie statystycznej, modelowaniu finansowym i innych dziedzinach opartych na danych.
  • System operacyjny: Algorytmy sortowania są używane w systemach operacyjnych do zadań takich jak planowanie zadań, zarządzanie pamięcią i organizacja systemu plików.

Podstawy algorytmów sortowania:

  • Wprowadzenie do technik sortowania – samouczki dotyczące struktury danych i algorytmów
  • Zastosowania, zalety i wady algorytmu sortowania
  • Jaki jest przykład sortowania z życia wzięty?
  • Co to jest sortowanie w DSA | Znaczenie sortowania

Algorytmy sortowania:

Implementacje bibliotek:

Łatwe problemy z sortowaniem:

  • Sortuj elementy według częstotliwości
  • Sortuj tablicę zer, 1 i 2
  • Sortuj numery zapisane na różnych komputerach
  • Sortuj tablicę w formie fali
  • Sprawdź, czy dowolne dwa przedziały nakładają się na siebie w danym zestawie przedziałów
  • Jak posortować tablicę dat w C/C++?
  • Sortowanie ciągów za pomocą sortowania bąbelkowego
  • Znajdź brakujące elementy zakresu
  • Sortuj tablicę według liczby ustawionych bitów
  • Sortuj elementy parzyste w kolejności rosnącej, a nieparzyste w kolejności malejącej
  • Sortuj tablicę, gdy sortowane są dwie połówki
  • Sortowanie dużych liczb całkowitych
  • Sortuj połączoną listę zer, 1 i 2

Średnie problemy z sortowaniem:

  • Liczba inwersji w tablicy przy użyciu sortowania przez scalanie
  • Znajdź minimalną długość nieposortowanej podtablicy, której sortowanie spowoduje posortowanie całej tablicy
  • Sortuj tablicę prawie posortowaną (lub posortowaną K).
  • Sortuj n liczb z zakresu od 0 do n^2 – 1 w czasie liniowym
  • Sortuj tablicę zgodnie z kolejnością określoną przez inną tablicę
  • Znajdź punkt, w którym pokrywają się maksymalne odstępy
  • Znajdź permutację, która powoduje najgorszy przypadek sortowania przez scalanie
  • Sortuj wektory par w kolejności rosnącej w C++
  • Minimalna liczba zamian, aby dwie tablice były identyczne
  • Problem dystrybucji czekolady
  • Przeprowadź permutację dwóch tablic w taki sposób, aby suma każdej pary była większa lub równa K
  • Sortowanie segmentowe Aby posortować tablicę z liczbami ujemnymi
  • Sortuj macierz w kolejności rosnącej
  • Konwertuj tablicę do postaci zredukowanej za pomocą wektora par
  • Najmniejsza trójka różnicowa z trzech tablic
  • Sprawdź, czy możliwe jest sortowanie tablicy z dozwoloną warunkową zamianą sąsiednich

Trudne problemy z sortowaniem:

  • Znajdź liczbę przekroczeń każdego elementu w tablicy
  • Policz różne wystąpienia jako podciąg
  • Policz minimalną liczbę podzbiorów (lub podciągów) kolejnymi liczbami
  • Wybierz k elementów tablicy tak, aby różnica między maksimum i minimum była zminimalizowana
  • Minimalna zamiana wymagana do konwersji drzewa binarnego na drzewo wyszukiwania binarnego
  • K-ty najmniejszy element po usunięciu niektórych liczb całkowitych z liczb naturalnych
  • Maksymalna różnica częstotliwości dwóch elementów taka, że ​​element mający większą częstotliwość jest również większy
  • Minimalna liczba swapów, aby osiągnąć permutowaną tablicę, przy czym dozwolone są maksymalnie 2 pozycje
  • Sprawdź, czy możliwe jest utworzenie takich samych elementów tablicy przy użyciu jednego numeru zewnętrznego
  • Posortuj tablicę po zastosowaniu podanego równania
  • Wydrukuj tablicę ciągów w posortowanej kolejności bez kopiowania jednego ciągu do drugiego

Szybkie linki :

  • „Zadania praktyczne” dotyczące sortowania
  • „Quizy” dotyczące sortowania

Zalecana:

  • Naucz się struktury danych i algorytmów | Poradnik DSA