Sortowanie jest jedną z najczęściej używanych funkcji w programowaniu. A ukończenie sortowania zajmie trochę czasu, jeśli nie użyliśmy prawidłowego algorytmu.
W tym artykule omówimy różne algorytmy sortowania.
Przeprowadzimy Cię przez różne algorytmy sortowania na każdym etapie wdrażania. Część implementacyjna będzie w Pythonie. Po otrzymaniu algorytmu możesz łatwo przekonwertować go na dowolny język. To kwestia składni języka.
W tym samouczku zobaczymy różne algorytmy od najgorszego do najlepszego. Więc nie martw się. Postępuj zgodnie z artykułem i wdrażaj je.
Przejdźmy do algorytmów sortowania.
Spis treści:
Sortowanie przez wstawianie
Sortowanie przez wstawianie jest jednym z prostych algorytmów sortowania. Jest to łatwe do wdrożenia. A sortowanie tablicy będzie kosztować więcej czasu. W większości przypadków nie będzie używany do sortowania większych tablic.
Algorytm sortowania przez wstawianie utrzymuje posortowane i nieposortowane części podrzędne w danej tablicy.
Posortowana podczęść zawiera tylko pierwszy element na początku procesu sortowania. Weźmiemy element z nieposortowanej tablicy i umieścimy go we właściwej pozycji w posortowanej podtablicy.
Zobaczmy wizualne ilustracje sortowania przez wstawianie krok po kroku na przykładzie.
Zobaczmy, jak zaimplementować sortowanie przez wstawianie.
- Zainicjuj tablicę fikcyjnymi danymi (liczbami całkowitymi).
- Iteruj po podanej tablicy od drugiego elementu.
- Weź bieżącą pozycję i element w dwóch zmiennych.
- Napisz pętlę, która wykonuje iterację do momentu pojawienia się pierwszego elementu tablicy lub wystąpienia elementu mniejszego niż bieżący element.
- Zaktualizuj bieżący element za pomocą poprzedniego elementu.
- Zmniejszenie aktualnej pozycji.
- Tutaj pętla musi dotrzeć do początku tablicy lub znaleźć mniejszy element niż bieżący element. Zastąp bieżący element pozycji bieżącym elementem.
Złożoność czasowa sortowania przez wstawianie wynosi O(n^2), a złożoność przestrzenna, jeśli O(1).
Otóż to; posortowaliśmy podaną tablicę. Uruchommy następujący kod. Mam nadzieję, że zainstalowałeś Pythona, jeśli nie, sprawdź przewodnik instalacji. Alternatywnie możesz użyć internetowego kompilatora Pythona.
def insertion_sort(arr, n): for i in range(1, n): ## current position and element current_position = i current_element = arr[i] ## iteratin until ### it reaches the first element or ### the current element is smaller than the previous element while current_position > 0 and current_element < arr[current_position - 1]: ## updating the current element with previous element arr[current_position] = arr[current_position - 1] ## moving to the previous position current_position -= 1 ## updating the current position element arr[current_position] = current_element if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] insertion_sort(arr, 9) ## printing the array print(str(arr))
Sortowanie według wyboru
Sortowanie przez wybieranie jest podobne do sortowania przez wstawianie z niewielką różnicą. Algorytm ten dzieli również tablicę na posortowane i nieposortowane podczęści. A następnie, w każdej iteracji, weźmiemy minimalny element z nieposortowanej podczęści i umieścimy go na ostatniej pozycji posortowanej podczęści.
Posortujmy ilustracje sortowania dla lepszego zrozumienia.
Zobaczmy, jak zaimplementować sortowanie przez wybieranie.
- Zainicjuj tablicę fikcyjnymi danymi (liczbami całkowitymi).
- Iteruj po podanej tablicy.
- Zachowaj indeks minimalnego elementu.
- Napisz pętlę iterującą od bieżącego elementu do ostatniego elementu.
- Sprawdź, czy bieżący element jest mniejszy niż element minimalny, czy nie.
- Jeśli bieżący element jest mniejszy niż element minimalny, zastąp indeks.
- Mamy przy sobie minimalny indeks elementów. Zamień bieżący element z minimalnym elementem, używając indeksów.
Złożoność czasowa sortowania przez wybieranie wynosi O(n^2), a złożoność przestrzenna, jeśli O(1).
Spróbuj zaimplementować algorytm, ponieważ jest podobny do sortowania przez wstawianie. Możesz zobaczyć kod poniżej.
def selection_sort(arr, n): for i in range(n): ## to store the index of the minimum element min_element_index = i for j in range(i + 1, n): ## checking and replacing the minimum element index if arr[j] < arr[min_element_index]: min_element_index = j ## swaping the current element with minimum element arr[i], arr[min_element_index] = arr[min_element_index], arr[i] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] selection_sort(arr, 9) ## printing the array print(str(arr))
Sortowanie bąbelkowe
Sortowanie bąbelkowe to prosty algorytm. Zamienia sąsiednie elementy w każdej iteracji wielokrotnie, aż dana tablica zostanie posortowana.
Iteruje po tablicy i przesuwa bieżący element do następnej pozycji, dopóki nie będzie mniejszy niż następny element.
Ilustracje pomagają nam wizualnie zrozumieć sortowanie bąbelkowe. Zobaczmy je.
Zobaczmy, jak zaimplementować sortowanie bąbelkowe.
Złożoność czasowa sortowania bąbelkowego to O(n^2), a złożoność przestrzenna to O(1).
Możesz teraz łatwo zaimplementować sortowanie bąbelkowe. Zobaczmy kod.
def bubble_sort(arr, n): for i in range(n): ## iterating from 0 to n-i-1 as last i elements are already sorted for j in range(n - i - 1): ## checking the next element if arr[j] > arr[j + 1]: ## swapping the adjucent elements arr[j], arr[j + 1] = arr[j + 1], arr[j] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] bubble_sort(arr, 9) ## printing the array print(str(arr))
Sortuj przez scalanie
Sortowanie przez scalanie to rekurencyjny algorytm sortowania podanej tablicy. Jest bardziej wydajny niż wcześniej omówione algorytmy pod względem złożoności czasowej. Kieruje się zasadą dziel i zwyciężaj.
Algorytm sortowania przez scalanie dzieli tablicę na dwie połowy i sortuje je oddzielnie. Po posortowaniu dwóch połówek tablicy łączy je w jedną posortowaną tablicę.
Ponieważ jest to algorytm rekurencyjny, dzieli tablicę, aż tablica stanie się najprostszą (tablicą z jednym elementem) do sortowania.
Czas na ilustrację. Zobaczmy.
Zobaczmy, jak zaimplementować sortowanie przez scalanie.
- Zainicjuj tablicę fikcyjnymi danymi (liczbami całkowitymi).
- Napisz funkcję o nazwie merge, aby scalić podtablice w jedną posortowaną tablicę. Akceptuje tablicę argumentów, lewy, środkowy i prawy indeks.
- Uzyskaj długości lewej i prawej długości podtablic, korzystając z podanych indeksów.
- Skopiuj elementy z tablicy do odpowiednich tablic lewej i prawej.
- Iteruj po dwóch podtablicach.
- Porównaj dwa elementy podtablic.
- Zastąp element tablicy mniejszym elementem z dwóch podtablic do sortowania.
- Sprawdź, czy w obu podtablicach pozostały jakieś elementy.
- Dodaj je do tablicy.
- Napisz funkcję o nazwie merge_sort z tablicą parametrów, lewym i prawym indeksem.
- Jeśli lewy indeks jest większy lub równy prawemu indeksowi, wróć.
- Znajdź środkowy punkt tablicy, aby podzielić tablicę na dwie połowy.
- Rekursywnie wywołuj metodę merge_sort używając lewego, prawego i środkowego indeksu.
- Po wywołaniach rekurencyjnych połącz tablicę z funkcją scalania.
Złożoność czasowa sortowania przez scalanie to O(nlogn), a złożoność przestrzenna, jeśli O(1).
To wszystko, jeśli chodzi o implementację algorytmu sortowania przez scalanie. Sprawdź poniższy kod.
def merge(arr, left_index, mid_index, right_index): ## left and right arrays left_array = arr[left_index:mid_index+1] right_array = arr[mid_index+1:right_index+1] ## getting the left and right array lengths left_array_length = mid_index - left_index + 1 right_array_length = right_index - mid_index ## indexes for merging two arrays i = j = 0 ## index for array elements replacement k = left_index ## iterating over the two sub-arrays while i < left_array_length and j < right_array_length: ## comapring the elements from left and right arrays if left_array[i] < right_array[j]: arr[k] = left_array[i] i += 1 else: arr[k] = right_array[j] j += 1 k += 1 ## adding remaining elements from the left and right arrays while i < left_array_length: arr[k] = left_array[i] i += 1 k += 1 while j < right_array_length: j += 1 k += 1 def merge_sort(arr, left_index, right_index): ## base case for recursive function if left_index >= right_index: return ## finding the middle index mid_index = (left_index + right_index) // 2 ## recursive calls merge_sort(arr, left_index, mid_index) merge_sort(arr, mid_index + 1, right_index) ## merging the two sub-arrays merge(arr, left_index, mid_index, right_index) if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] merge_sort(arr, 0, 8) ## printing the array print(str(arr))
Wniosek
Istnieje wiele innych algorytmów sortowania, ale powyżej wymieniono niektóre z często używanych. Mam nadzieję, że podobała Ci się nauka sortowania.
Następnie zapoznaj się z algorytmami wyszukiwania.
Miłego kodowania 🙂 👨💻