Мени

Сортирање избора у Ц ++ са примерима

selection sort c with examples

Испробајте Наш Инструмент За Елиминисање Проблема

Детаљни поглед на сортирање избора у Ц ++ са примерима.

Као што и само име сугерише, техника селекционог сортирања прво бира најмањи елемент у низу и замењује га првим елементом у низу.

Даље, замењује други најмањи елемент у низу са другим елементом и тако даље. Тако се за сваки пролаз бира најмањи елемент у низу и ставља у његов одговарајући положај док се читав низ не сортира.

=> Овде погледајте савршен водич за обуку за Ц ++.

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

Шта ћете научити:

Увод

Сортирање избора је прилично једноставна техника сортирања, јер техника укључује само проналажење најмањег елемента у сваком додавању и постављање у прави положај.

Сортирање избора делује ефикасно када је листа која ће се сортирати мале величине, али на њене перформансе то лоше утиче јер листа која се сортира расте у величини.

Стога можемо рећи да сортирање избора није препоручљиво за веће спискове података.

Општи алгоритам

Општи алгоритам за сортирање избора дат је у наставку:

како читати бин датотеку

Сортирање избора (А, Н)

Корак 1 : Поновите кораке 2 и 3 за К = 1 до Н-1
Корак 2 : Најмања рутина позива (А, К, Н, ПОС)
3. корак : Замените А (К) са А (ПОС)
(Крај петље)
4. корак : ЕКСИТ

Рутински најмањи (А, К, Н, ПОС)

  • Корак 1 : (иницијализовати) поставити најмањиЕлем = А (К)
  • Корак 2 : (иницијализација) поставите ПОС = К
  • 3. корак : за Ј = К + 1 до Н -1, поновити
    ако је најмањиЕлем> А (Ј)
    постави најмањиЕлем = А (Ј)
    поставите ПОС = Ј
    (ако крај)
    (Крај петље)
  • 4. корак : поврат ПОС

Псеудоцоде за сортирање избора

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)

Пример који илуструје овај алгоритам сортирања избора приказан је у наставку.

Илустрација

Илустрација сортирања избора

Пасс2

Пасс3

Пасс4

Табеларни приказ за ову илустрацију приказан је испод:

Несортирана листаНајмање елементаСортирана листа
{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 елемената била потребна четири пролаза. То генерално значи, да бисмо сортирали низ од Н елемената, потребно нам је укупно Н-1 пролаза.

Доље је дата имплементација алгоритма сортирања избора у Ц ++.

Пример Ц ++

#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

Као што је приказано у горњем програму, започињемо сортирање избора поређењем првог елемента у низу са свим осталим елементима у низу. На крају овог поређења, најмањи елемент у низу постављен је на прво место.

У следећем пролазу, користећи исти приступ, следећи најмањи елемент у низу поставља се у тачан положај. То се наставља све док Н елемената или док се читав низ не сортира.

Пример Јаве

Даље, имплементирамо технику сортирања избора на језику Јава.

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

И у горњем примеру Јава-а примењујемо исту логику. У више наврата проналазимо најмањи елемент у низу и стављамо га у сортирани низ док се читав низ потпуно не сортира.

Стога је сортирање избора најједноставнији алгоритам за примену, јер само морамо више пута пронаћи следећи најмањи елемент у низу и заменити га с елементом на његовом одговарајућем положају.

Анализа сложености сортирања избора

Као што се види у псеудокоду изнад за сортирање избора, знамо да сортирање селекције захтева две фор петље међусобно угнежђене да би се довршила. Један за петљу корача кроз све елементе у низу и проналазимо минимални индекс елемената користећи други за петљу који је угнежђен унутар спољне петље за.

Стога, с обзиром на величину Н улазног низа, алгоритам сортирања избора има следеће вредности времена и сложености.

Најгора временска сложеностО (н 2); О (н) замене
Најбоља временска сложеностО (н 2); О (н) замене
Просечна временска сложеностО (н 2); О (н) замене
Сложеност простораО (1)

Временска сложеност О ( н два) је углавном због употребе два за петље. Имајте на уму да техника сортирања одабира никада не узима више од замене О (н) и корисна је када се операција уписивања у меморију покаже као скупа.

Закључак

Сортирање избора је још једна најједноставнија техника сортирања која се лако може применити. Сортирање избора најбоље функционише када је познат опсег вредности које се сортирају. Што се тиче сортирања структура података помоћу селекционог сортирања, можемо сортирати само податке који су линеарни и коначне величине.

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

У овом упутству детаљно смо разговарали о сортирању избора, укључујући и имплементацију сортирања избора помоћу језика Ц ++ и Јава. Логика иза сортирања одабира је да се више пута пронађе најмањи елемент на листи и постави на одговарајући положај.

У следећем водичу детаљно ћемо научити сортирање уметања за које се каже да је ефикаснија техника од друге две технике о којима смо до сада разговарали, тј. Сортирање мехурића и сортирање избора.

=> Погледајте овде да бисте видели А-З од Ц ++ туторијала за обуку овде.

Препоручено читање

^