PROBLEMA Eliminare posizioni da un array

[merecol]

Ciao ragazzi.Mi sono cimentato nella creazione di una funzione che ordina gli elementi di un array.La mia idea è stata questa: prendo gli elementi dell'array di partenza,li copio in un altro array di appoggio inserendoli nella posizione relativa al loro valore (es. Il numero 5 verrà inserito nella posizione 5 dell'array),elimino le posizioni nell'array di appoggio in cui valori risultano undefined ed infine rendo l'array iniziale uguale a quello di appoggio.In questo modo risulterà l'array ordinato.Io per eliminare gli elementi undefined avevo pensato di utilizzare un ciclo di for che ripassa tutto l'array ed elimina li elimina ma penso sia molto dispendiosa come cosa.Esiste un modo per ottenere lo stesso risultato in maniera diversa?

 

[1nd33d]

Quello che adotti tu si chiama bucket sort, è un algoritmo semplice ma con diverse limitazioni:
- non gestisce valori ripetuti se non aggiungendo altri meccanismi (un po' come avviene per le collisioni nelle hashmap)
- devi creare un array lungo tanto quanto il valore dell'elemento più grande
- conseguenza del punto precedente, la potenziale grande quantità di celle vuote.
Ora non so se la tua intenzione sia quella di provare a scrivere un tuo algoritmo di sorting, ma quasi tutti i linguaggi di alto livello dispongono già di funzioni di sorting.
Se invece vuoi fare la tua versione del bucket sort, il modo in cui lo fai dipende anche dal linguaggio.
Che linguaggio stai usando e che struttura dati adotti?

 

[merecol]

Ciao,grazie per la risposta:)Lo sto implementando in javascript.Non sapevo dell'esistenza del bucket sort,gli ho dato un'occhiata e ho visto che l'array di appoggio è grande tanto quanto l'array originario.Invece con il mio metodo se il numero più alto è 500,l'array di appoggio avrà length 501...Sono io che ho sbagliato ad interpretare il bucket sort oppure la mia idea fa schifo?:)

 

[1nd33d]

Di bucketsort ne esistono diverse varianti, l'idea è che in tempo costante O(1) prendi un elemento a caso dell'array originario e lo metti in un "bucket". Alla fine leggi i bucket nell'ordine in cui sono stati definiti (eventualmente ordinando gli elementi in ogni bucket se ne contiene più di uno).
Il bucket sort come l'hai pensato te è la variante semplice nella quale ogni bucket contiene un solo valore, potenzialmente anche la più veloce, ma praticabile solo se lavori con valori non troppo grandi. Inoltre se hai valori ripetuti va modificata (potresti per esempio non copiare i valori ma semplicemente usare un array di "contatori" che incrementi ogni volta che trovi un certo valore).
Per eliminare le celle vuote nell'algoritmo che hai scritto te, potresti semplicemente percorrere da sinistra verso destra l'array ordinato e copiare solo i valori non nulli in un altro array, che conterrà i valori definitivi.

 

[merecol]

Sì infatti la mia idea era quella di scorrere l'array da sinistra a destra e copiare le posizioni non uguali a null nell'array originario.Un meccanismo per le ripetizioni già l'avevo pensato e penso funzioni bene.Una cosa però non ho capito:i bucket come vengono creati nell'algoritmo?Sono praticamente porzioni dello stesso array oppure no?Anche nell'algoritmo "originale" ci sono posti vuoti nell'array?

 

[1nd33d]

Bucket vuoti ce ne possono essere in tutte le varianti, anche se esistono metodi che ti permettono di saltarli senza controllare se sono null nella fase finale.
I bucket, per come li fai te, possono essere semplicemente posizioni in un array. Uno pseudocodice di massima:

 [B]function [/B] ordina(disordinati)
   max = min = disordinati[0]
    [B]foreach [/B] v [B]in [/B]disordinati  [B]do   [/B]//trova massimo e minimo
      [B]if [/B]v > max [B]then [/B]max = v
      [B]if [/B]v < min [B]then [/B]min = v
   bucket = [B]new [/B]array(max-min) //inizializzato a zero
   [B]foreach [/B]v [B]in [/B]disordinati [B]do  [/B]//segna le occorrenze dei valori
      bucket[v-min]++
   ordinati = [B]new [/B]array()
   [B]for [/B]i = 0 [B]to [/B]bucket.length [B]do[/B] //visita ogni bucket
      [B]for [/B]j = 1 [B]to [/B]bucket[i] [B]do[/B] //se il contatore del bucket è >0 inserisci valore in output
         ordinati.push(i + min)
   [B]return [/B]ordinati

