Insert sort java

di
Luca
il
7 risposte
L
Luca
Pochi posts
Iscritto da
gen, 2009
Messaggi:
4

Insert sort java

Salve a tutti,
dovrei implementare l'algoritmo di insert sort in java mediante una classe che ne gestisca il funzionamento. 

public class myClass
{
   ArrayList<Object> x;

   public myClass()
  {
         x= new ArrayList<Object>();
  }
  public void insertSort(Object o)
  {
    //inserire in x in modo ordinato l'oggetto o, x.add( ... )
  }

}

Il richiamo di questo metodo sarà del tipo
 myClass  z = new myClass();

z.insertSort(12);
z.insertSort(9);
z.insertSort(50);
z.insertSort(120)
z.insertSort(0);
z.insertSort(1);

stampando l'array x ( ad esempio con z.toString() ) -> [  0 , 1 , 9, 12 , 50, 120  ]
Nell'array x gli oggetti o devono essere ordinati secondo un loro particolare attributo ( es. o.y dove y double, int... )
Nei vari algoritmi che ho trovato , viene implementato il metodo insertion sort che ordina gli elementi contenuti in una lista solo dopo averla riempita. Ovviamente sarebbe meno costoso inserirli già direttamente ordinati...

Ringrazio chiunque avesse idee in merito all'implementazione di tale algoritmo!
Grazie, a presto!

7 Risposte

  • O
    Overflow
    Utente Attivo
    Iscritto da
    gen, 2008
    Messaggi:
    222

    Re: Insert sort java

    Luca ha scritto:

    ...Ovviamente sarebbe meno costoso inserirli già direttamente ordinati...
    guarda non cambia niente.
    Devi iterare sempre sulla lista e vedere il valore di quell'elemento è maggiore o minore di quello da inserire.
    Alla fine non cambia niente.
  • L
    Luca
    Pochi posts
    Iscritto da
    gen, 2009
    Messaggi:
    4

    Re: Insert sort java

    Ciao,
    si hai ragione, però io l'inserimento non lo faccio solo in un punto ma in più punti diversi all'interno del programma e mi serve averli ordinati già nel momento dell'inserimento... Il mio compito è quello di realizzare una sorta di fel, future event list, una lista che contenga eventi per la gestione di un simulatore discreto. Dovrei inserire gli eventi in fel , in modo da averli sempre in ordine di "arrivo" in modo da poterli schedulare secondo una particolare politica... rifare l'ordinamento ogni volta che arriva un nuovo evento non è , a mio avviso, la maniera più corretta per gestire il tutto, anche se il risultato non cambia...
  • O
    Overflow
    Utente Attivo
    Iscritto da
    gen, 2008
    Messaggi:
    222

    Re: Insert sort java

    Il metodo add aggiunge l'elemento alla fine della lista.
    x.add(oggetto1);
    x.add(oggetto2);
    x.add(oggetto3);

    nella lista avrai
    1. oggetto1
    2. oggetto2
    3. oggetto3

    quindi non serve ordinare la lista.
  • L
    Luca
    Pochi posts
    Iscritto da
    gen, 2009
    Messaggi:
    4

    Re: Insert sort java

    Bisogna ordinare gli oggetti in base ad un loro attributo. Un esempio potrebbe essere l'età anagrafica...
    Persona p1 = new Persona("Andrea" , 30 ) ;
    Persona p2 = new Persona("Luca" , 12 ) ;
    Persona p3 = new Persona("Marco" , 80 ) ;

    x.add(p1);
    x.add(p2);
    x.add(p3);

    x.toString() -> Andrea, Luca, Marco

    Le persone sono ordinate secondo l'ordine con il quale sono state inserite.., ma non in base all'età.. dovrebbe essere [ Luca, Andrea, Marco ] .. il mio ordinamento, in questo caso, è su un int, ma nel caso che interessa, è su un double, ma è il meno. L'insert Sort dovrebbe inserire le persone già in modo ordinato e non ordinarle in un secondo momento. Non so se sono riuscito a spiegarmi meglio...
  • J
    joksy
    Pochi posts
    Iscritto da
    gen, 2009
    Messaggi:
    18

    Re: Insert sort java

    Ciao Luca Ho visto oggi il tuo messo mi sono appena iscritto al forum. spero tu abbia gia risolto il problema se cosi non fosse ho pensato una cosa che magari ti sara utile (spero )

    ecco il code
    
