Selection sort
Ultimo aggiornamento
Il selection sort divide l'array in una zona ordinata a sinistra e una zona non ordinata a destra. A ogni passata scorre la zona non ordinata per trovare l'elemento più piccolo, poi lo scambia nella prima posizione non ordinata, facendo crescere di uno la zona ordinata. Premi play qui sopra per vedere scansione e scambio, o segui un confronto alla volta.
Il selection sort fa sempre lo stesso numero di confronti qualunque sia l'input, ma esegue al massimo n-1 scambi, molti meno del bubble sort, e questo può contare quando le scritture sono costose.
Complessità temporale e spaziale
| Caso | Complessità | Note |
|---|---|---|
| Caso migliore | O(n²) | I confronti avvengono anche se è ordinato |
| Caso medio | O(n²) | Ordine casuale |
| Caso peggiore | O(n²) | Ordinato al contrario |
| Spazio | O(1) | In loco |
| Stabile | No | Gli scambi possono riordinare gli elementi uguali |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Considera l'intero array come non ordinato. |
| 2 | Scorri la zona non ordinata per trovare l'elemento minimo. |
| 3 | Scambia quel minimo nella prima posizione non ordinata. |
| 4 | Sposta il confine di un passo a destra (quella posizione ora è ordinata). |
| 5 | Ripeti finché resta un solo elemento non ordinato. |
Esempio svolto
Ordinamento di [5, 2, 4, 1]:
| Passata | Array | Azione |
|---|---|---|
| Inizio | [5, 2, 4, 1] | L'intero array è non ordinato. |
| 1 | [1, 2, 4, 5] | Scorri [5, 2, 4, 1], il minimo è 1 all'indice 3; scambialo con l'indice 0. |
| 2 | [1, 2, 4, 5] | Scorri [2, 4, 5], il minimo è 2, già all'indice 1; lo scambi con se stesso. |
| 3 | [1, 2, 4, 5] | Scorri [4, 5], il minimo è 4, già all'indice 2; nessuno spostamento necessario. |
| Fine | [1, 2, 4, 5] | Resta solo 5, quindi è già al suo posto. |
Quando usare il selection sort
| Usalo quando | Evitalo quando |
|---|---|
Le scritture sono costose: fa al massimo n-1 scambi. | L'array è grande: dominano i confronti O(n²). |
| Ti serve un ordinamento in loco semplice e facile da implementare. | Ti serve un ordinamento stabile che preservi l'ordine delle chiavi uguali. |
La memoria è poca: usa solo O(1) di spazio extra. | I dati sono quasi ordinati: non può terminare prima come l'insertion sort. |
| L'insieme di dati è minuscolo e contano prestazioni prevedibili. | Conta la velocità complessiva: gli ordinamenti O(n log n) come il quicksort sono molto più veloci. |
Codice Selection Sort
Un'implementazione di Selection Sort pulita ed eseguibile in Python, JavaScript, Java, C++, C, Pseudocode. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Selection Sort in Python
Python
1def selection_sort(a):2 n = len(a)3 for i in range(n - 1):4 # Find the smallest element in the unsorted tail5 min_idx = i6 for j in range(i + 1, n):7 if a[j] < a[min_idx]:8 min_idx = j9 a[i], a[min_idx] = a[min_idx], a[i]10 return a11
12
13nums = [64, 25, 12, 22, 11]14print("Before:", nums)15selection_sort(nums)16print("After: ", nums)Codice Selection Sort in JavaScript
JavaScript
1function selectionSort(a) {2 for (let i = 0; i < a.length - 1; i++) {3 let min = i;4 // Find the smallest element in the unsorted tail5 for (let j = i + 1; j < a.length; j++) {6 if (a[j] < a[min]) min = j;7 }8 if (min !== i) [a[i], a[min]] = [a[min], a[i]];9 }10 return a;11}12
13const data = [5, 2, 9, 1, 7, 3];14console.log("Before:", data);15console.log("Sorted:", selectionSort([...data]));Codice Selection Sort in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void selectionSort(int[] arr) {5 for (int i = 0; i < arr.length - 1; i++) {6 int minIndex = i;7 // Find the smallest value in the unsorted part8 for (int j = i + 1; j < arr.length; j++) {9 if (arr[j] < arr[minIndex]) minIndex = j;10 }11 int tmp = arr[i];12 arr[i] = arr[minIndex];13 arr[minIndex] = tmp;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {29, 10, 14, 37, 13, 5};19 System.out.println("Before: " + Arrays.toString(arr));20 selectionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Codice Selection Sort in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void selectionSort(std::vector<int>& a) {11 for (size_t i = 0; i + 1 < a.size(); ++i) {12 // Find the smallest element in the unsorted suffix13 size_t minIdx = i;14 for (size_t j = i + 1; j < a.size(); ++j) {15 if (a[j] < a[minIdx]) minIdx = j;16 }17 std::swap(a[i], a[minIdx]);18 }19}20
21int main() {22 std::vector<int> data = {29, 10, 14, 37, 13, 5};23 std::cout << "Before: ";24 printVec(data);25 selectionSort(data);26 std::cout << "After: ";27 printVec(data);28 return 0;29}Codice Selection Sort in C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void selectionSort(int a[], int n) {9 for (int i = 0; i < n - 1; i++) {10 // Find the smallest element in the unsorted suffix11 int minIdx = i;12 for (int j = i + 1; j < n; j++) {13 if (a[j] < a[minIdx]) minIdx = j;14 }15 int tmp = a[i];16 a[i] = a[minIdx];17 a[minIdx] = tmp;18 }19}20
21int main(void) {22 int data[] = {29, 10, 14, 37, 13, 5};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 selectionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}Codice Selection Sort in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE i : INTEGER12DECLARE j : INTEGER13DECLARE minIndex : INTEGER14DECLARE temp : INTEGER15
16// Select the smallest remaining value and swap it into place17FOR i ← 1 TO n - 118 minIndex ← i19 FOR j ← i + 1 TO n20 IF nums[j] < nums[minIndex] THEN21 minIndex ← j22 ENDIF23 NEXT j24 IF minIndex <> i THEN25 temp ← nums[i]26 nums[i] ← nums[minIndex]27 nums[minIndex] ← temp28 ENDIF29NEXT i30
31FOR i ← 1 TO n32 OUTPUT nums[i]33NEXT iDomande frequenti sul selection sort
Qual è la complessità temporale del selection sort?
Il selection sort è
O(n²) in tutti i casi, migliore, medio e peggiore, perché scorre sempre l'intera zona non ordinata per trovare ogni minimo. Usa O(1) di spazio extra.Il selection sort è stabile?
La versione standard in loco non è stabile, perché scambiare al suo posto un minimo lontano può far scavalcare un elemento uguale a un altro. Esiste una variante stabile, ma richiede di spostare gli elementi invece di scambiarli.
Quando è utile il selection sort?
È utile quando il costo di scrittura in memoria è alto, dato che esegue al massimo
n-1 scambi: il minimo possibile per un ordinamento per confronto che sposta gli elementi.Qual è la differenza tra selection sort e bubble sort?
Sono entrambi ordinamenti per confronto
O(n²), ma il selection sort fa al massimo n-1 scambi, mentre il bubble sort può farne fino a O(n²). Il bubble sort può anche accorgersi che un array è già ordinato e fermarsi prima, mentre il selection sort esegue sempre tutte le passate.Meglio il selection sort o l'insertion sort?
Nella maggior parte dei casi preferisci l'insertion sort: è stabile, richiede
O(n) su dati quasi ordinati ed è più veloce in media. Scegli il selection sort solo quando la priorità è ridurre al minimo il numero di scritture, dato che garantisce al massimo n-1 scambi.Perché il selection sort richiede sempre O(n²) anche su un array ordinato?
Il selection sort non ha modo di sapere che un elemento è già il minimo senza scorrere il resto della zona non ordinata, quindi esegue ogni confronto a ogni passata indipendentemente dall'ordine dell'input. Questo significa che il caso migliore coincide con il peggiore,
O(n²), a differenza dell'insertion sort o del bubble sort, che possono interrompersi prima.Risorse correlate
Altre visualizzazioni
