Basic Sorting

1
// Esempio visuale
2
// Array iniziale: [4, 2, 6, 5, 1, 3]
3

4
// Prima iterazione (5 confronti):
5
// [4, 2, 6, 5, 1, 3] → confronta 4 e 2, scambia
6
// [2, 4, 6, 5, 1, 3] → confronta 4 e 6, non scambia
7
// [2, 4, 6, 5, 1, 3] → confronta 6 e 5, scambia
8
// [2, 4, 5, 6, 1, 3] → confronta 6 e 1, scambia
9
// [2, 4, 5, 1, 6, 3] → confronta 6 e 3, scambia
10
// [2, 4, 5, 1, 3, 6] → 6 è ordinato!
11

12
// Seconda iterazione (4 confronti):
13
// Il 5 risale fino alla penultima posizione
14
// [2, 4, 1, 3, 5, 6] → 5 è ordinato!
15

16
// E così via...

1
// Ordina un array usando Bubble Sort
2
function bubbleSort(array) {
3
  // Loop esterno: controlla quante iterazioni fare
4
  // Parte dalla fine perché a ogni iterazione l'ultimo elemento viene ordinato
5
  for (let i = array.length - 1; i > 0; i--) {
6

7
    // Loop interno: confronta elementi adiacenti
8
    // Si ferma a i perché gli elementi dopo i sono già ordinati
9
    for (let j = 0; j < i; j++) {
10

11
      // Se l'elemento corrente è maggiore del successivo, scambiali
12
      if (array[j] > array[j + 1]) {
13
        // Swap usando una variabile temporanea
14
        let temp = array[j];
15
        array[j] = array[j + 1];
16
        array[j + 1] = temp;
17
      }
18
    }
19
  }
20

21
  // Ritorna l'array ordinato
22
  return array;
23
}

1
// Tecnica standard per scambiare due elementi in un array
2
let temp = array[j];       // Salva il primo elemento
3
array[j] = array[j + 1];   // Sposta il secondo al posto del primo
4
array[j + 1] = temp;       // Metti il primo (salvato in temp) al posto del secondo

1
// Esempio visuale con indici
2
// Array:   [4, 2, 6, 5, 1, 3]
3
// Indici:  [0, 1, 2, 3, 4, 5]
4

5
// Prima iterazione:
6
// min = 0 (valore 4)
7
// Confronta con indice 1 (valore 2): 2 < 4, min = 1
8
// Confronta con indice 2 (valore 6): 6 > 2, min resta 1
9
// Confronta con indice 3 (valore 5): 5 > 2, min resta 1
10
// Confronta con indice 4 (valore 1): 1 < 2, min = 4
11
// Confronta con indice 5 (valore 3): 3 > 1, min resta 4
12
// Scambia indice 0 con indice 4: [1, 2, 6, 5, 4, 3]
13
// ↑ ordinato
14

15
// Seconda iterazione inizia dall'indice 1:
16
// min = 1 (valore 2)
17
// Confronta con tutti i successivi, 2 è già il minimo
18
// Nessuno scambio necessario
19
// [1, 2, 6, 5, 4, 3]
20
//     ↑ ordinato

1
// Ordina un array usando Selection Sort
2
function selectionSort(array) {
3
  // Loop esterno: itera attraverso l'array fino al penultimo elemento
4
  // Ogni iterazione posiziona un elemento nella posizione corretta
5
  for (let i = 0; i < array.length - 1; i++) {
6

7
    // Assume che il minimo sia all'indice corrente i
8
    let min = i;
9

10
    // Loop interno: trova l'elemento minimo nella parte non ordinata
11
    // Inizia da i+1 perché tutto prima di i è già ordinato
12
    for (let j = i + 1; j < array.length; j++) {
13

14
      // Se trova un elemento più piccolo, aggiorna l'indice min
15
      if (array[j] < array[min]) {
16
        min = j;
17
      }
18
    }
19

20
    // Scambia solo se il minimo è diverso dalla posizione corrente
21
    // Evita swap inutili quando l'elemento è già al posto giusto
22
    if (i !== min) {
23
      let temp = array[i];
24
      array[i] = array[min];
25
      array[min] = temp;
26
    }
27
  }
28

29
  // Ritorna l'array ordinato
30
  return array;
31
}

1
// Esempio visuale
2
// Array: [4, 2, 6, 5, 1, 3]
3
//        ↑ già ordinato
4

5
// Iterazione 1: elemento 2
6
// temp = 2
7
// Confronta 2 con 4: 4 > 2, sposta 4 a destra
8
// [4, 4, 6, 5, 1, 3]
9
// Inserisci 2 nella posizione liberata
10
// [2, 4, 6, 5, 1, 3]
11

12
// Iterazione 2: elemento 6
13
// temp = 6
14
// Confronta 6 con 4: 4 < 6, stop
15
// 6 resta al suo posto
16
// [2, 4, 6, 5, 1, 3]
17

18
// Iterazione 3: elemento 5
19
// temp = 5
20
// Confronta 5 con 6: 6 > 5, sposta 6 a destra
21
// Confronta 5 con 4: 4 < 5, stop
22
// Inserisci 5
23
// [2, 4, 5, 6, 1, 3]
24

25
// Iterazione 4: elemento 1
26
// temp = 1
27
// Sposta 6, 5, 4, 2 tutti a destra
28
// Inserisci 1 all'inizio
29
// [1, 2, 4, 5, 6, 3]

1
// Ordina un array usando Insertion Sort
2
function insertionSort(array) {
3
  // Loop esterno: inizia dal secondo elemento (indice 1)
4
  // Il primo elemento è considerato già ordinato
5
  for (let i = 1; i < array.length; i++) {
6

7
    // Salva l'elemento corrente da inserire nella parte ordinata
8
    let temp = array[i];
9

10
    // Loop interno: confronta con gli elementi nella parte ordinata
11
    // Usa var (non let) perché j viene usato fuori dal loop
12
    // j > -1 previene di andare oltre l'inizio dell'array
13
    for (var j = i - 1; array[j] > temp && j > -1; j--) {
14

15
      // Sposta l'elemento più grande una posizione a destra
16
      // Crea spazio per inserire temp
17
      array[j + 1] = array[j];
18
    }
19

20
    // Inserisci temp nella posizione corretta (j+1)
21
    // j è decrementato di 1 dal loop, quindi j+1 è la posizione giusta
22
    array[j + 1] = temp;
23
  }
24

25
  // Ritorna l'array ordinato
26
  return array;
27
}

1
// Array quasi ordinato: [1, 2, 3, 4, 5, 7, 6]
2
//                                      ↑ solo questo fuori posto
3

4
// Insertion Sort fa sostanzialmente UN SOLO PASSAGGIO
5
// Complessità: O(n) invece di O(n²)!
6

7
// Gli algoritmi più avanzati (O(n log n)) non avranno
8
// questo vantaggio e potrebbero essere più lenti in questo caso

1
// Pattern standard per scambiare due elementi
2
// Richiede una variabile temporanea per non perdere dati
3
let temp = array[i];    // Salva il primo valore
4
array[i] = array[j];    // Sovrascrivi il primo con il secondo
5
array[j] = temp;        // Metti il primo (salvato) nel secondo