Articolo originale: Sorting Algorithms Explained with Examples in JavaScript, Python, Java, and C++
Cos'è un algoritmo di ordinamento?
Gli algoritmi di ordinamento sono un insieme di istruzioni che prendono un array o una lista come input e ne riorganizzano gli elementi in un ordine particolare.
I più comuni operano in ordine numerico o in una forma di ordine alfabetico (lessicografico) e possono ordinare in modo ascendente (A-Z, 0-9) o discendente (Z-A, 9-0).
Perché gli algoritmi di ordinamento sono importanti?
Dato che spesso sono in grado di ridurre la complessità di un problema, gli algoritmi di ordinamento sono estremamente importanti in informatica. Questi algoritmi hanno applicazioni dirette in algoritmi di ricerca, algoritmi di database, metodi divide et impera, algoritmi di strutture dati e molti altri.
Pro e contro degli algoritmi di ordinamento
Nello scegliere un algoritmo di ordinamento, occorre che ci poniamo qualche domanda. Quanto è grande l'insieme da ordinare? Quanta memoria è disponibile? Dobbiamo aggiungere altri dati in futuro?
Le risposte a queste domande possono determinare quale algoritmo si adatterà al meglio a ogni situazione. Alcuni algoritmi, come il merge sort, possono richiedere molto spazio o memoria per essere eseguiti, mentre l'insertion sort non è sempre il più rapido, ma non necessita di molte risorse per essere eseguito.
Dovresti determinare quali sono i requisiti nel tuo caso e considerare le limitazioni del tuo sistema prima di decidere quale algoritmo di ordinamento usare.
Algoritmi di ordinamento comuni
Ecco alcuni dei più comuni algoritmi di ordinamento:
- Selection sort (ordinamento per selezione)
- Bubble sort (ordinamento a bolla)
- Insertion sort (ordinamento a inserimento)
- Merge sort
- Quick sort
- Heapsort (ordinamento per heap)
- Counting sort
- Radix sort
- Bucket sort
Ma prima di affrontarli uno per uno, parliamo un po' di come classificare gli algoritmi di ordinamento.
Classificazione degli algoritmi di ordinamento
Gli algoritmi di ordinamento possono essere categorizzati in base ai seguenti parametri:
- Il numero richiesto di scambi o inversioni: è il numero di volte in cui l'algoritmo scambia gli elementi per riorganizzare l'input. Selection sort richiede il numero minimo di scambi.
- Il numero di confronti: è il numero di volte che un algoritmo confronta gli elementi per riorganizzare l'input. Usando la notazione O-grande, gli algoritmi di ordinamento elencati precedentemente richiedono almeno
O(nlogn)confronti nel caso migliore eO(n^2)confronti nel caso peggiore per la maggior parte degli output. - Fanno o non fanno uso della ricorsione: alcuni algoritmi di ordinamento, come quick sort, usano tecniche ricorsive per ordinare l'input, Altri algoritmi di ordinamento, come selection sort o insertion sort, usano tecniche non ricorsive. Infine, alcuni come merge sort, usano sia tecniche ricorsive che non per ordinare l'input.
- Sono stabili o instabili: gli algoritmi di ordinamento stabili mantengono l'ordine relativo degli elementi con valori o chiavi uguali. Quelli instabili non mantengono l'ordine relativo di elementi con valori/chiavi uguali.
Ad esempio, immagina di avere l'array di input[1, 2, 3, 2, 4]. Per evidenziare la differenza tra i due valori uguali2, denotiamoli con2ae2b, ottenendo l'array di input[1, 2a, 3, 2b, 4].
Gli algoritmi di ordinamento stabili mantengono l'ordine di2ae2b, così che l'output sarà[1, 2a, 2b, 3, 4]. Quelli instabili non mantengono l'ordine dei valori uguali e l'array di output potrebbe essere[1, 2b, 2a, 3, 4].
Insertion sort, merge sort e bubble sort sono stabili. Heap sort e quick sort sono instabili. - La quantità di spazio extra richiesto: alcuni algoritmi di ordinamento possono ordinare una lista senza crearne una nuova. Questi sono conosciuti come algoritmi di ordinamento in loco (o in place) e richiedono uno spazio di memoria extra costante
O(1). Invece, gli algoritmi di ordinamento non in loco creano una nuova lista ordinando l'input.
Insertion sort e quick sort sono in loco, dato che gli elementi vengono spostati intorno a un elemento pivot e non fanno uso di un array separato.
Merge sort è un esempio di ordinamento non in loco, dato che la dimensione dell'input viene assegnata in anticipo per contenere l'output durante il processo di ordinamento, richiedendo memoria aggiuntiva.
Bucket Sort
Bucket sort è un algoritmo di ordinamento che opera sugli elementi dividendoli in diversi bucket per poi ordinare individualmente i bucket. Ognuno di essi viene ordinato separatamente usando uno specifico algoritmo di ordinamento come insertion sort o applicando ricorsivamente bucket sort.
Bucket sort è principalmente utile quando l'input è uniformemente distribuito in un intervallo. Ad esempio, immagina di avere un grande array di numeri decimali distribuiti uniformemente tra un estremo inferiore e un estremo superiore.
Potresti utilizzare un altro algoritmo di ordinamento come merge sort o quick sort, tuttavia, questi algoritmi garantiscono nel caso migliore una complessità temporale di O(nlogn).
Usando bucket sort, l'ordinamento dello stesso array può avvenire in un tempo O(n).
Pseudo-codice per Bucket Sort:
funzione bucketSort(array di numeri a,intero n)
per ogni numero intero x in n
inserisci x in bucket[n*x];
per ogni bucket
ordina(bucket);Counting Sort
L'algoritmo counting sort crea inizialmente una lista con il conteggio o le occorrenze di ogni valore unico nell'input, per poi generare la lista finale ordinata in base alla lista con le occorrenze.
Una cosa importante da tenere a mente è che counting sort può essere usato soltanto conoscendo a priori l'intervallo dei valori possibili.
Esempio:
Hai una lista di interi da 0 a 5:
input = [2, 5, 3, 1, 4, 2]Hai bisogno di creare una lista con il conteggio di ogni valore unico nella lista input. Dato sai che l'intervallo dei valori di input è da 0 a 5, puoi creare una lista con 5 segnaposti per i valori da 0 a 5, rispettivamente:
count = [0, 0, 0, 0, 0, 0]
# val: 0 1 2 3 4 5Poi, percorri la lista input iterando sull'indice per ogni valore.
Ad esempio, il primo valore della lista input è 2, quindi aggiungi uno al valore al secondo indice della lista count list, che rappresenta il valore 2:
count = [0, 0, 1, 0, 0, 0]
# val: 0 1 2 3 4 5Il valore successivo nella lista input è 5, quindi aggiungi uno al valore all'ultimo indice della lista count, che rappresenta il valore 5:
count = [0, 0, 1, 0, 0, 1]
# val: 0 1 2 3 4 5Continui finché non hai il conteggio totale di ogni valore nella lista input:
count = [0, 1, 2, 1, 1, 1]
# val: 0 1 2 3 4 5Infine, dato che conosci quante volte appare ogni valore nella lista input, puoi creare facilmente una lista output ordinata. Itera sulla lista count e, per ogni conteggio, aggiungi il valore corrispondente
(0 - 5) all'array output quel numero di volte.
Ad esempio, non ci sono 0 nella lista input list, ma il valore 1 è presente una volta, quindi lo aggiungi all'array output una volta:
output = [1]Il valore 2 è presente due volte, quindi lo aggiungi alla lista output due volte:
output = [1, 2, 2]E così via, finché non ottieni la lista finale output ordinata:
output = [1, 2, 2, 3, 4, 5]Proprietà
- Complessità spaziale:
O(k) - Performance nel caso migliore:
O(n+k) - Performance media:
O(n+k) - Performance nel caso peggiore:
O(n+k) - Stabile: sì (
kè nell'intervallo degli elementi dell'array)
Implementazione in JavaScript
let numeri = [1, 4, 1, 2, 7, 5, 2];
let conteggio = [];
let output = [];
let i = 0;
let max = Math.max(...numeri);
// inizializza counter
for (i = 0; i <= max; i++) {
conteggio[i] = 0;
}
// inizializza l'array output
for (i = 0; i < numeri.length; i++) {
output[i] = 0;
}
for (i = 0; i < numeri.length; i++) {
conteggio[numeri[i]]++;
}
for (i = 1; i < conteggio.length; i++) {
conteggio[i] += conteggio[i - 1];
}
for (i = numeri.length - 1; i >= 0; i--) {
output[--conteggio[numeri[i]]] = numeri[i];
}
// array output ordinato
for (i = 0; i < output.length; i++) {
console.log(output[i]);
}
Implementazione in C++
#include <iostream>
#include <vector>
void countSort(int upperBound, int lowerBound, std::vector < int > numbersToSort) // limite inferiore (lowerBound) e superiore (upperBound) dei numeri in vector
{
int i;
int range = upperBound - lowerBound; // Crea un range largo abbastanza da contenere tutti i numeri tra il minimo e il massimo
std::vector < int > counts(range + 1); // Inizializza counts della dimensione del range
std::fill(counts.begin(), counts.end(), 0); // Riempi il vettore di zeri
std::vector < int > storedNumbers(numbersToSort.size()); // Inizializza storedNumbers della stessa dimensione del vettore di input
std::fill(storedNumbers.begin(), storedNumbers.end(), 0); // Riempi il vettore storedNumbers di zeri
for (i = 0; i < numbersToSort.size(); i++) {
int index = numbersToSort[i] - lowerBound; // For example, if 5 is the lower bound and numbersToSort[i] is 5, the inPer esempio, se 5 è il limite inferiore, e numbersToSort[i] è 5, l'indice sarà 0
counts[index] += 1; // e il conteggio di 5 è salvato in counts[0]
}
for (i = 1; i < counts.size(); i++) {
counts[i] += counts[i - 1];
}
for (i = numbersToSort.size() - 1; i >= 0; i--) { // Copia gli elementi da numbersToSort a storedNumbers seguento count
storedNumbers[--counts[numbersToSort[i] - lowerBound]] = numbersToSort[i];
}
for (i = 0; i < storedNumbers.size(); i++) {
std::cout << storedNumbers[i];
if (i != storedNumbers.size() - 1)
std::cout << ", ";
}
std::cout << std::endl;
}Implementazione in Swift
func countingSort(_ array: [Int]) {
// Crea un array per salvare il conteggio di ogni elemento
let maxElement = array.max() ?? 0
var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
for element in array {
countArray[element] += 1
}
for i in 1..<countArray.count {
countArray[i] += countArray[i - 1]
}
var sortedArray = [Int](repeating: 0, count: array.count)
// copia gli elementi da array a sortedArray seguendo count
for i in (0..<array.count).reversed() {
countArray[array[i]] -= 1
sortedArray[countArray[array[i]]] = array[i]
}
print(sortedArray)
}
Insertion Sort
Insertion sort è un semplice algoritmo di ordinamento adatto a un numero ridotto di elementi.
Esempio:
Insertion sort confronta l'elemento key con gli elementi precedenti. Se gli elementi precedenti sono più grandi dell'elemento key, vengono spostati nella posizione successiva.
Inizia dall'indice 1 fino alla lunghezza dell'array di input.
[ 8 3 5 1 4 2 ]Step 1 :
key = 3 //partendo dal 1° indice.key viene confrontato con gli elementi precedenti.
In questo caso, key viene confrontato con 8. Dato che 8 > 3, l'8 viene spostato nella posizione successiva e key inserita nella precedente.
Risultato: [ 3 8 5 1 4 2 ]Step 2 :
![[ 3 8 5 1 4 2 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/2.png?raw=true)
key = 5 //2° indice
8 > 5 //sposta 8 al 2° indice e inserisce 5 al 1° indice.
Risultato: [ 3 5 8 1 4 2 ]
Step 3 :
![[ 3 5 8 1 4 2 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/3.png?raw=true)
key = 1 //3° indice
8 > 1 => [ 3 5 1 8 4 2 ]
5 > 1 => [ 3 1 5 8 4 2 ]
3 > 1 => [ 1 3 5 8 4 2 ]
Risultato: [ 1 3 5 8 4 2 ]
Step 4 :
![[ 1 3 5 8 4 2 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/4.png?raw=true)
key = 4 //4° indice
8 > 4 => [ 1 3 5 4 8 2 ]
5 > 4 => [ 1 3 4 5 8 2 ]
3 > 4 ≠> stop
Risultato: [ 1 3 4 5 8 2 ]
Step 5 :
![[ 1 3 4 5 8 2 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/5.png?raw=true)
key = 2 //5° indice
8 > 2 => [ 1 3 4 5 2 8 ]
5 > 2 => [ 1 3 4 2 5 8 ]
4 > 2 => [ 1 3 2 4 5 8 ]
3 > 2 => [ 1 2 3 4 5 8 ]
1 > 2 ≠> stop
Risultato: [1 2 3 4 5 8]
![[ 1 2 3 4 5 8 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/6.png?raw=true)
L'algoritmo mostrato qui sotto è una versione leggermente ottimizzata per evitare di scambiare l'elemento key in ogni iterazione. Qui, l'elemento key verrà scambiato alla fine dell'iterazione (step).
InsertionSort(arr[])
for j = 1 to arr.length
key = arr[j]
i = j - 1
while i > 0 and arr[i] > key
arr[i+1] = arr[i]
i = i - 1
arr[i+1] = key
Ecco l'implementazione dettagliata in JavaScript:
function insertion_sort(A) {
var len = array_length(A);
var i = 1;
while (i < len) {
var x = A[i];
var j = i - 1;
while (j >= 0 && A[j] > x) {
A[j + 1] = A[j];
j = j - 1;
}
A[j + 1] = x;
i = i + 1;
}
}E un'implementazione breve in Swift:
var array = [8, 3, 5, 1, 4, 2]
func insertionSort(array: inout [Int]) -> [Int] {
for j in 0..<array.count {
let key = array[j]
var i = j - 1
while i > 0 && array[i] > key {
array[i + 1] = array[i]
i = i - 1
}
array[i + 1] = key
}
return array
}
Qui sotto puoi vedere un esempio in Java:
public int[] insertionSort(int[] arr) {
for (j = 1; j < arr.length; j++) {
int key = arr[j]
int i = j - 1
while (i > 0 and arr[i] > key) {
arr[i + 1] = arr[i]
i -= 1
}
arr[i + 1] = key
}
return arr;
}E infine in C:
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}Proprietà:
- Complessità spaziale:
O(1) - Complessità temporale:
O(n),O(n* n),O(n* n)rispettivamente per caso migliore, media e caso peggiore. - Caso migliore: l'array è già ordinato
- Media: l'array è ordinato in modo casuale
- Caso peggiore: l'array è ordinato è invertito.
- Ordinamento in loco: sì
- Stabile: sì
Heapsort
Heapsort è un efficiente algoritmo di ordinamento basato sull'uso di max/min heap. Un heap è una struttura di dati ad albero che soddisfa la proprietà di heap: per un max heap, la chiave di ogni nodo è minore o uguale alla chiave del suo genitore (se ne possiede uno).
Questa proprietà può essere sfruttata per accedere all'elemento massimo nell'heap in un tempo O(logn), usando il metodo maxHeapify. Svolgiamo questa operazione n volte, ogni volta muovendo il massimo in cima all'heap ed estraendolo per inserirlo nell'array ordinato. Dunque, dopo n iterazioni avremo una versione ordinata dell'array di input.
È un algoritmo in loco e richiede di costruire inizialmente una struttura di dati heap. L'algoritmo è anche instabile, che significa che in seguito al confronto di oggetti con la stessa chiave, l'ordine originale non viene preservato.
Questo algoritmo viene eseguito in un tempo O(nlogn) e spazio addizionale O(1) (O(n) includendo lo spazio richiesto per memorizzare i dati di input) dato che tutte le operazioni vengono eseguite completamente in loco.
La complessità temporale di heapsort nel caso migliore, medio e peggiore è O(nlogn). Sebbene heapsort abbia una migliore complessità nel caso peggiore rispetto a quicksort, in pratica, quicksort viene eseguito più velocemente se ben implemenetato. È un algortimo basato sul confronto, quindi può essere usato per insiemi di dati non numerici, in quanto una certa relazione (proprietà heap) può essere definita tra gli elementi.
Qui sotto puoi vedere l'implementazione in Java:
import java.util.Arrays;
public class Heapsort {
public static void main(String[] args) {
// array di test
Integer[] arr = {
1,
4,
3,
2,
64,
3,
2,
4,
5,
5,
2,
12,
14,
5,
3,
0,
-1
};
String[] strarr = {
"hope you find this helpful!",
"wef",
"rg",
"q2rq2r",
"avs",
"erhijer0g",
"ewofij",
"gwe",
"q",
"random"
};
arr = heapsort(arr);
strarr = heapsort(strarr);
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(strarr));
}
// TEMPO O(nlogn), SPAZIO O(1), NON STABOILE
public static < E extends Comparable < E >> E[] heapsort(E[] arr) {
int heaplength = arr.length;
for (int i = arr.length / 2; i > 0; i--) {
arr = maxheapify(arr, i, heaplength);
}
for (int i = arr.length - 1; i >= 0; i--) {
E max = arr[0];
arr[0] = arr[i];
arr[i] = max;
heaplength--;
arr = maxheapify(arr, 1, heaplength);
}
return arr;
}
// Crea maxheap dall'array
public static < E extends Comparable < E >> E[] maxheapify(E[] arr, Integer node, Integer heaplength) {
Integer left = node * 2;
Integer right = node * 2 + 1;
Integer largest = node;
if (left.compareTo(heaplength) <= 0 && arr[left - 1].compareTo(arr[node - 1]) >= 0) {
largest = left;
}
if (right.compareTo(heaplength) <= 0 && arr[right - 1].compareTo(arr[largest - 1]) >= 0) {
largest = right;
}
if (largest != node) {
E temp = arr[node - 1];
arr[node - 1] = arr[largest - 1];
arr[largest - 1] = temp;
maxheapify(arr, largest, heaplength);
}
return arr;
}
}E in C++:
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main() {
int arr[] = {
12,
11,
13,
5,
6,
7
};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}Radix sort
Prerequisito: Counting sort
Quick sort, merge sort e heapsort sono algoritmi di ordinamento basati sul confronto. Counting sort non lo è. Ha una complessità di O(n+k), dove k è l'elemento massimo dell'array di input. Quindi, se k è O(n), counting sort diventa un ordinamento lineare, che è preferibile rispetto aa algoritmi di ordinamento basati sul confronto che hanno complessità temporale O(nlogn).
L'idea è di estendere l'algoritmo counting sort per ottenere una migliore complessità temporale quando k tende a O(n^2). Da qui, l'idea di Radix Sort.
L'algoritmo:
Per ogni cifra i, dove i varia dalla cifra meno significativa alla più significativa di un numero, ordina l'array di input usando l'algoritmo counting sort secondo la cifra i-esima. Usiamo counting sort perché è stabile.
Consideriamo come esempio l'array di input:
10, 21, 17, 34, 44, 11, 654, 123L'algoritmo ordinerà l'array di input secondo la cifra delle unità (quella meno significativa).
0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:Così l'array diventa:
10, 21, 11, 123, 24, 44, 654, 17Adesso, l'ordinamento avviene in base alla cifra delle decine:
0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:L'array diventa:
10, 11, 17, 21, 123, 34, 44, 654Infine, l'ordinamento avvien secondo la cifra delle centinaia (quella più significativa):
0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:L'array diventa:
10, 11, 17, 21, 34, 44, 123, 654ed è ordinato. Ecco come funziona quest'algoritmo.
Ecco un'implementazione in C:
void countsort(int arr[], int n, int place) {
int i, freq[range] = {
0
}; //range for integers is 10 as digits range from 0-9
int output[n];
for (i = 0; i < n; i++)
freq[(arr[i] / place) % range]++;
for (i = 1; i < range; i++)
freq[i] += freq[i - 1];
for (i = n - 1; i >= 0; i--) {
output[freq[(arr[i] / place) % range] - 1] = arr[i];
freq[(arr[i] / place) % range]--;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
void radixsort(ll arr[], int n, int maxx) { //maxx is the maximum element in the array
int mul = 1;
while (maxx) {
countsort(arr, n, mul);
mul *= 10;
maxx /= 10;
}
}Selection Sort
Selection sort è uno degli algoritmi di ordinamento più semplici. Questo algoritmo prende il nome dal modo in cui itera sull'array: seleziona l'elemento più piccolo attuale e lo mette al suo posto.
Vediamo come funziona:
- Trova l'elemento più piccolo dell'array e lo scambia con il primo elemento.
- Trova il secondo elemento più piccolo dell'array e lo scambia con il secondo elemento dell'array.
- Trova il terzo elemento più piccolo dell'array e lo scambia con il terzo elemento dell'array.
- Ripete il processo di trovare l'elemento più piccolo successivo e posizionarlo correttamente finché l'array non è completamente ordinato.
Ma come scriveresti il codice per trovare l'indice del secondo valore nell'array?
Un modo semplice è notare che il valore più piccolo è già stato scambiato e posizionato all'indice 0, quindi il problema si riduce alla ricerca dell'elemento più piccolo partendo dall'indice 1.
Il numero di confronti di chiavi di selection sort è pari a N(N − 1)/2.
Implementazione in C/C++
Il seguente programma in C++ contiene un'implementazione iterativa e ricorsiva dell'algoritmo selection sort. Entrambe le implementazioni sono invocate nella funzione main().
#include <iostream>
#include <string>
using namespace std;
template < typename T, size_t n >
void print_array(T
const ( & arr)[n]) {
for (size_t i = 0; i < n; i++)
std::cout << arr[i] << ' ';
cout << "\n";
}
int minIndex(int a[], int i, int j) {
if (i == j)
return i;
int k = minIndex(a, i + 1, j);
return (a[i] < a[k]) ? i : k;
}
void recurSelectionSort(int a[], int n, int index = 0) {
if (index == n)
return;
int k = minIndex(a, index, n - 1);
if (k != index)
swap(a[k], a[index]);
recurSelectionSort(a, n, index + 1);
}
void iterSelectionSort(int a[], int n) {
for (int i = 0; i < n; i++) {
int min_index = i;
int min_element = a[i];
for (int j = i + 1; j < n; j++) {
if (a[j] < min_element) {
min_element = a[j];
min_index = j;
}
}
swap(a[i], a[min_index]);
}
}
int main() {
int recurArr[6] = {
100,
35,
500,
9,
67,
20
};
int iterArr[5] = {
25,
0,
500,
56,
98
};
cout << "Recursive Selection Sort" << "\n";
print_array(recurArr); // 100 35 500 9 67 20
recurSelectionSort(recurArr, 6);
print_array(recurArr); // 9 20 35 67 100 500
cout << "Iterative Selection Sort" << "\n";
print_array(iterArr); // 25 0 500 56 98
iterSelectionSort(iterArr, 5);
print_array(iterArr); // 0 25 56 98 500
}Implementazione in JavaScript
function selection_sort(A) {
var len = A.length;
for (var i = 0; i < len - 1; i = i + 1) {
var j_min = i;
for (var j = i + 1; j < len; j = j + 1) {
if (A[j] < A[j_min]) {
j_min = j;
} else {}
}
if (j_min !== i) {
swap(A, i, j_min);
} else {}
}
}
function swap(A, x, y) {
var temp = A[x];
A[x] = A[y];
A[y] = temp;
}
Implementazione in Python
def seletion_sort(arr):
if not arr:
return arr
for i in range(len(arr)):
min_i = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_i]:
min_i = j
(arr[i], arr[min_i]) = (arr[min_i], arr[i])Implementazione in Java
public void selectionsort(int array[]) {
int n = array.length; // metodo per trovare la lunghezza di un array
for (int i = 0; i < n - 1; i++) {
int index = i;
int min = array[i]; // prende l'elemento minimo come elemento i-esimo dell'array
for (int j = i + 1; j < n; j++) {
if (array[j] < array[index]) {
index = j;
min = array[j];
}
}
int t = array[index]; // scambia il posto degli elemento
array[index] = array[i];
array[i] = t;
}
}Implementazione in MATLAB
function [sorted] = selectionSort(unsorted)
len = length(unsorted);
for i = 1:1:len
minInd = i;
for j = i+1:1:len
if unsorted(j) < unsorted(minInd)
minInd = j;
end
end
unsorted([i minInd]) = unsorted([minInd i]);
end
sorted = unsorted;
end
Proprietà
- Complessità spaziale:
O(n) - Complessità temporale:
O(n^2) - Ordinamento in loco: sì
- Stabile: No
Bubble Sort
Bubble sort è un semplice algoritmo che ordina una lista, permettendo sia ai valori alti che bassi di raggiungerne la cima. L'algoritmo percorre la lista e confronta i valori adiacenti, scambiandoli se non sono nell'ordine corretto.
La complessità nel caso peggiore è di O(n^2). Bubble sort è molto lento se comparato ad altri algoritmi di ordinamento come quick sort. Il lato positivo è che è uno degli algoritmi di ordinamento più facili da comprendere e scrivere da zero.
Da un punto di vista tecnico, bubble sort è adeguato per ordinare array di piccole dimensioni o se è necessario eseguire un algoritmo di ordinamento su un computer con risorse di memoria particolarmente ridotte.
Esempio:
Primo passagio della lista:
- Partendo da
[4, 2, 6, 3, 9], l'algoritmo compara i primi due elementi nell'array, 4 e 2. Li scambia perché 2 < 4:[2, 4, 6, 3, 9] - Confronta i due valori successivi, 4 and 6. Dato che 4 < 6, risultano già in ordine e l'algoritmo passa avanti:
[2, 4, 6, 3, 9] - I due valori successivi vengono scambiati perché 3 < 6:
[2, 4, 3, 6, 9] - Gli ultimi due valori, 6 e 9, sono già in ordine e l'algoritmo non li scambia.
Secondo passaggio della lista:
- 2 < 4, quindi non c'è bisogno di scambiare le posizioni:
[2, 4, 3, 6, 9] - L'algoritmo scambia i valori successivi perché 3 < 4:
[2, 3, 4, 6, 9] - Non c'è scambio per i valori successivi, in quanto 4 < 6:
[2, 3, 4, 6, 9] - E ancora, 6 < 9, quindi non avviene nessuno scambio:
[2, 3, 4, 6, 9]
La lista adesso è ordinata, ma l'algoritmo bubble sort non se ne accorge. Invece, necessita di completare un altro passaggio completo della lista senza scambiare alcun valore per sapere che la lista è ordinata.
Terzo passaggio della lista:
[2, 3, 4, 6, 9]=>[2, 3, 4, 6, 9][2, 3, 4, 6, 9]=>[2, 3, 4, 6, 9][2, 3, 4, 6, 9]=>[2, 3, 4, 6, 9][2, 3, 4, 6, 9]=>[2, 3, 4, 6, 9]
Chiaramente, bubble sort è lontano dall'essere l'algoritmo di ordinamento più efficiente. Ad ogni modo, è semplice da capire e da mettere in pratica.
Proprietà
- Complessità spaziale:
O(1) - Performance nel caso migliore:`O(n)`
- Performance media:
O(n*n) - Performance nel caso peggiore:
O(n*n) - Stabile: sì
Esempio in JavaScript
let arr = [1, 4, 7, 45, 7, 43, 44, 25, 6, 4, 6, 9],
sorted = false;
while (!sorted) {
sorted = true;
for (var i = 0; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
let temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
sorted = false;
}
}
}Esempio in Java
public class BubbleSort {
static void sort(int[] arr) {
int n = arr.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int x = 1; x < (n - i); x++) {
if (arr[x - 1] > arr[x]) {
temp = arr[x - 1];
arr[x - 1] = arr[x];
arr[x] = temp;
}
}
}
}
public static void main(String[] args) {
for (int i = 0; i < 15; i++) {
int arr[i] = (int)(Math.random() * 100 + 1);
}
System.out.println("array before sorting\n");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
bubbleSort(arr);
System.out.println("\n array after sorting\n");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}Esempio in C++
// implementazione ricorsiva
void bubblesort(int arr[], int n) {
if (n == 1) // caso base
return;
bool swap_flag = false;
for (int i = 0; i < n - 1; i++) { // dopo questo passaggio l'elemento più grande è spostato alla posizione desiderata
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swap_flag = true;
}
}
// se non sono stati scambiati elementi nel loop, allora restituisci che l'array è ordinato
if (swap_flag == false)
return;
bubblesort(arr, n - 1); // ricorsione per il resto dell'array
}Esempio in Swift
func bubbleSort(_ inputArray: [Int]) -> [Int] {
// assicurati che l'array di input ha più di un elemento
guard inputArray.count > 1 else { return inputArray }
// gli argomenti delle funzioni sono costandi di default, quindi facciamo una copia
var numbers = inputArray
for i in 0..<(numbers.count - 1) {
for j in 0..<(numbers.count - i - 1) {
if numbers[j] > numbers[j + 1] {
numbers.swapAt(j, j + 1)
}
}
}
// restituisce l'array ordinato
return numbers
}
Esempio in Python
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
print arr
Esempio in PHP
function bubble_sort($arr) {
$size = count($arr)-1;
for ($i=0; $i<$size; $i++) {
for ($j=0; $j<$size-$i; $j++) {
$k = $j+1;
if ($arr[$k] < $arr[$j]) {
// Scambia elementi agli indici: $j, $k
list($arr[$j], $arr[$k]) = array($arr[$k], $arr[$j]);
}
}
}
return $arr; // restituisci l'array ordinato
}
$arr = array(1,3,2,8,5,7,4,0);
print("Prima di ordinare");
print_r($arr);
$arr = bubble_sort($arr);
print("Dopo aver ordinato usando Bubble Sort");
print_r($arr);
Esempio in C
#include <stdio.h>
int BubbleSort(int array[], int n);
int main(void) {
int arr[] = {
10,
2,
3,
1,
4,
5,
8,
9,
7,
6
};
BubbleSort(arr, 10);
for (int i = 0; i < 10; i++) {
printf("%d", arr[i]);
}
return 0;
}
int BubbleSort(int array[], n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) //n is length of array
{
if (array[j] > array[j + 1]) // For decreasing order use
{
int swap = array[j];
array[j] = array[j + 1];
array[j + 1] = swap;
}
}
}
}Quick Sort
Quick sort è un efficiente algoritmo di ordinamento divide et impera. La sua complessità temporale nel caso medio è O(nlog(n)), mentre quella nel caso peggiore è O(n^2) in base alla selezione dell'elemento pivot, che divide l'array attuale in due sotto-array.
Ad esempio, la complessità temporale di quick sort è approssimativamente O(nlog(n)) quando la selezione del pivot divide l'array originale in due sotto-array di dimensione quasi uguale.
D'altra parte, se l'algoritmo che seleziona l'elemento pivot dell'array di input restituisce costantemente 2 sotto-array con una grande differenza in termini di dimensione, l'algoritmo quick sort può raggiungere la complessità temporale del caso peggiore pari a O(n^2).
Gli step coinvolti in quick sort sono:
- Scelta dell'elemento pivot, in questo caso, l'ultimo elemento dell'array.
- Partizione: ordinamento dell'array in modo che tutti gli elementi minori del pivot siano a sinistra e tutti quelli maggiori a destra.
- Chiamata ricorsiva di quick sort, considerando il pivot precedente per dividere in modo adeguato gli array di sinistra e destra (Una discussione più dettagliata è presente nei commenti qui sotto).
Implementazione in JavaScript:
const arr = [6, 2, 5, 3, 8, 7, 1, 4];
const quickSort = (arr, start, end) => {
if (start < end) {
// puoi imparare come viene selezionato il pivot nei commenti sotto
let pivot = partition(arr, start, end);
// assicurati di leggere i conmmenti sotto per capire perché pivot-1 e pivot+1 sono usati
// queste sono le invocazioni ricorsive a quickSort
quickSort(arr, start, pivot - 1);
quickSort(arr, pivot + 1, end);
}
}
const partition = (arr, start, end) => {
let pivot = end;
// imposta i a start-1 così che possa accedere al primo indice nel caso in cui il valore di arr[0] sia più grande di arr[pivot]
// i commenti successivi espandono sul commento qua sopra
let i = start - 1,
j = start;
// incrementa j fino all'indice precedente il pivot
while (j < pivot) {
// se il valore è più grande del pivot allora incrementa j
if (arr[j] > arr[pivot]) {
j++;
}
// quando il valore ad arr[j] è minore del pivot:
// incrementa i (arr[i] sarà un valore più grande di arr[pivot]) scambia i calori arr[i] e arr[j]
else {
i++;
swap(arr, j, i);
j++;
}
}
// il valore ad arr[i+1] sarà più grande del valore ad arr[pivot]
swap(arr, i + 1, pivot);
/* restituisci i+1, visto che i valori alla sua sinistra sono inferiori ad arr[i+1]
e i valore alla sua destra sono maggiorni di arr[i+1] */
/* In questo modo, quando i quickSort ricorsivi sono chiamati,
il nuovo sotto-array non include il valore pivot usato in precedenza */
return i + 1;
}
const swap = (arr, firstIndex, secondIndex) => {
let temp = arr[firstIndex];
arr[firstIndex] = arr[secondIndex];
arr[secondIndex] = temp;
}
quickSort(arr, 0, arr.length - 1);
console.log(arr);
Implementazione in C
#include<stdio.h>
void swap(int * a, int * b) {
int t = * a;
* a = * b;
* b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap( & arr[i], & arr[j]);
}
}
swap( & arr[i + 1], & arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}
int main() {
int arr[] = {
10,
7,
8,
9,
1,
5
};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: n");
printArray(arr, n);
return 0;
}Implementazione in Python3
import random
z = [random.randint(0, 100) for i in range(0, 20)]
def quicksort(z):
if len(z) > 1:
piv = int(len(z) / 2)
val = z[piv]
lft = [i for i in z if i < val]
mid = [i for i in z if i == val]
rgt = [i for i in z if i > val]
res = quicksort(lft) + mid + quicksort(rgt)
return res
else:
return z
ans1 = quicksort(z)
print ans1Implementazione in MATLAB
a = [9,4,7,3,8,5,1,6,2];
sorted = quicksort(a,1,length(a));
function [unsorted] = quicksort(unsorted, low, high)
if low < high
[pInd, unsorted] = partition(unsorted, low, high);
unsorted = quicksort(unsorted, low, pInd-1);
unsorted = quicksort(unsorted, pInd+1, high);
end
end
function [pInd, unsorted] = partition(unsorted, low, high)
i = low-1;
for j = low:1:high-1
if unsorted(j) <= unsorted(high)
i = i+1;
unsorted([i,j]) = unsorted([j,i]);
end
end
unsorted([i+1,high]) = unsorted([high,i+1]);
pInd = i+1;
end
Complessità
Le complessità nel caso migliore, medio, peggiore e di memoria sono rispettivamente: n log(n), n log(n), n^2, log(n). Non è un algoritmo stabile ed è di solito eseguito in loco con O(log(n)) spazio di stack.
La complessità spaziale di quick sort è O(n). Rappresenta un miglioramento rispetto ad altri algoritmi di ordinamento divide et impera, che prendono uno spazio di O(nlog(n)).
Per quick sort, ciò avviene cambiando l'ordine degli elementi all'interno dell'array dato. Fai il confronto con merge sort, che crea 2 array, ognuno di lunghezza n/2 in ogni chiamata di funzione.
Tuttavia, se il pivot viene mantenuto nel mezzo, questi algoritmi di ordinamento vengono eseguiti in O(n*n). Si può evitare questo problema usando un pivot random.
Timsort
Timsort è un algoritmo di ordinamento veloce che opera in modo stabile con complessità O(N log(N)).
Timsort è un mix di insertion sort e merge sort. Questo algoritmo è implementato in Arrays.sort() di Java, ma anche sorted() e sort() in Python. Le parti più piccole vengono ordinate usando insertion sort e poi unite insieme con merge sort.
Implementazione in Python:
def binary_search(
the_array,
item,
start,
end,
):
if start == end:
if the_array[start] > item:
return start
else:
return start + 1
if start > end:
return start
mid = round((start + end) / 2)
if the_array[mid] < item:
return binary_search(the_array, item, mid + 1, end)
elif the_array[mid] > item:
return binary_search(the_array, item, start, mid - 1)
else:
return mid
def insertion_sort(the_array):
l = len(the_array)
for index in range(1, l):
value = the_array[index]
pos = binary_search(the_array, value, 0, index - 1)
the_array = the_array[:pos] + [value] + the_array[pos:index] \
+ the_array[index + 1:]
return the_array
def merge(left, right):
"""Prende due liste ordinare
e restituisce una singola lista ordinata
comparando gli elementi uno alla volta.
[1, 2, 3, 4, 5, 6]
"""
if not left:
return right
if not right:
return left
if left[0] < right[0]:
return [left[0]] + merge(left[1:], right)
return [right[0]] + merge(left, right[1:])
def timsort(the_array):
(runs, sorted_runs) = ([], [])
length = len(the_array)
new_run = [the_array[0]]
# per ogni i nel range da 1 alla lunghezza dell'array
for i in range(1, length):
# se i è alla fine della lista
if i == length - 1:
new_run.append(the_array[i])
runs.append(new_run)
break
# se l'i-esimo elemento dell'aray è inferiore a quello prima
if the_array[i] < the_array[i - 1]:
# se new_run ha valore di None (NULL)
if not new_run:
runs.append([the_array[i]])
new_run.append(the_array[i])
else:
runs.append(new_run)
new_run = []
else:
# altrimenti se è uguare a maggiore di
new_run.append(the_array[i])
# per ogni item in runs, appendilo usando insertion sort
for item in runs:
sorted_runs.append(insertion_sort(item))
# per ogni run in sorted_runs, uniscile
sorted_array = []
for run in sorted_runs:
sorted_array = merge(sorted_array, run)
print sorted_array
timsort([
2,
3,
1,
5,
6,
7,
])
Complessità:
Timsort ha una complessità stabile di O(N log(N)) ed è ben comparabile con quick sort. Puoi vedere un confronto tra le complessità in questa tabella.
Merge Sort
Merge sort è un algoritmo divide et impera. Divide l'array di input in due metà, chiama sé stesso per le due metà e unisce le due porzioni ordinate. La porzione maggiore dell'algoritmo riceve due array ordinati, da unire in un singolo array ordinato. L'intero procedimento di ordinamento di un array di N interi può essere riassunto in 3 step:
- Divisione dell'array in due metà.
- Ordinamento della metà di sinistra e della metà di destra usando ricorsivamente lo stesso algoritmo.
- Unione delle due metà ordinate.
Esiste un algoritmo detto Two Finger che ci aiuta a unire assieme due array ordinati. Usando questo sottoprogramma e chiamando la funzione merge sort sulle metà dell'array ricorsivamente, otterremo l'array finale ordinato che stiamo cercando.
Dato che questo è un algoritmo basato sulla ricorsione, presenta una relazione di ricorrenza. La relazione di ricorrenza è semplicemente un modo di rappresentare un problema in termini dei suoi sottoproblemi.
T(n) = 2 * T(n / 2) + O(n)
Traducendo in italiano: dividiamo il sottoproblema in due parti ad ogni step, e abbiamo una quantità lineare di operazioni da svolgere per unire le due metà ordinate in ogni step.
Complessità
Il vantaggio più grande dell'uso di merge sort è che la complessità temporale per l'ordinamento di un intero array è solamente n*log(n), molto meglio di n^2 per bubble sort o insertion sort.
Prima di scrivere il codice, vediamo di capire come funziona merge sort con l'aiuto di un diagramma.
- Inizialmente abbiamo un array di 6 interi non ordinati:
Arr(5, 8, 3, 9, 1, 2) - Dividiamo l'array in due metà
Arr1 = (5, 8, 3)eArr2 = (9, 1, 2) - Di nuovo, li dividiamo in due metà:
Arr3 = (5, 8)eArr4 = (3)eArr5 = (9, 1)eArr6 = (2) - Di nuovo, li dividiamo in due metà:
Arr7 = (5),Arr8 = (8),Arr9 = (9),Arr10 = (1)andArr6 = (2) - Confrontiamo gli elementi nei sotto-array per poi unirli.
Proprietà:
- Complessità spaziale:
O(n) - Complessità temporale:
O(n*log(n)). La complessità temporale per merge sort potrebbe non essere ovvia di primo acchito. Il fattorelog(n)deriva dalla relazione di ricorrenza che abbiamo menzionato precedentemente. - Ordinamento in loco: no, in una implementazione usuale.
- Stabile: sì.
- Parallelizzabile: sì (svariate varianti parallele sono discusse nella terza edizione di Introduction to Algorithms di Cormen, Leiserson, Rivest e Stein).
Implementazione in C++
void merge(int array[], int left, int mid, int right) {
int i, j, k;
// dimensione della sotto-lista sinistra
int size_left = mid - left + 1;
// dimensione della sotto-lista denstra
int size_right = right - mid;
// crea gli array temporanei
int Left[size_left], Right[size_right];
// copia i dati agli array temporanei destro e sinistro
for (i = 0; i < size_left; i++) {
Left[i] = array[left + i];
}
for (j = 0; j < size_right; j++) {
Right[j] = array[mid + 1 + j];
}
// unisci gli array temporanei in arr[left ..right]
i = 0; // Indice iniziale del sotto-array sinistro
j = 0; // Indice iniziare del sotto-array destro
k = left; // Indice iniziare del sotto-array unito
while (i < size_left && j < size_right) {
if (Left[i] <= Right[j]) {
array[k] = Left[i];
i++;
} else {
array[k] = Right[j];
j++;
}
k++;
}
// copia gli elementi rimanenti del sotto-array sinistro
while (i < size_left) {
array[k] = Left[i];
i++;
k++;
}
// copia gli elementi rimanenti del sotto-array destro
while (j < size_right) {
array[k] = Right[j];
j++;
k++;
}
}
void mergeSort(int array[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
// infine uniscili
merge(array, left, mid, right);
}
}Implementazione in JavaScript
function mergeSort(arr) {
if (arr.length < 2) return arr;
var mid = Math.floor(arr.length / 2);
var subLeft = mergeSort(arr.slice(0, mid));
var subRight = mergeSort(arr.slice(mid));
return merge(subLeft, subRight);
}Prima verifichiamo la lunghezza dell'array. Se è 1, restituiamo semplicemente l'array. Questo è il caso base. Altrimenti, troviamo il valore centrale e dividiamo l'array in due metà. Ordiniamo entrambe le metà con chiamate ricorsive della funzione mergeSort.
function merge (a,b) {
var result = [];
while (a.length >0 && b.length >0)
result.push(a[0] < b[0]? a.shift() : b.shift());
return result.concat(a.length? a : b);
}Quando uniamo le due metà, memorizziamo il risultato in un array ausiliario. Confronteremo l'elemento iniziale dell'array di sinistra con l'elemento iniziale dell'array di destra. Qualsiasi sia il minore, verrà inserito nell'array con il risultato e rimosso da quello d'appartenenza con l'operatore shift(). Se alla fine ci sono ancora valori negli array di sinistra o destra, verranno concatenati alla fine del risultato. Ecco l'array ordinato:
var test = [5, 6, 7, 3, 1, 3, 15];
console.log(mergeSort(test));
>> [1, 3, 3, 5, 6, 7, 15]Implementazione in JS
const list = [23, 4, 42, 15, 16, 8, 3]
const mergeSort = (list) => {
if (list.length <= 1) return list;
const middle = list.length / 2;
const left = list.slice(0, middle);
const right = list.slice(middle, list.length);
return merge(mergeSort(left), mergeSort(right));
}
const merge = (left, right) => {
var result = [];
while (left.length || right.length) {
if (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
} else if (left.length) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result;
}
console.log(mergeSort(list)) // [ 3, 4, 8, 15, 16, 23, 42 ]Implementazione in C
#include<stdlib.h>
#include<stdio.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main() {
int arr[] = {
12,
11,
13,
5,
6,
7
};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;Implementazione in C++
Consideriamo l'array A = {2,5,7,8,9,12,13} e l'array B = {3,5,6,9,15}. Vogliamo che anche l'array C sia in ordine ascendente.
void mergesort(int A[], int size_a, int B[], int size_b, int C[]) {
int token_a, token_b, token_c;
for (token_a = 0, token_b = 0, token_c = 0; token_a < size_a && token_b < size_b;) {
if (A[token_a] <= B[token_b])
C[token_c++] = A[token_a++];
else
C[token_c++] = B[token_b++];
}
if (token_a < size_a) {
while (token_a < size_a)
C[token_c++] = A[token_a++];
} else {
while (token_b < size_b)
C[token_c++] = B[token_b++];
}
}Implementazione in Python
#!/usr/bin/python
# -*- coding: utf-8 -*-
def merge(left, right, compare):
result = []
(i, j) = (0, 0)
while i < len(left) and j < len(right):
if compare(left[i], right[j]):
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
while i < len(left):
result.append(left[i])
i += 1
while j < len(right):
result.append(right[j])
j += 1
return result
def merge_sort(arr, compare=lambda x, y: x < y):
# Usa funzione lambda per ordinare l'array in entrambi (crescente e decrescente) gli ordini
# Come default ordina l'array in ordine crescente
if len(arr) < 2:
return arr[:]
else:
middle = len(arr) // 2
left = merge_sort(arr[:middle], compare)
right = merge_sort(arr[middle:], compare)
return merge(left, right, compare)
arr = [2, 1, 4, 5, 3]
print merge_sort(arr)
Implementazione in Java
public class mergesort {
public static int[] mergesort(int[] arr, int lo, int hi) {
if (lo == hi) {
int[] ba = new int[1];
ba[0] = arr[lo];
return ba;
}
int mid = (lo + hi) / 2;
int arr1[] = mergesort(arr, lo, mid);
int arr2[] = mergesort(arr, mid + 1, hi);
return merge(arr1, arr2);
}
public static int[] merge(int[] arr1, int[] arr2) {
int i = 0, j = 0, k = 0;
int n = arr1.length;
int m = arr2.length;
int[] arr3 = new int[m + n];
while (i < n && j < m) {
if (arr1[i] < arr2[j]) {
arr3[k] = arr1[i];
i++;
} else {
arr3[k] = arr2[j];
j++;
}
k++;
}
while (i < n) {
arr3[k] = arr1[i];
i++;
k++;
}
while (j < m) {
arr3[k] = arr2[j];
j++;
k++;
}
return arr3;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {
2,
9,
8,
3,
6,
4,
10,
7
};
int[] so = mergesort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++)
System.out.print(so[i] + " ");
}
}Esempio in Java
public class mergesort {
public static int[] mergesort(int[] arr, int lo, int hi) {
if (lo == hi) {
int[] ba = new int[1];
ba[0] = arr[lo];
return ba;
}
int mid = (lo + hi) / 2;
int arr1[] = mergesort(arr, lo, mid);
int arr2[] = mergesort(arr, mid + 1, hi);
return merge(arr1, arr2);
}
public static int[] merge(int[] arr1, int[] arr2) {
int i = 0, j = 0, k = 0;
int n = arr1.length;
int m = arr2.length;
int[] arr3 = new int[m + n];
while (i < n && j < m) {
if (arr1[i] < arr2[j]) {
arr3[k] = arr1[i];
i++;
} else {
arr3[k] = arr2[j];
j++;
}
k++;
}
while (i < n) {
arr3[k] = arr1[i];
i++;
k++;
}
while (j < m) {
arr3[k] = arr2[j];
j++;
k++;
}
return arr3;
}
public static void main(String[] args) {
int arr[] = {
2,
9,
8,
3,
6,
4,
10,
7
};
int[] so = mergesort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++)
System.out.print(so[i] + " ");
}
}