public class MySortedList<T extends Comparable<T>> {

	private ArrayList<T> list;
	
	public MySortedList() {
		list = new ArrayList<T>();
	}
	
	public void add(T el){		
			list.add(el);
	}
	
	public void sorted(){
			//ascending order insert
			// qui implementi il sort...
			// usando il compareTo
			// che ti definisce se un tuo type e minore maggiore o =
			// in questo modo puoi comparare qualsiasi cosa
			// basta che definisci come vuoi tu :)
		for (int i = 1; i < list.size(); i++) {
			int j = i;
			T B = list.get(i);
			while ((j > 0) && (list.get(j-1).compareTo(B) == 1)) {
			list.set(j, list.get(j-1));
			j--;
			}
			list.set(j, B);
			}
		
	}
	
	public ArrayList<T> getList(){
		return list;
	}
	
	public static void main(String[] args) {
		MySortedList<Person> compare  = new MySortedList<Person>();
		Person p1 = new Person("Andrea" , 30 ) ;
		Person p2 = new Person("Luca" , 12 ) ;
		Person p3 = new Person("Marco" , 80 ) ;
		compare.add(p1);
		compare.add(p2);
		compare.add(p3);
		compare.sorted();
		ArrayList<Person> d = compare.getList();
		
		for (Person person : d) {
			System.out.println(person.name);
		}
	}

}

class Person implements Comparable<Person>{
	String name;
	int age;
	public Person(String n,int x) {
		name = n;
		age = x;
	}
	public int compareTo(Person o) {
		if(age < o.age)
			return -1;
		else if(age > o.age)
			return 1;
		else return 0;
			
	}

    La cosa mi e venuta in mente vedendo la classe Persona, credo che du debba sortare qualsiasi cosa da una Persona a un Nodo ecc quindi ti consiglio di usare l interface comparable in questo modo come puoi vedere tu puoi definire come vorresti ordinare gli oggetti di quel tipo senza modificare la classe MySortedList, quindi se devi ordinare un ogetto di typo A basta che implementi Comparable e il gioco e fatto :) Ho usato i generics perche offrono + restrizioni.

    adesso cmq l output e
    Luca
    Andrea
    Marco

    Spero ti serva ciao e buona giornata
  • L
    Luca
    Pochi posts
    Iscritto da
    gen, 2009
    Messaggi:
    4

    Re: Insert sort java

    Ciao joksy ,
    ti ringrazio dell'aiuto , però a questa soluzione ci avevo già pensato. Il mio problema non è ordinare la lista dopo averla riempita, ma ordinare la lista mentre la riempio.
    Nel tuo esempio, prima fai le add degli oggetti persona sulla lista e poi ne fai il sort(). Quello che intendo io è che ordino mentre aggiungo... l'add ( o il metodo che fa l'add, es. myAdd ) deve, oltre al fare l'add sulla lista, anche scegliere dove farlo, in modo da inserire l'oggetto non al fondo della lista ( come fa il metodo add ), ma inserirlo in modo che l'evento occupi una posizione già ordinata ( in modo crescente ) in base ad es. ad un suo parametro, l'età della persona... ok ?
    Aspetto risposte, ciao!
  • J
    joksy
    Pochi posts
    Iscritto da
    gen, 2009
    Messaggi:
    18

    Re: Insert sort java

    Ciao Luca ,

    Ma devi per forza implementarlo usando un inseriont sort??? perche' ho guardato adesso lo pseudo code dell algoritmo e cmq come parametri chiede un array(nel tuo caso una lista) quindi se costretto a farlo sempre... se hai un numero piccolo di eventi ti conviene ah ogni add fare il sort cosi hai la lista sortata. tipo nel mio caso fai 
    
	public void add(T el){		
			list.add(el);
			sorted();
	}
    cosi hai sempre la lista sortata. se invece hai tanti eventi forse e meglio cambiare strategia xke insertion sort ha coplexity O(n^2) .

    Se invece usi la classe TreeMap<K,V> puoi mappare una key(es = eta) con un value (es = Persona) la classe implementa un RedBlackTree() che un albero bilanciato. Essendo un binary tree ad ogni inserimento l oggetto sara nella sua posizione ordinata. e con la method vlaues() avrai la lista ordinata.
    Il redblack assicura O(log n) in insert delete and search.
Devi accedere o registrarti per scrivere nel forum
7 risposte