[JAVA] Ordinamento veloce di array senza ricorsione

[Bobo90]

Salve ragazzi.. volevo porvi un semplice quesito per voi.. sono alle prime armi con java e mi si è posto un problema davanti di questa natura.. dato un array di interi in entrata di grandezza qualunque ma formato da interi il cui valore è compreso necessariamente tra 0 e 100 devo ordinare tale array con una certa performance.. L'array può contenere quanti elementi voglio e inoltre un elemento può essere ripetuto quante volte si vuole. Devo implementare tale metodo senza ricorsione.. ovvero marge sort inutilizzabile e il problema è che deve essere performante! Ho provato con il bubble, insertion e selection sort ma tutti e 3 ci mettono troppo tempo.. nella guida mi viene consigliato di usare un vettore di appoggio.. ci ho provato ma inutilmente perchè ci mette sempre troppo tempo.. sapreste aiutarmi per caso? Ricordatevi che sono alle prime armi quindi ahimè non fate uscire paroloni che per me sarebbero incomprensibili xD Grazie mille!!

[VincenzoTheBest]

Originariamente inviato da Bobo90
Devo implementare tale metodo senza ricorsione..

Dov'è il problema che riguarda Java?

E' un problema generale di algoritmi...

[Bobo90]

Ah.... ho sbagliato quindi sezione? devo farlo su java per questo l'ho messo in questa sezione.. riguarda gli algoritmi si però specificando JAVA pensavo poteste essere più precisi su come risolverlo senza ricorrere a metodi troppo difficili..

[VincenzoTheBest]

Originariamente inviato da Bobo90
riguarda gli algoritmi si però specificando JAVA pensavo poteste essere più precisi su come risolverlo senza ricorrere a metodi troppo difficili..

Ok allora proviamo a farne uno ex novo no?

La soluzione che proponi riguardo l'uso di un appoggio può andare bene.
Magari a te risulta poco performante se utilizzi solo un array statico al di là della tecnica che hai usato.

Potresti caricare i dati in input in una LinkedList oppure in una
ArrayList
in modo da diminuire progressivamente l'insieme di numeri dal quale scegliere l'i-esimo numero da inserire nella struttura di appoggio.

In modo approssimativo posso dirti che la LinkedList è più performante per quanto riguarda le operazioni di inserimento e rimozione, mentre la ArrayList è più performante per quanto riguarda le operazioni di accesso. Dunque a te la scelta.

[Bobo90]

..L'ho risolto in un modo cosi banale che se ci ripenso mi mangio le mani per quanto tempo ci ho sbattuto la testa..... scorro il vettore in entrata e grazie al vettore di supporto metto un 1 nella posizione di ogni cifra che scorro del vettore.. mi spiego con un esempio:
vettore in entrata= 3,54,76,32,23
vettore di supporto avrà un 1 nella posizione 3.. un 1 nella posizione 54 e cosi via... nel caso ci siano doppioni allora l'1 diventerà 2 se ci sono due doppioni, 3 se ci sono 3 doppioni e via.. e poi riscorro il vettore di supporto e a seconda degli 1, o 2 o 3 o cosi via, che trovo posizionerò la cifrà della posizione dove ho trovato gli uno e incremento -.-

[andbin]

Originariamente inviato da Bobo90
vettore in entrata= 3,54,76,32,23
vettore di supporto avrà un 1 nella posizione 3.. un 1 nella posizione 54 e cosi via... nel caso ci siano doppioni allora l'1 diventerà 2 se ci sono due doppioni, 3 se ci sono 3 doppioni e via.. e poi riscorro il vettore di supporto e a seconda degli 1, o 2 o 3 o cosi via, che trovo posizionerò la cifrà della posizione dove ho trovato gli uno e incremento -.-

E questo cosa centra con un vero e proprio "ordinamento" dei valori??? .... niente.

[VincenzoTheBest]

Originariamente inviato da andbin
E questo cosa centra con un vero e proprio "ordinamento" dei valori??? .... niente.

Infatti...

[Bobo90]

Mi spiegate cosa volete dire scusate? Quello che fa quel metodo è un vero e proprio ordinamento dei valori di un vettore.... a meno che per "ordinamento" voi non intendiate altro però a casa ordinamento significa quello....2,65,76,45 ----> 2,45,65,76

[VincenzoTheBest]

Originariamente inviato da Bobo90
Mi spiegate cosa volete dire scusate? Quello che fa quel metodo è un vero e proprio ordinamento dei valori di un vettore.... a meno che per "ordinamento" voi non intendiate altro però a casa ordinamento significa quello....2,65,76,45 ----> 2,45,65,76

Forse ti sarai espresso male..perchè quello che hai scritto nel precedente post non dice nulla.

[Bobo90]

Mmmmm mi sa che non ci capiamo.. cosa volevate dire voi con la frase "E questo cosa centra con un vero e proprio "ordinamento" dei valori??? .... niente."??
Il metodo che io ho proposto risolve a pieno il problema che ho posto! Un esempio di un vettore stupido e breve.. v= 16,4,3
Con il metodo che io ho proposto mi creo un vettore di supporto. Posiziono in questo vettore nella posizione 16 il numero 1.. nella posizione 4 il numeri 1 e nella posizione 3 il numero 1... se il vettore fosse stato v=16,16,3 allora nel vettore di supporto alla posizione 16 ci sarebbe stato un 2 perchè i doppioni sono 2! Poi scorro il vettore di supporto.. nella posizione i-esima trovo un numero diverso da 0? allora nel vettore d'origine alla posizione 0 metterò l'indice "i" e incremento!
Questo è un vero e proprio ordinamento! Non capisco la vostra affermazione.. se non è ordinamento questo cosa intendete per "ordinamento" voi?