Меню

Сортиране на избора в C ++ с примери

selection sort c with examples

Опитайте Нашия Инструмент За Премахване На Проблемите

Поглед в дълбочина на сортирането на избора в C ++ с примери.

Както подсказва самото име, техниката за сортиране на селекция първо избира най-малкия елемент в масива и го разменя с първия елемент в масива.

След това сменя втория най-малък елемент в масива с втория елемент и така нататък. По този начин за всеки проход се избира най-малкият елемент в масива и се поставя в правилното му положение, докато не се сортира целият масив.

=> Вижте Перфектното ръководство за обучение на C ++ тук.

Сортиране на избора

Какво ще научите:

Въведение

Сортирането при подбор е доста проста техника за сортиране, тъй като техниката включва само намиране на най-малкия елемент във всеки проход и поставянето му в правилната позиция.

Сортирането на селекцията работи ефективно, когато списъкът, който ще се сортира, е с малък размер, но ефективността му се влияе зле, тъй като списъкът за сортиране нараства.

Следователно можем да кажем, че сортирането на подбора не е препоръчително за по-големи списъци с данни.

Общ алгоритъм

Общият алгоритъм за сортиране на подбора е даден по-долу:

кой е най-добрият имейл за използване

Сортиране на избора (A, N)

Етап 1 : Повторете стъпки 2 и 3 за K = 1 до N-1
Стъпка 2 : Повикване на рутина най-малко (A, K, N, POS)
Стъпка 3 : Разменете A (K) с A (POS)
(Край на цикъла)
Стъпка 4 : EXIT

Рутинни най-малки (A, K, N, POS)

  • Етап 1 : (инициализиране) задаване на най-малъкElem = A (K)
  • Стъпка 2 : (инициализиране) задайте POS = K
  • Стъпка 3 : за J = K + 1 до N -1, повторете
    ако е най-малъкElem> A (J)
    задайте най-малкияElem = A (J)
    задайте POS = J
    (ако край)
    (Край на цикъла)
  • Стъпка 4 : връщане на POS

Псевдокод за сортиране по избор

Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j)

Пример за илюстриране на този алгоритъм за сортиране на подбор е показан по-долу.

Илюстрация

Илюстрация за сортиране на селекцията

Pass2

Pass3

Pass4

Табличното представяне на тази илюстрация е показано по-долу:

Несортиран списъкНай-малко елементСортиран списък
{18,10,7,20,2}две{}
{18,10,7,20}7{две}
{18,10,20}10{2.7}
{18.20}18.{2,7,10)
{двадесет}двайсет{2,7,10,18}
{}{2,7,10,18,20}

От илюстрацията виждаме, че при всяко преминаване следващият най-малък елемент се поставя в правилното си положение в сортирания масив. От горната илюстрация виждаме, че за сортиране на масив от 5 елемента са необходими четири прохода. Това означава като цяло, за да сортираме масив от N елемента, ни трябват общо N-1 преминавания.

По-долу е дадено изпълнението на алгоритъм за сортиране на подбор в C ++.

Пример за C ++

#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<' Input list of elements to be Sorted '; for(int i=0;i<10;i++) { cout<

Изход:

Входен списък на елементите за сортиране

11 5 2 20 42 53 23 34 101 22

Сортираният списък с елементи е

2 5 11 20 22 23 34 42 53 101

Брой проходи, необходими за сортиране на масива: 10

Както е показано в горната програма, ние започваме сортиране на избора чрез сравняване на първия елемент в масива с всички останали елементи в масива. В края на това сравнение най-малкият елемент в масива се поставя на първо място.

При следващия проход, използвайки същия подход, следващият най-малък елемент в масива се поставя в правилната му позиция. Това продължава, докато N елементи или докато целият масив не бъде сортиран.

Пример за Java

След това внедряваме техниката за сортиране на подбора на езика Java.

class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println(' Input list to be sorted... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println(' printing sorted elements... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j)

Изход:

Списък на въведените данни за сортиране ...

11 5 2 20 42 53 23 34 101 22

отпечатване на сортирани елементи ...

2 5 11 20 22 23 34 42 53 101

В горния пример за Java също прилагаме същата логика. Многократно намираме най-малкия елемент в масива и го поставяме в сортирания масив, докато целият масив не бъде напълно сортиран.

По този начин сортирането на селекцията е най-простият алгоритъм за изпълнение, тъй като просто трябва многократно да намираме следващия най-малък елемент в масива и да го разменяме с елемента на подходящата му позиция.

Анализ на сложността на сортирането на селекцията

Както се вижда в псевдокода по-горе за сортиране на селекция, знаем, че сортирането на селекция изисква две за цикли, вложени един с друг, за да се завърши. Един за цикъл стъпва през всички елементи в масива и намираме минималния индекс на елемента, използвайки друг for цикъл, който е вложен във външния цикъл for.

Следователно, като се има предвид размер N на входния масив, алгоритъмът за сортиране на избора има следните стойности за време и сложност.

Най-лошата времева сложностO (n2); O (n) суапове
Най-добрата сложност във времетоO (n2); O (n) суапове
Средна времева сложностO (n2); O (n) суапове
Космическа сложностO (1)

Сложността на времето на O ( н две) се дължи главно на използването на две за цикли. Обърнете внимание, че техниката за сортиране на подбора никога не отнема повече от O (n) суапове и е полезна, когато операцията по запис в паметта се окаже скъпа.

Заключение

Сортирането по избор е още една най-проста техника за сортиране, която може лесно да бъде приложена. Сортирането по избор работи най-добре, когато е известен диапазонът на стойностите, които трябва да бъдат сортирани. Що се отнася до сортирането на структури от данни, използвайки сортиране на подбор, можем да сортираме само структурата на данни, която е линейна и с краен размер.

Това означава, че можем ефективно да сортираме структури от данни като масиви, като използваме сортирането на селекцията.

В този урок обсъдихме подробно сортирането на селекцията, включително изпълнението на сортирането на селекцията, използвайки езиците C ++ и Java. Логиката зад сортирането на селекцията е да намирате най-малкия елемент в списъка многократно и да го поставяте в правилната позиция.

В следващия урок ще научим подробно за сортирането на вмъкване, за което се казва, че е по-ефективна техника от другите две техники, които обсъждахме досега, т.е. сортиране на балончета и сортиране на селекция.

=> Проверете тук, за да видите A-Z на C ++ уроци за обучение тук.

Препоръчително четене

^