Menu

Sortowanie przez wybór w Javie - Algorytm sortowania przez wybór i przykłady

  • Główny
  • Inny
  • Sortowanie przez wybór w Javie - Algorytm sortowania przez wybór i przykłady

selection sort java selection sort algorithm examples

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Ten samouczek wyjaśni wszystko na temat sortowania przez wybór w Javie wraz z algorytmem sortowania przez wybór, kodem Java, implementacją w języku Java i przykładami języka Java:

Technika sortowania przez wybór to metoda, w której najmniejszy element tablicy jest wybierany i zamieniany na pierwszy element tablicy. Następnie drugi najmniejszy element w tablicy jest wymieniany z drugim elementem i odwrotnie.

=> Zajrzyj tutaj, aby zobaczyć A-Z samouczków szkoleniowych Java tutaj.

Sortowanie przez wybór w Javie

Czego się nauczysz:

Sortowanie przez wybór w Javie

W ten sposób najmniejszy element w tablicy jest wielokrotnie wybierany i umieszczany w odpowiedniej pozycji, aż cała tablica zostanie posortowana.

Do sortowania przez wybór zachowywane są dwie tablice podrzędne:

  1. Posortowana pod tablica: W każdej iteracji minimalny element jest znajdowany i umieszczany we właściwej pozycji. Ta podtablica jest posortowana.
  2. Niesortowana pod tablica: Pozostałe elementy, które nie są posortowane.

Sortowanie przez wybieranie to prosta i łatwa technika sortowania. Technika polega jedynie na znalezieniu najmniejszego elementu w każdym przejściu i umieszczeniu go we właściwej pozycji. Sortowanie przez wybór jest idealne dla mniejszych zestawów danych, ponieważ skutecznie sortuje mniejszy zbiór danych.

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

Algorytm sortowania przez wybór

Ogólny algorytm sortowania przez wybór przedstawiono poniżej:

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 : [initialize] set smallestItem = A [K]

Krok 2 : [inicjalizuj] ustaw POS = K

Krok 3 :

dla J = K + 1 do N -1, powtórz
if smallestItem> A [J]
set smallestItem = A [J]
ustaw POS = J
[jeśli koniec]
[Koniec pętli]

Krok 4 : zwrot POS

Jak widać, procedura znajdowania najmniejszej liczby jest wywoływana podczas przeglądania zbioru danych. Po znalezieniu najmniejszego elementu umieszcza się go w żądanej pozycji.

pytania i odpowiedzi na rozmowę w sprawie zapewnienia jakości pdf

Pseudokod do sortowania przez wybór

Pseudokod algorytmu sortowania przez wybór podano poniżej.

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]

Zilustrujmy teraz sortowanie tablicy przy użyciu sortowania przez wybór.

Przykład sortowania przez wybór

Rozważmy następującą tablicę, która ma być posortowana jako przykład sortowania przez wybór.

Przykład sortowania przez wybór

Zdanie 1

Zdanie 2

Zdanie 3

Zdanie 4

Poniżej podano tabelaryczną reprezentację dla ilustracji:

Niesortowana listaNajmniejszy elementPosortowana lista
{17,10,7,29,2}dwa{}
{17,10,7,29}7{dwa}
{17,10,29}10{2.7}
{17.29}17{2,7,10)
{29}29{2,7,10,17}
{}{2,7,10,17,29}

Na ilustracji widzimy, że z każdym przejściem kolejny najmniejszy element jest umieszczany na właściwej pozycji w posortowanej tablicy. Ogólnie, aby posortować tablicę N elementów, potrzebujemy łącznie N-1 przebiegów.

Implementacja sortowania przez wybór w Javie

Pokażmy teraz program Java do implementacji sortowania przez wybór.

