introduction sorting techniques c
Списък на различните техники за сортиране в C ++.
Сортирането е техника, която се прилага за подреждане на данните в определен ред. Сортирането е необходимо, за да се гарантира, че данните, които използваме, са в определен ред, за да можем лесно да извлечем необходимата информация от купчината данни.
Ако данните са неподредени и несортирани, когато искаме дадена информация, тогава ще трябва всеки път да я търсим една по една, за да извлечем данните.
=> Прочетете серията Easy C ++ Training.
Поради това винаги е препоръчително да поддържаме данните си подредени в определен ред, така че извличането на информация, както и други операции, извършвани върху данните, да могат да се извършват лесно и ефективно.
Съхраняваме данни под формата на записи. Всеки запис се състои от едно или повече полета. Когато всеки запис има уникална стойност на определено поле, ние го наричаме ключово поле. Например, в клас Roll No може да бъде уникално или ключово поле.
безплатен sql софтуер за Windows 10
Можем да сортираме данните в конкретно ключово поле и след това да ги подредим във възходящ / увеличаващ се ред или в низходящ / намаляващ ред.
По същия начин в телефонен речник всеки запис се състои от името на човек, адрес и телефонен номер. При това телефонният номер е уникално или ключово поле. Можем да сортираме данните от речника в това телефонно поле. Друга възможност е да сортираме данни или цифрово, или буквено-цифрово.
Когато можем да настроим данните да бъдат сортирани в самата основна памет, без да е необходима друга спомагателна памет, тогава ние ги наричаме като Вътрешно сортиране .
От друга страна, когато се нуждаем от спомагателна памет за съхраняване на междинни данни по време на сортирането, тогава наричаме техниката като Външно сортиране .
В този урок ще научим подробно различните техники за сортиране в C ++.
Какво ще научите:
Техники за сортиране в C ++
C ++ поддържа различни техники за сортиране, изброени по-долу.
Сортиране на балончета
Bubble sort е най-простата техника, при която сравняваме всеки елемент със съседния му елемент и разменяме елементите, ако не са в ред. По този начин в края на всяка итерация (наречена пропуск), най-тежкият елемент се издува в края на списъка.
По-долу е даден пример за сортиране на балончета.
Масив за сортиране:
Както се вижда по-горе, тъй като това е малък масив и почти беше сортиран, успяхме да получим напълно сортиран масив за няколко прохода.
Нека внедрим техниката на сортиране на балончета в 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 < Изход:
Списък за въвеждане ...
10 2 0 43 12
Сортиран списък с елементи ...
0 2 10 12 43
Както се вижда от изхода, в техниката на сортиране на балончета, при всяко преминаване най-тежкият елемент се балонче до края на масива, като по този начин масивът се сортира напълно.
Сортиране на избора
Това е проста, но лесна за изпълнение техника, при която намираме най-малкия елемент в списъка и го поставяме на правилното му място. При всяко преминаване се избира следващият най-малък елемент и се поставя в правилното му положение.
Да вземем същия масив като в предишния пример и да извършим сортиране по избор, за да сортираме този масив.
Както е показано на горната илюстрация, за N броя елементи вземаме N-1 проходи, за да сортираме напълно масива. В края на всеки проход най-малкият елемент в масива се поставя на правилното му място в сортирания масив.
След това нека приложим Selection Sort, използвайки 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< Изход:
Входен списък на елементите за сортиране
12 45 8 15 33
Сортираният списък с елементи е
8 12 15 33 45
При сортиране на селекцията при всеки проход най-малкият елемент в масива се поставя в правилното му положение. Следователно в края на процеса на сортиране получаваме напълно сортиран масив.
Сортиране по вмъкване
Сортирането при вмъкване е техника, при която започваме от втория елемент на списъка. Сравняваме втория елемент с предишния (1ул) елемент и го поставете на правилното му място. При следващия проход, за всеки елемент, ние го сравняваме с всички предишни елементи и го вмъкваме на правилното му място.
Горните три техники за сортиране са лесни и лесни за изпълнение. Тези техники се представят добре, когато размерът на списъка е по-малък. Тъй като списъкът нараства, тези техники не се представят толкова ефективно.
Техниката ще бъде ясна, като се разбере следната илюстрация.
Масивът, който трябва да се сортира, е както следва:
Сега за всеки проход сравняваме текущия елемент с всички предишни елементи. Така при първото преминаване започваме с втория елемент.
Така че ние изискваме N брой проходи, за да сортираме напълно масив, съдържащ N брой елементи.
Нека внедрим техниката за сортиране на вмъкване, използвайки 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 < Изход:
Списъкът за въвеждане е
12 4 3 1 15
Сортираният списък е
1 3 4 12 15
Горният изход показва пълния сортиран масив, използващ сортиране на вмъкване.
Бързо сортиране
Quicksort е най-ефективният алгоритъм, който може да се използва за сортиране на данните. Тази техника използва стратегията „разделяй и владей“, при която проблемът е разделен на няколко подпроблеми и след решаването на тези подпроблеми поотделно се обединяват заедно за пълен сортиран списък.
В бързото сортиране първо разделяме списъка около шарнирния елемент и след това поставяме останалите елементи в правилните им позиции според шарнирния елемент.
Както е показано на горната илюстрация, в техниката Quicksort ние разделяме масива около опорен елемент така, че всички елементи, по-малки от въртенето, са вляво, кой от тези, по-големи от въртенето, е вдясно. След това ние вземаме тези два масива независимо и ги сортираме и след това се присъединяваме или завладяваме, за да получим резултатен сортиран масив.
Ключът към Quicksort е изборът на основния елемент. Тя може да бъде първи, последен или среден елемент на масива. Първата стъпка след избора на елемента pivot е поставянето на pivot в правилното му положение, така че да можем да разделим масива по подходящ начин.
Нека внедрим техниката за бързо сортиране, използвайки 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< Изход:
Входен масив
12 23 3 43 51
Масивът е сортиран с Quicksort
3 12 23 43 51
В реализацията за бърза сортировка по-горе имаме рутина за разделяне, която се използва за разделяне на входния масив около пивотен елемент, който е последният елемент в масива. След това извикваме подпрограмата за бързо сортиране рекурсивно, за да сортираме индивидуално под-масивите, както е показано на илюстрацията.
Сливане на сортиране
Това е друга техника, която използва стратегията „Разделяй и владей“. При тази техника първо разделяме списъка на равни половини. След това извършваме техника за сортиране на обединяване на тези списъци независимо, така че и двата списъка да бъдат сортирани. Накрая обединяваме двата списъка, за да получим пълен сортиран списък.
Сортирането чрез сливане и бързото сортиране са по-бързи от повечето други техники за сортиране. Тяхната ефективност остава непокътната, дори когато списъкът се разраства по-голям.
Нека да видим илюстрация на техниката Merge Sort.
В горната илюстрация виждаме, че техниката за сортиране на сливане разделя оригиналния масив на подмасиви многократно, докато във всеки подмасив има само един елемент. След като това бъде направено, подредовете след това се сортират независимо и се обединяват заедно, за да образуват пълен сортиран масив.
След това нека приложим Merge Sort, използвайки езика 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< Изход:
Въведете брой елементи за сортиране: 5
Въведете 5 елемента за сортиране: 10 21 47 3 59
Сортиран масив
3 10 21 47 59
Сортиране на черупката
Сортирането на черупки е продължение на техниката за сортиране на вмъкване. При сортиране с вмъкване се справяме само със следващия елемент, докато при сортирането на черупки предоставяме увеличение или празнина, с помощта на която създаваме по-малки списъци от родителския списък. Елементите в подсписъците не е задължително да са съседни, а обикновено са разделени на ‘gap_value’.
Сортирането на черупки се извършва по-бързо от сортирането с вмъкване и изисква по-малко ходове от това на сортирането с вмъкване.
Ако предоставим празнина от, тогава ще имаме следните под-списъци с всеки елемент, който е разделен на 3 елемента.
След това сортираме тези три подлиста.
Горният масив, който получихме след обединяване на сортираните подмасиви, е почти сортиран. Сега можем да извършим сортиране на вмъкване на този масив, за да сортираме целия масив.
По този начин виждаме, че след като разделим масива на под-списъци, като използваме съответния инкремент и след това ги обединим, получаваме почти сортирания списък. Техниката за сортиране на вмъкване в този списък може да се извърши и масивът се сортира с по-малко движения от първоначалното сортиране на вмъкването.
По-долу е дадено изпълнението на Shell Sort в 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 Изход:
Масив за сортиране:
45 23 53 43 18
Масив след сортиране на черупката:
18 23 43 45 53
По този начин сортирането на черупки действа като огромно подобрение спрямо сортирането при вмъкване и дори не предприема половината от стъпките за сортиране на масива.
Сортиране на купчина
Хепсорт е техника, при която за сортиране на списъка се използва структура на данните от купчина (мин. Купчина или макс. Купчина). Първо конструираме купчина от несортирания списък и също така използваме купчината за сортиране на масива.
Хепсортът е ефективен, но не е толкова бърз или сортирането на обединяване.
Както е показано на горната илюстрация, първо конструираме максимална купчина от елементите на масива, които ще бъдат сортирани. След това прекосяваме купчината и разменяме последния и първия елемент. По това време последният елемент вече е сортиран. След това отново изграждаме максимална купчина от останалите елементи.
Отново прекосете купчината и разменете първия и последния елемент и добавете последния елемент към сортирания списък. Този процес продължава, докато в купчината не остане само един елемент, който става първият елемент от сортирания списък.
Нека сега приложим Heap Sort, използвайки 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 Изход:
Входен масив
4 17 3 12 9
Сортиран масив
3 4 9 12 17
Досега обсъдихме накратко всички основни техники за сортиране с илюстрация. Ще научим подробно всяка от тези техники в следващите ни уроци, заедно с различни примери, за да разберем всяка техника.
Заключение
Сортирането е необходимо, за да се запазят сортираните данни в правилния ред. Несортираните и неподредени могат да отнемат по-дълго време за достъп и по този начин могат да засегнат производителността на цялата програма. По този начин за всякакви операции, свързани с данни като достъп, търсене, манипулация и т.н., се нуждаем от сортиране на данните.
Има много техники за сортиране, използвани в програмирането. Всяка техника може да се използва в зависимост от структурата на данните, която използваме, или времето, необходимо на алгоритъма за сортиране на данните или паметта, заети от алгоритъма за сортиране на данните. Техниката, която използваме, също зависи от това коя структура на данни сортираме.
Техниките за сортиране ни позволяват да сортираме структурите си от данни в определен ред и да подреждаме елементите във възходящ или низходящ ред. Виждали сме техники за сортиране като сортиране на мехурчета, сортиране по селекция, сортиране чрез вмъкване, сортиране на бързи, сортиране на черупки, сортиране на обединяване и сортиране на купчини. Bubble sort и Selection sort са по-прости и лесни за изпълнение.
В следващите ни уроци ще видим подробно всяка от гореспоменатите техники за сортиране.
=> Щракнете тук за безплатния курс C ++.
Препоръчително четене
- Сортиране на купчини в C ++ с примери
- Обединяване на сортиране в C ++ с примери
- Сортиране по вмъкване в C ++ с примери
- JMeter Video 1: Въведение, JMeter Изтегляне и инсталиране
- Въведение в езика за програмиране на Java - видео урок
- Процес на въвеждане и инсталиране на Python
- Команда за сортиране на Unix със синтаксис, опции и примери
- Метод за сортиране на MongoDB () с примери
