(articolo redatto da Gaetano De Pascale)
Abbiamo provato a chiedere ad un’intelligenza artificiale di descrivere ed implementare i migliori 5 algoritmi di sorting. Ecco la sua risposta, con le implementazioni in c#, typescript e java.
Quicksort
È uno degli algoritmi di sorting più efficienti e utilizzati in molti ambienti di sviluppo. Funziona selezionando un elemento pivot e poi spostando gli elementi minori alla sua sinistra e quelli maggiori alla sua destra. Quindi, esegue ricorsivamente lo stesso processo su ciascuna delle sotto liste ottenute finché non sono ordinate.
Typescript
function quickSort(arr: number[]) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[arr.length - 1];
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const sortedArray = quickSort([4, 6, 2, 7, 1, 3, 5]);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7]c#
using System;
namespace SortingAlgorithms
{
public static class QuickSort
{
public static void Sort(int[] array)
{
Sort(array, 0, array.Length - 1);
}
private static void Sort(int[] array, int left, int right)
{
if (left >= right)
{
return;
}
int pivot = array[(left + right) / 2];
int index = Partition(array, left, right, pivot);
Sort(array, left, index - 1);
Sort(array, index, right);
}
private static int Partition(int[] array, int left, int right, int pivot)
{
while (left <= right)
{
while (array[left] < pivot)
{
left++;
}
while (array[right] > pivot)
{
right--;
}
if (left <= right)
{
Swap(array, left, right);
left++;
right--;
}
}
return left;
}
private static void Swap(int[] array, int left, int right)
{
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
}
Java
import java.util.Arrays;
public class QuickSort {
public static void sort(int[] array) {
sort(array, 0, array.length - 1);
}
private static void sort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int pivot = array[(left + right) / 2];
int index = partition(array, left, right, pivot);
sort(array, left, index - 1);
sort(array, index, right);
}
private static int partition(int[] array, int left, int right, int pivot) {
while (left <= right) {
while (array[left] < pivot) {
left++;
}
while (array[right] > pivot) {
right--;
}
if (left <= right) {
swap(array, left, right);
left++;
right--;
}
}
return left;
}
private static void swap(int[] array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
public static void main(String[] args) {
int[] array = {4, 6, 2, 7, 1, 3, 5};
sort(array);
System.out.println(Arrays.toString(array)); // [1, 2, 3, 4, 5, 6, 7]
}
}
Merge Sort
È un altro algoritmo di sorting efficiente che funziona dividendo la lista di elementi da ordinare in sotto liste di elementi già ordinati; quindi, fonde le sotto liste per ottenere la lista completamente ordinata.
Typescript
function mergeSort(arr: number[]) {
if (arr.length <= 1) {
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left: number[], right: number[]) {
const result = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return [...result, ...left, ...right];
}
const sortedArray = mergeSort([4, 6, 2, 7, 1, 3, 5]);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7]
c#
using System;
namespace SortingAlgorithms
{
public static class MergeSort
{
public static void Sort(int[] array)
{
int[] temp = new int[array.Length];
Sort(array, temp, 0, array.Length - 1);
}
private static void Sort(int[] array, int[] temp, int left, int right)
{
if (left >= right)
{
return;
}
int middle = (left + right) / 2;
Sort(array, temp, left, middle);
Sort(array, temp, middle + 1, right);
Merge(array, temp, left, right);
}
private static void Merge(int[] array, int[] temp, int left, int right)
{
int middle = (left + right) / 2;
int leftIndex = left;
int rightIndex = middle + 1;
int tempIndex = left;
while (leftIndex <= middle && rightIndex <= right)
{
if (array[leftIndex] < array[rightIndex])
{
temp[tempIndex++] = array[leftIndex++];
}
else
{
temp[tempIndex++] = array[rightIndex++];
}
}
while (leftIndex <= middle)
{
temp[tempIndex++] = array[leftIndex++];
}
while (rightIndex <= right)
{
temp[tempIndex++] = array[rightIndex++];
}
for (int i = left; i <= right; i++)
{
array[i] = temp[i];
}
}
}
}
Java
import java.util.Arrays;
public class MergeSort {
public static void sort(int[] array) {
int[] temp = new int[array.length];
sort(array, temp, 0, array.length - 1);
}
private static void sort(int[] array, int[] temp, int left, int right) {
if (left >= right) {
return;
}
int middle = (left + right) / 2;
sort(array, temp, left, middle);
sort(array, temp, middle + 1, right);
merge(array, temp, left, right);
}
private static void merge(int[] array, int[] temp, int left, int right) {
int middle = (left + right) / 2;
int leftIndex = left;
int rightIndex = middle + 1;
int tempIndex = left;
while (leftIndex <= middle && rightIndex <= right) {
if (array[leftIndex] < array[rightIndex]) {
temp[tempIndex++] = array[leftIndex++];
} else {
temp[tempIndex++] = array[rightIndex++];
}
}
while (leftIndex <= middle) {
temp[tempIndex++] = array[leftIndex++];
}
while (rightIndex <= right) {
temp[tempIndex++] = array[rightIndex++];
}
for (int i = left; i <= right; i++) {
array[i] = temp[i];
}
}
public static void main(String[] args) {
int[] array = {4, 6, 2, 7, 1, 3, 5};
sort(array);
System.out.println(Arrays.toString(array)); // [1, 2, 3, 4, 5, 6, 7]
}
}
Heapsort
È un algoritmo di sorting basato sull’utilizzo di una struttura dati nota come heap. Funziona creando un heap con gli elementi della lista da ordinare; quindi, estrae il massimo (o il minimo, a seconda della configurazione dell’algoritmo) elemento dall’heap e lo sposta alla fine della lista ordinata. Questo processo viene ripetuto finché non sono stati estratti tutti gli elementi dall’heap.
Typescript
function heapSort(arr: number[]) {
const heap = new MaxHeap(arr);
const sortedArray = [];
while (heap.size() > 0) {
sortedArray.push(heap.extractMax());
}
return sortedArray;
}
class MaxHeap {
private heap: number[];
constructor(array: number[]) {
this.heap = this.buildHeap(array);
}
public extractMax(): number {
const max = this.heap[0];
this.heap[0] = this.heap[this.heap.length - 1];
this.heap.pop();
this.siftDown(0);
return max;
}
public size(): number {
return this.heap.length;
}
private buildHeap(array: number[]): number[] {
for (let i = Math.floor(array.length / 2); i >= 0; i--) {
this.siftDown(i);
}
return array;
}
private siftDown(currentIndex: number): void {
const maxIndex = this.getMaxChildIndex(currentIndex);
if (maxIndex === null) {
return;
}
if (this.heap[currentIndex] < this.heap[maxIndex]) {
this.swap(currentIndex, maxIndex);
this.siftDown(maxIndex);
}
}
private getMaxChildIndex(currentIndex: number): number | null {
const leftChildIndex = 2 * currentIndex + 1;
const rightChildIndex = 2 * currentIndex + 2;
if (leftChildIndex >= this.heap.length) {
return null;
}
if (rightChildIndex >= this.heap.length) {
return leftChildIndex;
}
return this.heap[leftChildIndex] > this.heap[rightChildIndex] ? leftChildIndex : rightChildIndex;
}
private swap(i: number, j: number): void {
const temp = this.heap[i];
this.heap[i] = this.heap[j];
this.heap[j] = temp;
}
const sortedArray = heapSort([4, 6, 2, 7, 1, 3, 5]);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7]
c#
using System;
namespace SortingAlgorithms
{
public static class HeapSort
{
public static void Sort(int[] array)
{
int n = array.Length;
for (int i = n / 2 - 1; i >= 0; i--)
{
Heapify(array, n, i);
}
for (int i = n - 1; i >= 0; i--)
{
Swap(array, 0, i);
Heapify(array, i, 0);
}
}
private static void Heapify(int[] array, int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && array[left] > array[largest])
{
largest = left;
}
if (right < n && array[right] > array[largest])
{
largest = right;
}
if (largest != i)
{
Swap(array, i, largest);
Heapify(array, n, largest);
}
}
private static void Swap(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
Java
import java.util.Arrays;
public class HeapSort {
public static void sort(int[] array) {
int n = array.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
for (int i = n - 1; i >= 0; i--) {
swap(array, 0, i);
heapify(array, i, 0);
}
}
private static void heapify(int[] array, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && array[left] > array[largest]) {
largest = left;
}
if (right < n && array[right] > array[largest]) {
largest = right;
}
if (largest != i) {
swap(array, i, largest);
heapify(array, n, largest);
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int[] array = {4, 6, 2, 7, 1, 3, 5};
sort(array);
System.out.println(Arrays.toString(array)); // [1, 2, 3, 4, 5, 6, 7]
}
}
Insertion Sort
È un algoritmo di sorting semplice ma efficace che funziona inserendo gli elementi della lista uno per uno in una nuova lista ordinata. Ad ogni passo, l’elemento viene inserito nella posizione corretta nella lista ordinata in modo che la lista rimanga ordinata.
Typescript
function insertionSort(arr: number[]) {
const sortedArray = [arr[0]];
for (let i = 1; i < arr.length; i++) {
let j = sortedArray.length - 1;
while (j >= 0 && sortedArray[j] > arr[i]) {
j--;
}
sortedArray.splice(j + 1, 0, arr[i]);
}
return sortedArray;
}
const sortedArray = insertionSort([4, 6, 2, 7, 1, 3, 5]);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7]
c#
using System;
namespace SortingAlgorithms
{
public static class InsertionSort
{
public static void Sort(int[] array)
{
for (int i = 1; i < array.Length; i++)
{
int current = array[i];
int j = i - 1;
while (j >= 0 && array[j] > current)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = current;
}
}
}
}
Java
import java.util.Arrays;
public class InsertionSort {
public static void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
int current = array[i];
int j = i - 1;
while (j >= 0 && array[j] > current) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = current;
}
}
public static void main(String[] args) {
int[] array = {4, 6, 2, 7, 1, 3, 5};
sort(array);
System.out.println(Arrays.toString(array)); // [1, 2, 3, 4, 5, 6, 7]
}
}
Selection Sort
È un altro algoritmo di sorting semplice che funziona selezionando il minimo (o il massimo) elemento della lista non ordinata e spostandolo all’inizio (o alla fine) della lista ordinata. Questo processo viene ripetuto finché non sono stati ordinati tutti gli elementi della lista.
Typescript
function selectionSort(arr: number[]) {
const sortedArray = [];
while (arr.length > 0) {
let minIndex = 0;
for (let i = 1; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
sortedArray.push(arr[minIndex]);
arr.splice(minIndex, 1);
}
return sortedArray;
}
const sortedArray = selectionSort([4, 6, 2, 7, 1, 3, 5]);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7]
c#
using System;
namespace SortingAlgorithms
{
public static class SelectionSort
{
public static void Sort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < array.Length; j++)
{
if (array[j] < array[minIndex])
{
minIndex = j;
}
}
Swap(array, i, minIndex);
}
}
private static void Swap(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j]; array[j] = temp;
}
}
}
Java
import java.util.Arrays;
public class SelectionSort {
public static void sort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array, i, minIndex);
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int[] array = {4, 6, 2, 7, 1, 3, 5};
sort(array);
System.out.println(Arrays.toString(array)); // [1, 2, 3, 4, 5, 6, 7]
}
}
Conclusioni
Che ne dici? Come se l’è cavata l’intelligenza artificiale rispetto al compito che le avevamo richiesto?
Se anche tu vuoi occuparti di progetti di ricerca e sviluppo IT di ultima generazione
dai un’occhiata alle nostre opportunità di lavoro e conosciamoci subito!