import java.util.*; class Main { static void sel_sort(int numArray[]) { int n = numArray.length; // traverse unsorted array for (int i = 0; i

Wynik:

Oryginalna tablica: [7, 5, 2, 20, 42, 15, 23, 34, 10]
Posortowana tablica: [2, 5, 7, 10, 15, 20, 23, 34, 42]

Wyjście - program Java do implementacji sortowania przez wybór

W powyższym przykładzie Java wielokrotnie znajdujemy najmniejszy element w tablicy i umieszczamy go w posortowanej tablicy, aż cała tablica zostanie całkowicie posortowana.

jaki jest klucz bezpieczeństwa w routerze

Lista połączona z sortowaniem wyboru w Javie

Poniżej znajduje się lista połączona, którą musimy posortować za pomocą sortowania przez wybór. W tym celu użyjemy rekurencyjnego podejścia do sortowania przez selekcję. Zamiast zamieniać część danych węzła, zamienimy węzły i ponownie wyrównamy wskaźniki.

Więc jeśli połączona lista jest podana w następujący sposób:

połączona lista

lista połączona - 2

Poniżej podano program w języku Java, który implementuje powyższe sortowanie.

// add a node to the beginning of the linked list static Node addNode( Node head_ref, int new_data) { // create a node Node newNode = new Node(); // assign data to node newNode.data = new_data; // link the node to linked list newNode.next = (head_ref); //head now points to new node (head_ref) = newNode; return head_ref; } // method to swap nodes static Node swapNodes( Node head_ref, Node curr_node1, Node curr_node2, Node prev_node) { // curr_node2 is new head head_ref = curr_node2; // realign links prev_node.next = curr_node1; // now swap next pointers of nodes Node temp = curr_node2.next; curr_node2.next = curr_node1.next; curr_node1.next = temp; return head_ref; } // sort the linked list using selection sort static Node Selection_Sort( Node head) { // only a single node in linked list if (head.next == null) return head; // minNode => node with minimum data value Node minNode = head; // prevMin => node previous to minNode Node prevMin = null; Node ptr; // traverse the list from head to last node for (ptr = head; ptr.next != null; ptr = ptr.next) { // check if current node is minimum if (ptr.next.data

Wynik:

Oryginalna połączona lista:
7 9 3 5 1 11
Lista połączona po sortowaniu:
1 3 5 7 9 11

Implementowanie sortowania Java - dane wyjściowe

Zwróć uwagę, że w powyższym programie ponownie wyrównaliśmy łącza węzłów zamiast sortować tylko komponent danych węzła.

Często Zadawane Pytania

P # 1) Jak działa sortowanie przez wybór?

Odpowiedź: Sortowanie przez wybieranie polega na utrzymywaniu dwóch tablic podrzędnych. Minimalny element z niesortowanej podtablicy jest umieszczany we właściwej pozycji w posortowanej pod-tablicy. Następnie drugi najniższy element ustawia się we właściwej pozycji. W ten sposób cała tablica jest sortowana, wybierając minimalny element podczas każdej iteracji.

Pytanie nr 2) Jaka jest złożoność sortowania przez wybór?

Odpowiedź: Ogólna złożoność sortowania przez wybieranie wynosi O (ndwa), co czyni go algorytmem nieefektywnym w przypadku większych zbiorów danych. Inne techniki sortowania są bardziej wydajne.

Pytanie 3) Jakie są zalety i wady sortowania przez wybór?

Odpowiedź: Sortowanie przez wybieranie jest techniką sortowania na miejscu, dzięki czemu nie wymaga dodatkowego miejsca do przechowywania elementów pośrednich.

Działa wydajnie na mniejszych strukturach danych, a także na prawie posortowanych zestawach danych.

Główną wadą techniki sortowania przez wybór jest to, że działa ona bardzo słabo wraz ze wzrostem rozmiaru struktury danych. Nie tylko staje się wolniejszy, ale także zmniejsza wydajność.

Pytanie 4) Ile zamian znajduje się w sortowaniu przez wybór?

Odpowiedź: Technika sortowania przez selekcję przyjmuje minimalną liczbę swapów. W najlepszym przypadku, gdy tablica jest posortowana, liczba zamiany w sortowaniu przez wybór wynosi 0.

Pytanie 5) Czy sortowanie przez wybór jest szybsze niż sortowanie przez wstawianie?

Odpowiedź: Sortowanie przez wstawianie jest szybsze i bardziej wydajne, a także stabilne. Sortowanie przez wybór jest szybsze tylko w przypadku mniejszych zestawów danych i częściowo posortowanych struktur.

Wniosek

Sortowanie przez wybór to technika, która działa poprzez wybranie minimalnego elementu podczas przechodzenia przez tablicę. Dla każdego przebiegu / iteracji wybierany jest następny minimalny element zestawu danych i umieszczany na jego właściwej pozycji.

Technika sortowania przez wybór działa wydajnie, gdy liczba elementów w zestawie danych jest mniejsza, ale zaczyna działać słabo w miarę wzrostu rozmiaru zbioru danych. Staje się nieefektywne w porównaniu z innymi podobnymi technikami, takimi jak sortowanie przez wstawianie.

W tym samouczku zaimplementowaliśmy przykłady sortowania tablic i połączonych list przy użyciu sortowania przez wybór.

=> Odwiedź tutaj, aby zobaczyć serię szkoleń Java dla wszystkich.

rekomendowane lektury

^