introduction sorting techniques c
Lista różnych technik sortowania w C ++.
Sortowanie to technika zaimplementowana w celu uporządkowania danych w określonej kolejności. Sortowanie jest wymagane, aby upewnić się, że dane, których używamy, są w określonej kolejności, abyśmy mogli łatwo pobrać wymaganą informację ze stosu danych.
Jeśli dane są zaniedbane i nieposortowane, kiedy chcemy określonej informacji, będziemy musieli przeszukiwać je za każdym razem, aby odzyskać dane.
=> Przeczytaj serię szkoleń Easy C ++.
Dlatego zawsze zaleca się, aby nasze dane były uporządkowane w określonej kolejności, aby wyszukiwanie informacji, a także inne operacje wykonywane na danych, mogły być wykonywane łatwo i wydajnie.
Dane przechowujemy w formie ewidencji. Każdy rekord składa się z co najmniej jednego pola. Gdy każdy rekord ma unikalną wartość określonego pola, nazywamy go polem kluczowym. Na przykład, w klasie Roll No może być polem unikatowym lub kluczowym.
czym jest QA i QC w testowaniu oprogramowania
Możemy sortować dane w określonym polu kluczowym, a następnie układać je w porządku rosnącym / rosnącym lub malejącym / malejącym.
Podobnie w słowniku telefonicznym każdy rekord składa się z nazwiska osoby, adresu i numeru telefonu. W tym przypadku numer telefonu jest polem unikatowym lub kluczowym. W tym polu telefonu możemy sortować dane ze słownika. Alternatywnie możemy również sortować dane numerycznie lub alfanumerycznie.
Kiedy możemy dostosować dane do sortowania w samej pamięci głównej bez potrzeby korzystania z innej pamięci pomocniczej, wówczas nazywamy to Sortowanie wewnętrzne .
Z drugiej strony, gdy potrzebujemy pamięci pomocniczej do przechowywania danych pośrednich podczas sortowania, wówczas nazywamy tę technikę jako Sortowanie zewnętrzne .
W tym samouczku szczegółowo poznamy różne techniki sortowania w C ++.
Czego się nauczysz:
Techniki sortowania w C ++
C ++ obsługuje różne techniki sortowania wymienione poniżej.
Sortowanie bąbelkowe
Sortowanie bąbelkowe to najprostsza technika, w której porównujemy każdy element z sąsiednim elementem i zamieniamy elementy, jeśli nie są w kolejności. W ten sposób na końcu każdej iteracji (nazywanej przebiegiem) najcięższy element zostanie wyświetlony na końcu listy.
Poniżej podano przykład sortowania bąbelkowego.
Tablica do posortowania:
Jak widać powyżej, ponieważ jest to mała tablica i była prawie posortowana, udało nam się uzyskać całkowicie posortowaną tablicę w kilku przebiegach.
Zaimplementujmy technikę Bubble Sort w C ++.
#include using namespace std; int main () { int i, j,temp; int a(5) = {10,2,0,43,12}; cout <<'Input list ...
'; for(i = 0; i<5; i++) { cout < Wynik:
Lista wejściowa…
10 2 0 43 12
Posortowana lista elementów…
0 2 10 12 43
Jak widać na wyjściu, w technice sortowania bąbelkowego, z każdym przebiegiem najcięższy element jest przepuszczany do końca tablicy, w ten sposób całkowicie sortując tablicę.
Sortowanie przez wybór
Jest to prosta, ale łatwa w realizacji technika, w której znajdujemy najmniejszy element na liście i umieszczamy go w odpowiednim miejscu. Przy każdym przejściu kolejny najmniejszy element jest wybierany i umieszczany w odpowiednim miejscu.
Weźmy tę samą tablicę, co w poprzednim przykładzie i przeprowadź sortowanie przez wybór, aby posortować tę tablicę.
Jak pokazano na powyższej ilustracji, dla liczby N elementów przyjmujemy N-1 przebiegów, aby całkowicie posortować tablicę. Na końcu każdego przebiegu najmniejszy element tablicy jest umieszczany we właściwej pozycji w posortowanej tablicy.
Następnie zaimplementujmy sortowanie przez wybór w C ++.
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(5) = {12,45,8,15,33}; int pos,temp; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<5;i++) { cout< Wynik:
Wprowadź listę elementów do sortowania
12 45 8 15 33
Posortowana lista elementów to
8 12 15 33 45
W sortowaniu przez selekcję z każdym przebiegiem najmniejszy element tablicy jest umieszczany na właściwej pozycji. Stąd pod koniec procesu sortowania otrzymujemy całkowicie posortowaną tablicę.
Sortowanie przez wstawianie
Sortowanie przez wstawianie to technika, w której zaczynamy od drugiego elementu listy. Porównujemy drugi element z poprzednim (1św) i umieść go w odpowiednim miejscu. W następnym przebiegu dla każdego elementu porównujemy go ze wszystkimi jego poprzednimi elementami i wstawiamy ten element w odpowiednie miejsce.
Powyższe trzy techniki sortowania są proste i łatwe do wdrożenia. Techniki te działają dobrze, gdy rozmiar listy jest mniejszy. W miarę jak lista rośnie, techniki te nie działają tak skutecznie.
Technika będzie zrozumiała po zrozumieniu poniższej ilustracji.
Tablica do posortowania jest następująca:
Teraz dla każdego przebiegu porównujemy bieżący element ze wszystkimi jego poprzednimi elementami. Zatem w pierwszym przebiegu zaczynamy od drugiego elementu.
Więc potrzebujemy N liczby przebiegów, aby całkowicie posortować tablicę zawierającą N liczby elementów.
Zaimplementujmy technikę sortowania przez wstawianie w C ++.
#include using namespace std; int main () { int myarray(5) = { 12,4,3,1,15}; cout<<'
Input list is
'; for(int i=0;i<5;i++) { cout < Wynik:
Lista wejściowa to
12 4 3 1 15
Posortowana lista to
1 3 4 12 15
Powyższe dane wyjściowe pokazują pełną posortowaną tablicę przy użyciu sortowania przez wstawianie.
Szybkie sortowanie
Quicksort jest najbardziej wydajnym algorytmem, którego można użyć do sortowania danych. Technika ta wykorzystuje strategię „dziel i rządź”, w której problem jest podzielony na kilka podproblemów, a po rozwiązaniu tych podproblemów indywidualnie są łączone razem w celu uzyskania pełnej posortowanej listy.
W quicksort najpierw dzielimy listę wokół elementu pivot, a następnie umieszczamy pozostałe elementy w odpowiednich pozycjach zgodnie z elementem pivot.
Jak pokazano na powyższej ilustracji, w technice Quicksort dzielimy tablicę wokół elementu obrotowego w taki sposób, że wszystkie elementy mniejsze niż pivot znajdują się po jego lewej stronie, a z tych większych niż pivot znajdują się po jego prawej stronie. Następnie bierzemy te dwie tablice niezależnie i sortujemy je, a następnie łączymy je lub podbijamy, aby uzyskać wynikową posortowaną tablicę.
Kluczem do Quicksort jest wybór elementu pivot. Może to być pierwszy, ostatni lub środkowy element tablicy. Pierwszym krokiem po wybraniu elementu pivot jest umieszczenie pivota w jego prawidłowej pozycji, tak abyśmy mogli odpowiednio podzielić tablicę.
Zaimplementujmy technikę szybkiego sortowania w C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Wynik:
Tablica wejściowa
12 23 3 43 51
Tablica posortowana za pomocą Quicksort
3 12 23 43 51
W powyższej implementacji quicksort mamy procedurę partycjonowania, która służy do dzielenia tablicy wejściowej wokół elementu przestawnego, który jest ostatnim elementem tablicy. Następnie rekurencyjnie wywołujemy procedurę quicksort, aby indywidualnie posortować pod-tablice, jak pokazano na ilustracji.
Merge Sort
To kolejna technika wykorzystująca strategię „Dziel i rządź”. W tej technice najpierw dzielimy listę na równe połowy. Następnie niezależnie wykonujemy na tych listach technikę scalania, tak aby obie listy były sortowane. Na koniec łączymy obie listy, aby uzyskać pełną posortowaną listę.
Sortowanie przez scalanie i szybkie sortowanie są szybsze niż większość innych technik sortowania. Ich wydajność pozostaje nienaruszona, nawet gdy lista rośnie.
Zobaczmy ilustrację techniki Merge Sort.
Na powyższej ilustracji widzimy, że technika sortowania przez scalanie wielokrotnie dzieli oryginalną tablicę na podtablice, aż w każdej podtablicy będzie tylko jeden element. Po wykonaniu tej czynności podtablice są następnie sortowane niezależnie i łączone w celu utworzenia kompletnej posortowanej tablicy.
Następnie zaimplementujmy Merge Sort przy użyciu języka C ++.
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< Wynik:
Podaj liczbę elementów do posortowania: 5
Wpisz 5 elementów do posortowania: 10 21 47 3 59
Posortowana tablica
3 10 21 47 59
Sortowanie powłoki
Sortowanie powłoki jest rozszerzeniem techniki sortowania przez wstawianie. W sortowaniu przez wstawianie mamy do czynienia tylko z następnym elementem, podczas gdy w przypadku sortowania powłoki podajemy przyrost lub przerwę, za pomocą których tworzymy mniejsze listy z listy nadrzędnej. Elementy na listach podrzędnych nie muszą być ciągłe, raczej są one zwykle oddalone od siebie o wartość „gap_value”.
Sortowanie powłokowe działa szybciej niż sortowanie przez wstawianie i wymaga mniej ruchów niż sortowanie przez wstawianie.
Jeśli podamy przerwę o wartości, będziemy mieli następujące listy podrzędne z każdym elementem, który jest oddalony o 3 elementy.
Następnie sortujemy te trzy podlisty.
Powyższa tablica, którą otrzymaliśmy po scaleniu posortowanych pod-tablic, jest prawie posortowana. Teraz możemy wykonać sortowanie przez wstawianie na tej tablicy, aby posortować całą tablicę.
Widzimy więc, że gdy podzielimy tablicę na podlisty za pomocą odpowiedniego przyrostu, a następnie połączymy je razem, otrzymamy prawie posortowaną listę. Technikę sortowania przez wstawianie na tej liście można wykonać, a tablica jest sortowana w mniejszej liczbie ruchów niż oryginalne sortowanie przez wstawianie.
Poniżej podano implementację metody Shell Sort w C ++.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18}; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i Wynik:
Tablica do posortowania:
45 23 53 43 18
Tablica po sortowaniu powłoki:
18 23 43 45 53
W ten sposób sortowanie powłoki działa jak ogromne ulepszenie w stosunku do sortowania przez wstawianie i nie zajmuje nawet połowy liczby kroków, aby posortować tablicę.
Sortowanie na stosie
Heapsort to technika, w której do sortowania listy używana jest struktura danych sterty (min-heap lub max-heap). Najpierw konstruujemy stertę z nieposortowanej listy, a także używamy sterty do sortowania tablicy.
Heapsort jest skuteczny, ale nie tak szybki, ani sortowanie przez scalanie.
Jak pokazano na powyższej ilustracji, najpierw konstruujemy maksymalną stertę z elementów tablicy do sortowania. Następnie przechodzimy przez stertę i zamieniamy ostatni i pierwszy element. W tym momencie ostatni element jest już posortowany. Następnie ponownie konstruujemy maksymalny stos z pozostałych elementów.
Ponownie przejdź przez stertę i zamień pierwszy i ostatni element oraz dodaj ostatni element do posortowanej listy. Ten proces jest kontynuowany do momentu, gdy w stercie pozostanie tylko jeden element, który stanie się pierwszym elementem posortowanej listy.
Zaimplementujmy teraz Heap Sort w C ++.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Wynik:
Tablica wejściowa
4 17 3 12 9
Posortowana tablica
3 4 9 12 17
Do tej pory omówiliśmy pokrótce wszystkie główne techniki sortowania z ilustracją. Dowiemy się szczegółowo każdej z tych technik w naszych kolejnych samouczkach wraz z różnymi przykładami, aby zrozumieć każdą technikę.
Wniosek
Sortowanie jest wymagane, aby dane były posortowane i we właściwej kolejności. Nieposortowany i zaniedbany może zająć więcej czasu, aby uzyskać dostęp, a tym samym może wpłynąć na wydajność całego programu. Dlatego w przypadku wszelkich operacji związanych z danymi, takich jak dostęp, wyszukiwanie, manipulacja itp., Potrzebujemy posortować dane.
W programowaniu stosuje się wiele technik sortowania. Każdą technikę można zastosować w zależności od używanej przez nas struktury danych lub czasu potrzebnego algorytmowi na sortowanie danych lub pamięci zajmowanej przez algorytm do sortowania danych. Technika, której używamy, zależy również od struktury danych, które sortujemy.
Techniki sortowania pozwalają nam sortować nasze struktury danych w określonej kolejności i układać elementy w kolejności rosnącej lub malejącej. Widzieliśmy techniki sortowania, takie jak sortowanie bąbelkowe, sortowanie przez wybór, sortowanie przez wstawianie, sortowanie szybkie, sortowanie powłoki, sortowanie przez scalanie i sortowanie na stosie. Sortowanie bąbelkowe i sortowanie przez wybór są prostsze i łatwiejsze do wdrożenia.
W naszych kolejnych samouczkach szczegółowo omówimy każdą z wyżej wymienionych technik sortowania.
=> Kliknij tutaj, aby uzyskać bezpłatny kurs C ++.
rekomendowane lektury
- Sortuj na stosie w C ++ z przykładami
- Sortuj w C ++ z przykładami
- Sortuj przez wstawianie w C ++ z przykładami
- JMeter Video 1: Wprowadzenie, JMeter Pobieranie i instalacja
- Wprowadzenie do języka programowania Java - samouczek wideo
- Wprowadzenie do języka Python i proces instalacji
- Polecenie sortowania systemu Unix ze składnią, opcjami i przykładami
- Metoda MongoDB Sort () z przykładami
