PROBLEMA Eliminare posizioni da un array

merecol

Utente Attivo
154
1
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

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
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

Utente Attivo
154
1
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?:)
 
Ultima modifica:

1nd33d

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
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.
 
Ultima modifica:

merecol

Utente Attivo
154
1
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

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
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:
Codice:
 [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:
 
Ultima modifica:

merecol

Utente Attivo
154
1
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

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
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)
 
Ultima modifica:

merecol

Utente Attivo
154
1
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

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
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ì.
 
Ultima modifica:

merecol

Utente Attivo
154
1
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

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
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).
 

1nd33d

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
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.
 
Ultima modifica:

merecol

Utente Attivo
154
1
È 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?
 

Entra

oppure Accedi utilizzando

Hot: E3 2021, chi ti è piaciuto di più?

  • Ubisoft

    Voti: 37 23.1%
  • Gearbox

    Voti: 3 1.9%
  • Xbox & Bethesda

    Voti: 101 63.1%
  • Square Enix

    Voti: 14 8.8%
  • Capcom

    Voti: 7 4.4%
  • Nintendo

    Voti: 21 13.1%
  • Altro (Specificare)

    Voti: 15 9.4%

Discussioni Simili