ovviamente tutto non testato, ma l'idea dovrebbe essere giusta.
edit: testato in python, l'algoritmo è giusto, ma c'è un errorino, manca un "+1" da qualche parte, a te scoprirlo se vuoi :asd:

 

[merecol]

Io i bucket non li avevo proprio considerati:)Avevo semplicemente pensato a mettere i numeri nelle posizioni corrispondenti al loro valore e poi eliminare le posizioni null:)Quello che non capisco è come vengono creati i bucket e la loro utilità:)

 

[1nd33d]

I bucket sono solo dei contenitori dove inserisci l'elemento, nel tuo algoritmo sono le celle dell'array... il tuo algoritmo, se ho ben capito, fa questo:
array disordinato: [ 5, 2, 3, 8, 1]
array bucket: [null, 1, 2, 3, null, 5, null, null, 8]
array ordinato: [1, 2, 3, 5, 8]

Forse non avevi pensato ai bucket, ma di fatto li hai usati, senza saperlo. Volendo fare i pignoli, l'algoritmo bucket sort con bucket unitari come il tuo corrisponde a un counting sort, ma non funziona come lo immagini tu (lo pseudocodice che ti ho scritto sopra dovrebbe essere un counting sort). Infatti prova a pensare come si comporterebbe il tuo algoritmo con valori ripetuti, e se avessi anche valori negativi?

Prova a ordinare questo: [2, 3, 2, 1, 8]
otterresti: [1, 2, 3, 8] ma ti sei perso un "2"

o questo: [2, 8, -1, 2, 4]
andresti in errore perchè cercheresti di inserire "-1" nella posizione -1 dell'array (ma gli array hanno posizioni solo da 0 in su, in alcuni linguaggi da 1 in su)

 

[merecol]

L'algoritmo è pronto,funziona per bene anche con i numeri negativi e per i "doppioni".L'unica cosa è che per creare alla fine l'array ordinato e per eliminare i null devo ripassare totalmente l'array di appoggio.Non c'è un modo per eliminare i null dell'array di appoggio senza ripassarlo tutto?

 

[1nd33d]

L'algoritmo è pronto,funziona per bene anche con i numeri negativi e per i "doppioni".L'unica cosa è che per creare alla fine l'array ordinato e per eliminare i null devo ripassare totalmente l'array di appoggio.Non c'è un modo per eliminare i null dell'array di appoggio senza ripassarlo tutto?

Nella teoria forse anche si, ma nella pratica probabilmente non porterebbe grandi vantaggi (anzi forse è peggiorativo) e complicheresti il codice per nulla.
Se funziona bene lascialo così.

 

[merecol]

L'unica pecca di questo algoritmo è che non gestisce i numeri decimali,col metodo delle posizioni credo sia impossibile gestirli,si dovrebbe usare un metodo di confronto...sei d'accordo?

 

[1nd33d]

Beh si, il counting sort non funziona con valori decimali, a meno che non siano con un numero di cifre decimali fissato (in quel caso puoi mapparli a numeri interi)
Se devi trattare numeri decimali ti conviene usare un algoritmo di sorting più generico, tipo merge sort o quick sort (questi sono i più "famosi", ma ce ne sono molti altri).

 

[merecol]

In che senso puoi mapparli a numeri interi?

 

[1nd33d]

Per esempio se li tronchi tutti alla terza cifra decimale ti basta moltiplicarli per 1000. Ma ti conviene usare un algoritmo di quelli che ho detto nel post precedente.
Non ho ancora capito se tu voglia per forza implementarti da te l'algoritmo di ordinamento, ma gli array in Javascript dispongono già di un metodo che li ordina.

 

[merecol]

È un esperimento,un'esercitazione se vogliamo metterla cosi:):)A questo metodo avevo già pensato però poi il problema è inserire quei numeri in maniera ordinata tra i numeri interi.Ad esempio se ho 1,10 e 1,20 capisco che 1,10 è più piccolo ma poi come li inserisco questi numeri nell'array ordinato tra 1 e 2?