Menu

Výběr Seřadit v C ++ s příklady

selection sort c with examples

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Hloubkový pohled na výběr Seřadit v C ++ s příklady.

Jak název napovídá sám, technika výběru výběru nejprve vybere nejmenší prvek v poli a zamění jej za první prvek v poli.

Dále zamění druhý nejmenší prvek v poli s druhým prvkem atd. Pro každý průchod je tedy vybrán nejmenší prvek v poli a umístěn do správné polohy, dokud není tříděno celé pole.

=> Podívejte se na průvodce Perfect C ++ Training Guide zde.

Výběr řazení

Co se naučíte:

Úvod

Třídění výběru je docela přímá technika třídění, protože zahrnuje pouze nalezení nejmenšího prvku v každém průchodu a jeho umístění do správné polohy.

Třídění výběru funguje efektivně, když je seznam, který má být seřazen, malé velikosti, ale jeho výkon je špatně ovlivněn, protože velikost seznamu, který se má třídit, roste.

Můžeme tedy říci, že výběr není vhodný pro větší seznamy dat.

Obecný algoritmus

Obecný algoritmus pro výběr je uveden níže:

jak předat pole v Javě

Výběr řazení (A, N)

Krok 1 : Opakujte kroky 2 a 3 pro K = 1 až N-1
Krok 2 : Volejte rutinu nejmenší (A, K, N, POS)
Krok 3 : Zaměňte A (K) za A (POS)
(Konec smyčky)
Krok 4 : KONEC

Rutina nejmenší (A, K, N, POS)

  • Krok 1 : (inicializovat) nastavit nejmenšíElem = A (K)
  • Krok 2 : (inicializovat) nastavit POS = K
  • Krok 3 : pro J = K + 1 až N -1, opakujte
    pokud je nejmenšíElem> A (J)
    nastavit nejmenšíElem = A (J)
    nastavit POS = J
    (pokud je konec)
    (Konec smyčky)
  • Krok 4 : návrat POS

Pseudokód pro výběr Seřadit

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)

Níže je uveden příklad pro ilustraci tohoto algoritmu třídění výběru.

Ilustrace

Výběr Třídit ilustrace

Pass2

Pass3

Pass4

Tabulkové znázornění pro tuto ilustraci je uvedeno níže:

Nezařazený seznamNejméně prvekSeřazený seznam
{18,10,7,20,2}dva{}
{18,10,7,20}7{dva}
{18,10,20}10{2.7}
{18.20}18{2,7,10)
{dvacet}dvacet{2,7,10,18}
{}{2,7,10,18,20}

Z obrázku vidíme, že s každým průchodem je nejmenší prvek vložen do správné polohy v seřazeném poli. Z výše uvedeného obrázku vidíme, že aby bylo možné řadit pole 5 prvků, byly vyžadovány čtyři průchody. To znamená obecně, abychom mohli řadit pole N prvků, potřebujeme celkem N-1 průchodů.

Níže je uvedena implementace algoritmu výběru řazení v C ++.

Příklad 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<

Výstup:

Vstupní seznam prvků, které mají být seřazeny

11 5 2 20 42 53 23 34 101 22

Seřazený seznam prvků je

2 5 11 20 22 23 34 42 53 101

Počet průchodů potřebných k seřazení pole: 10

Jak je ukázáno ve výše uvedeném programu, začneme výběr výběrem porovnáním prvního prvku v poli se všemi ostatními prvky v poli. Na konci tohoto srovnání je nejmenší prvek v poli umístěn na první pozici.

V dalším průchodu se stejným přístupem umístí další nejmenší prvek v poli do správné polohy. To pokračuje až do N prvků nebo do seřazení celého pole.

Příklad Java

Dále implementujeme techniku ​​výběru výběru v jazyce 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)

Výstup:

Vstupní seznam k seřazení…

11 5 2 20 42 53 23 34 101 22

tisk seřazených prvků…

2 5 11 20 22 23 34 42 53 101

Ve výše uvedeném příkladu Java také použijeme stejnou logiku. Opakovaně najdeme nejmenší prvek v poli a vložíme jej do seřazeného pole, dokud nebude celé pole zcela tříděno.

Výběrové řazení je tedy nejjednodušší algoritmus, který je třeba implementovat, protože musíme opakovaně najít další nejmenší prvek v poli a vyměnit jej s prvkem v příslušné poloze.

Analýza složitosti výběru Seřadit

Jak je vidět ve výše uvedeném pseudokódu pro výběrové řazení, víme, že výběrové řazení vyžaduje dvě, aby se smyčky vnořené navzájem dokončily. Jeden pro smyčku prochází všemi prvky v poli a my najdeme minimální index prvku pomocí jiného pro smyčku, která je vnořena do vnější smyčky for.

Proto vzhledem k velikosti N vstupního pole má algoritmus výběru řazení následující hodnoty času a složitosti.

Nejhorší časová složitostO (n2); O (n) swapy
Nejlepší časová složitostO (n2); O (n) swapy
Průměrná časová složitostO (n2); O (n) swapy
Složitost prostoruO (1)

Časová složitost O ( n dva) je hlavně kvůli použití dvou pro smyčky. Všimněte si, že technika výběru výběru nikdy nezabere více než O (n) swapů a je výhodná, když se operace zápisu do paměti ukáže jako nákladná.

Závěr

Třídění podle výběru je další nejjednodušší technikou třídění, kterou lze snadno implementovat. Třídění výběru funguje nejlépe, když je znám rozsah hodnot, které mají být tříděny. Takže pokud jde o třídění datových struktur pomocí výběrového třídění, můžeme třídit pouze datové struktury, které jsou lineární a konečné velikosti.

To znamená, že můžeme efektivně řadit datové struktury, jako jsou pole, pomocí výběrového třídění.

V tomto kurzu jsme podrobně diskutovali o výběru výběru, včetně implementace výběru výběru pomocí jazyků C ++ a Java. Logikou za výběrem je najít opakovaně nejmenší prvek v seznamu a umístit jej na správné místo.

V dalším tutoriálu se podrobně seznámíme s typem vkládání, o kterém se říká, že je efektivnější technikou než ostatní dvě techniky, které jsme dosud diskutovali, tj. Třídění bublin a třídění výběru.

=> Podívejte se sem a podívejte se zde na A-Z výukových kurzů C ++.

Doporučené čtení

^