Въведение в сортирането в C ++
Имайки колекция от елементи по поръчка, сортирането помага при подреждането на елементите в записа въз основа на отношението за поръчка. Помислете за запис на файл, който съдържа много информация, за достъп до списък от записа е необходимо да има ключово поле, което да сочи текущото местоположение на елемента. Например, помислете за списък с имена в базата данни, той може да бъде сортиран по азбучен ред. Сортирането играе важна роля в областта на компютрите и технологиите. Нека видим повече в тази статия.
Какво е сортирането в C ++?
Сортирането е основната концепция, използвана от програмиста или изследователя за сортиране на необходимите данни. Редът на сложност е даден с 0 (N * log (N)). Сортирането на вход улеснява решаването на много проблеми като елемент Search, Maximum и Minimum. Въпреки че сортирането подрежда данните в последователността, ефективността на процеса е много важна, която се основава на два критерия: - Време и памет, необходими за извършване на сортиране по дадените данни. Времето се измерва чрез преброяване на сравненията на използваните ключове. Има много алгоритми за сортиране. Като цяло сортирането в C ++ се разграничава на два типа:
- Вътрешно сортиране
- Външно сортиране
Синтаксис и пример
Синтаксис:
C ++ използва sort () вградена функция за своите алгоритми, за да сортира контейнерите като вектори, масиви.
Сортиране (масив, масив + размер);
Примери:
#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)
изход:
Как работи?
За начало ще вземем Quick Sort, който се счита за важен метод сред различните видове сортиране. Основното сортиране на масив използва Quicksort подход. Има различни начини за изпълнение на сортирането, целта на всяка от тези техники е същата като сравняването на два елемента и замяната им с временната променлива. В тази статия ще обсъдим най-важното сортиране, използвано за изпълнение. Следват:
- Сортиране на балончета
- Сортиране на вмъкване
- Бързо сортиране
- Сортиране на селекцията
Има сортиране на сливане, сортиране по радиация, сортиране на лента, за което можем да обсъдим по-късно. Първо ще преминем с сорт Bubble.
1. Сортиране на балончета
Сортирането на балоните е един от най-простите методи за сортиране, които можем да използваме за приложения. При тази техника се правят последователни суапове през записите, които се сортират. На всяка стъпка той сравнява ключа с данните и обменя елементите, ако не в желания ред. Сортирането се извършва със съседните елементи по времето, когато само един елемент се поставя на сортираното място след размяна.
Пример: Нека разгледаме несортиран масив A () = (6, 2, 4, 7, 1)
| 6 | 2 | 4 | 7 | 1 |
| А (0) | А (1) | А (2) | А (3) | А (4) |
Стъпка 1: Сравняване на A (0)> A (1), ако условието е вярно, разменете елемента (6> 2) истина, поставете 2 в A (0). По подобен начин всички стъпки се извършват еднакво, докато масивът не бъде сортиран.
Сега масивът е A () = (2, 6, 4, 7, 1)
Стъпка 2: 6 се сравнява с 4. Тъй като 6 е по-голям от 4. Следователно, 6 и 4 се разменят.
Сега масивът е A () = (2, 4, 6, 7, 1)
Стъпка 3: Елемент 6 се сравнява със 7. Тъй като 6 <2 и елементите са във възходящ ред, елементите не се разменят.
Сортираният масив е A () = (2, 4, 6, 7, 1).
Продължете процеса, докато масивът не се сортира.
2. Сортиране на вмъкване
В тази техника започваме с втория елемент от данни, като приемем, че първият елемент вече е сортиран и се прави сравнение с втория елемент, а стъпката продължава с другия следващ елемент. В масив от N елементи е необходимо да има N-1 проходи, за да има сортиран елемент.
Помислете за масив A () = (8, 3, 6, 1)
| 8 | 3 | 6 | 1 |
Стъпка 1: Първият елемент търси най-големия елемент в масива, който да смени. Ако е по-голям, той остава същият и преминава към втория елемент, тук 8 е по-голям от всички, не се прави размяна.
| 8 | 3 | 6 | 1 |
Стъпка 2: Размяна с втория елемент
| 3 | 8 | 6 | 1 |
Стъпка: Размяна с третия елемент
| 3 | 6 | 8 | 1 |
Стъпка 4: Размяна с четвъртия елемент
| 1 | 3 | 6 | 8 |
3. Бързо сортиране
Тази техника следва алгоритъма на разделяне и завладяване и се счита за много ефективна, както и по-бърза за огромни масиви. Те са разделени на три подсекции: ляв, десен и среден. Средният елемент има единична стойност и е кръстен като въртящ се. Механизмът върви по този начин, елементът в левия сегмент не трябва да има ключ, по-голям от средния елемент, а никой елемент вдясно има ключ, който е по-малък от този на средния елемент. Сега нека започнем с илюстрация на процеса на сортиране. Quicksort използва рекурсивна концепция, докато сортира подчаст. Масивът е разделен на подчаст, отново левият и десният сегменти са разделени чрез завладяване. Тук в този пример като се има предвид, че последният елемент има въртене и първият елемент се приема нисък. Помислете за елемент от масив
| 49 | 22 | 11 | 16 | 56 | 30 |
Вземането на най-десния елемент има въртящ елемент = 30
| 16 | 22 | 11 | 30 | 56 | 49 |
Елементът, по-голям от въртенето, се поставя в ляво, по-малък вдясно.
| 16 | 22 | 11 | 56 | 49 |
Показалецът е поставен на въртенето и е разделен около въртене.
| 11 | 22 | 16 | 56 | 49 |
Подчастите са сортирани поотделно.
| 11 | 16 | 22 | 30 | 49 | 56 |
Накрая получихме сортиран масив.
4. Сортиране на селекцията
Тази техника се нарича също борсово сортиране, което извършва двойна операция за търсене и сортиране. Внедряването извършва директно сортиране на подбор, както е определено по-долу. Тук е необходимо да се идентифицира най-малкият елемент, присъстващ в масива, и този елемент е сортиран в първата позиция, След това вторият най-малък елемент е идентифициран и той е сортиран във втората позиция. Сортът за избор излиза от цикъла си, когато несортираната подчаст стане празна. Времевата сложност е дадена като O (n 2 ).
Помислете за следния масив:
| 63 | 26 | 13 | 23 | 12 |
1. Намерете най-малкия елемент и го поставете в началото и той се разменя с позицията.
| 12 | 26 | 13 | 23 | 63 |
2. Вторият елемент a (1) е идентифициран, сравнете с минималния елемент и го поставете във втората позиция, подобно на преминаването продължава.
| 12 | 13 | 26 | 23 | 64 |
Крайна сортирана продукция
| 12 | 13 | 23 | 26 | 64 |
заключение
В заключение, тази статия се фокусира върху сортирането на концепции и техния механизъм на работа. Всички тези техники за сортиране използват концепции за паралелна обработка. Сортирането формира основен градивен елемент в структурирането на алгоритми за решаване на проблемите на данните в реалния свят чрез сортиране на набора от стойности според изискванията.
Препоръчителни статии
Това е ръководство за сортирането в C ++. Тук обсъждаме Въведение и синтаксис с примери, заедно с Как работи. Можете също да прегледате и другите ни предложени статии, за да научите повече -
- Сортиране в Tableau
- Итератор в C ++
- Функции на масив в C
- Сортиране на купчина в С
- Как се извършва сортирането в PHP?
- Сортиране на купи в Python
- Iterator в Java
- Топ 11 функции и предимства на C ++
- Iterator в Python | Ползи и примери на Python