SORTOWANIE PRZEZ WYBÓR

W tym artykule omówimy algorytm sortowania przez wybór. Procedura sortowania przez wybór jest również prosta. Ten artykuł będzie bardzo pomocny i interesujący dla studentów, ponieważ mogą spotkać się z rodzajem selekcji jako pytaniem na egzaminach. Dlatego ważne jest, aby omówić ten temat.

Podczas sortowania przez wybieranie w każdym przebiegu wybierana jest najmniejsza wartość spośród nieposortowanych elementów tablicy i wstawiana w odpowiedniej pozycji do tablicy. Jest to również najprostszy algorytm. Jest to algorytm sortowania porównawczego w miejscu. W tym algorytmie tablica jest dzielona na dwie części, pierwsza to część posortowana, a druga to część nieposortowana. Początkowo posortowana część tablicy jest pusta, a nieposortowana część to podana tablica. Posortowana część jest umieszczana po lewej stronie, a nieposortowana część po prawej stronie.

Podczas sortowania przez wybór z nieposortowanej tablicy wybierany jest pierwszy najmniejszy element i umieszczany na pierwszej pozycji. Następnie wybierany jest drugi najmniejszy element i umieszczany na drugiej pozycji. Proces trwa do momentu całkowitego posortowania tablicy.

Średnia i najgorszy przypadek złożoności sortowania przez wybór wynosi NA²) , Gdzie N to liczba elementów. Z tego powodu nie nadaje się do dużych zbiorów danych.

Sortowanie przez wybór jest zwykle używane, gdy -

Mała tablica ma zostać posortowana
Koszt wymiany nie ma znaczenia
Sprawdzenie wszystkich elementów jest obowiązkowe

Przyjrzyjmy się teraz algorytmowi sortowania przez wybór.

Algorytm

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL &gt; arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos

Działanie algorytmu sortowania przez selekcję

Przyjrzyjmy się teraz działaniu algorytmu sortowania przez wybór.

Aby zrozumieć działanie algorytmu sortowania przez wybór, weźmy nieposortowaną tablicę. Sortowanie przez wybór będzie łatwiejsze do zrozumienia na przykładzie.

Niech elementami tablicy są -

Teraz dla pierwszej pozycji w posortowanej tablicy należy sekwencyjnie przeskanować całą tablicę.

Obecnie, 12 jest przechowywany na pierwszej pozycji, po przeszukaniu całej tablicy okazuje się, że 8 jest najmniejszą wartością.

proszę

Zamień więc 12 z 8. Po pierwszej iteracji liczba 8 pojawi się na pierwszej pozycji posortowanej tablicy.

Dla drugiej pozycji, gdzie obecnie przechowywana jest liczba 29, ponownie skanujemy sekwencyjnie pozostałe elementy nieposortowanej tablicy. Po zeskanowaniu okazuje się, że 12 jest drugim najniższym elementem tablicy, który powinien pojawić się na drugiej pozycji.

Teraz zamień 29 z 12. Po drugiej iteracji liczba 12 pojawi się na drugiej pozycji w posortowanej tablicy. Zatem po dwóch iteracjach dwie najmniejsze wartości są umieszczane na początku w posortowany sposób.

Ten sam proces dotyczy pozostałych elementów tablicy. Teraz pokazujemy obrazową reprezentację całego procesu sortowania.

Teraz tablica jest całkowicie posortowana.

Złożoność sortowania przez wybór

Przyjrzyjmy się teraz złożoności czasowej sortowania przez wybór w najlepszym przypadku, średnim i najgorszym przypadku. Zobaczymy także złożoność przestrzenną sortowania przez wybór.

1. Złożoność czasowa

Sprawa	Złożoność czasu
Najlepszy przypadek	NA²)
Przeciętny przypadek	NA²)
Najgorszy przypadek	NA²)

NA²)

2. Złożoność przestrzeni

Złożoność przestrzeni	O(1)
Stabilny	TAK

Złożoność przestrzenna sortowania przez wybór wynosi O(1). Dzieje się tak dlatego, że w przypadku sortowania przez wybór do zamiany wymagana jest dodatkowa zmienna.

Implementacja sortowania przez wybór

Przyjrzyjmy się teraz programom sortowania przez wybór w różnych językach programowania.

Program: Napisz program realizujący sortowanie przez wybór w języku C.

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

Wyjście:

Program: Napisz program implementujący sortowanie przez wybór w Javie.

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

Wyjście:

Po wykonaniu powyższego kodu wynikiem będzie -

To tyle na temat artykułu. Mam nadzieję, że artykuł będzie dla Ciebie pomocny i pouczający.

Artykuł ten nie ograniczał się tylko do algorytmu. Omówiliśmy także złożoność sortowania przez wybór, działanie i implementację w różnych językach programowania.

TechCodeview

Algorytm sortowania przez wybór