Menu

Wybór sortowania w C ++ z przykładami

selection sort c with examples

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Dogłębne spojrzenie na wybór Sortowanie w C ++ z przykładami.

Jak sama nazwa sugeruje, technika sortowania przez wybór najpierw wybiera najmniejszy element w tablicy i zamienia go na pierwszy element tablicy.

Następnie zamienia drugi najmniejszy element w tablicy na drugi i tak dalej. W ten sposób dla każdego przebiegu wybierany jest najmniejszy element tablicy i umieszczany na jego właściwej pozycji, aż cała tablica zostanie posortowana.

=> Sprawdź doskonały przewodnik szkoleniowy C ++ tutaj.

Sortowanie przez wybór

Czego się nauczysz:

Wprowadzenie

Sortowanie przez wybieranie jest dość prostą techniką sortowania, ponieważ polega ona tylko na znalezieniu najmniejszego elementu w każdym przejściu i umieszczeniu go we właściwej pozycji.

Sortowanie przez wybór działa wydajnie, gdy sortowana lista ma mały rozmiar, ale jej wydajność jest niekorzystna, ponieważ lista do sortowania rośnie.

Dlatego możemy powiedzieć, że sortowanie przez wybór nie jest zalecane w przypadku większych list danych.

Algorytm ogólny

Poniżej podano ogólny algorytm sortowania przez wybieranie:

najlepsze darmowe oprogramowanie do czyszczenia dla systemu Windows 10

Sortowanie przez wybór (A, N)

Krok 1 : Powtórz kroki 2 i 3 dla K = 1 do N-1
Krok 2 : Najmniejsza procedura połączenia (A, K, N, POS)
Krok 3 : Zamień A (K) na A (POS)
(Koniec pętli)
Krok 4 : WYJŚCIE

Rutynowe najmniejsze (A, K, N, POS)

  • Krok 1 : (zainicjalizuj) ustaw najmniejszyElem = A (K)
  • Krok 2 : (inicjalizuj) ustaw POS = K
  • Krok 3 : dla J = K + 1 do N -1, powtórz
    if najmniejszyElem> A (J)
    ustaw smallestElem = A (J)
    ustaw POS = J
    (jeśli koniec)
    (Koniec pętli)
  • Krok 4 : zwrot POS

Pseudokod do sortowania przez wybór

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)

Przykład ilustrujący ten algorytm sortowania przez wybór pokazano poniżej.

Ilustracja

Ilustracja sortowania wyboru

Pass2

Pass3

Pass4

Tabelaryczne przedstawienie tej ilustracji pokazano poniżej:

Niesortowana listaNajmniejszy elementPosortowana lista
{18,10,7,20,2}dwa{}
{18,10,7,20}7{dwa}
{18,10,20}10{2.7}
{18.20}18{2,7,10)
{20}20{2,7,10,18}
{}{2,7,10,18,20}

Na ilustracji widzimy, że z każdym przejściem kolejny najmniejszy element jest umieszczany na właściwej pozycji w posortowanej tablicy. Z powyższej ilustracji widzimy, że aby posortować tablicę 5 elementów, potrzebne były cztery przebiegi. Oznacza to ogólnie, że aby posortować tablicę N elementów, potrzebujemy łącznie N-1 przebiegów.

Poniżej podano implementację algorytmu sortowania przez wybór w C ++.

Przykład w 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<

Wynik:

Wprowadź listę elementów do sortowania

11 5 2 20 42 53 23 34 101 22

Posortowana lista elementów to

2 5 11 20 22 23 34 42 53 101

Liczba przebiegów wymaganych do posortowania tablicy: 10

Jak pokazano w powyższym programie, zaczynamy sortowanie przez wybór, porównując pierwszy element tablicy ze wszystkimi pozostałymi elementami tablicy. Na końcu tego porównania najmniejszy element tablicy jest umieszczany na pierwszej pozycji.

W następnym przebiegu, stosując to samo podejście, następny najmniejszy element w tablicy jest umieszczany na właściwej pozycji. Trwa to do N elementów lub do posortowania całej tablicy.

Przykład Java

Następnie wdrażamy technikę sortowania przez wybór w języku 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)

Wynik:

Lista wejściowa do sortowania…

11 5 2 20 42 53 23 34 101 22

drukowanie posortowanych elementów…

2 5 11 20 22 23 34 42 53 101

W powyższym przykładzie Java również stosujemy tę samą logikę. Wielokrotnie znajdujemy najmniejszy element w tablicy i umieszczamy go w posortowanej tablicy, aż cała tablica zostanie całkowicie posortowana.

Tak więc sortowanie przez wybór jest najprostszym algorytmem do zaimplementowania, ponieważ musimy po prostu wielokrotnie znaleźć następny najmniejszy element w tablicy i zamienić go na element w odpowiedniej pozycji.

Analiza złożoności sortowania selekcji

Jak widać na powyższym pseudokodzie dla sortowania przez wybór, wiemy, że sortowanie przez wybór wymaga dwóch dla zagnieżdżonych pętli, aby się dokończyć. Jedna pętla for przechodzi przez wszystkie elementy tablicy i znajdujemy minimalny indeks elementu, używając innej pętli for, która jest zagnieżdżona w zewnętrznej pętli for.

Dlatego, biorąc pod uwagę rozmiar N tablicy wejściowej, algorytm sortowania przez wybór ma następujące wartości czasu i złożoności.

W najgorszym przypadku złożoność czasowaO (n 2); O (n) swapy
Złożoność czasu w najlepszym przypadkuO (n 2); O (n) swapy
Średnia złożoność czasowaO (n 2); O (n) swapy
Złożoność przestrzeniO (1)

Złożoność czasowa O ( n dwa) wynika głównie z użycia dwóch pętli. Należy zauważyć, że technika sortowania przez wybór nigdy nie wymaga więcej niż O (n) zamian i jest korzystna, gdy operacja zapisu do pamięci okaże się kosztowna.

Wniosek

Sortowanie przez wybór to kolejna najprostsza technika sortowania, którą można łatwo wdrożyć. Sortowanie przez wybór działa najlepiej, gdy znany jest zakres sortowanych wartości. Tak więc, jeśli chodzi o sortowanie struktur danych za pomocą sortowania przez wybór, możemy sortować tylko struktury danych, które są liniowe i mają skończony rozmiar.

Oznacza to, że możemy efektywnie sortować struktury danych, takie jak tablice, przy użyciu sortowania przez wybór.

W tym samouczku szczegółowo omówiliśmy sortowanie przez wybór, w tym implementację sortowania przez wybór w językach C ++ i Java. Logika stojąca za sortowaniem przez wybór polega na wielokrotnym znajdowaniu najmniejszego elementu na liście i umieszczaniu go we właściwej pozycji.

W następnym samouczku dowiemy się szczegółowo o sortowaniu przez wstawianie, które jest uważane za bardziej wydajną technikę niż pozostałe dwie techniki, które omówiliśmy do tej pory, tj. Sortowanie bąbelkowe i sortowanie przez wybór.

=> Sprawdź tutaj, aby zobaczyć samouczki szkoleniowe od A do Z języka C ++ tutaj.

rekomendowane lektury

^