[java] un esercizio per chi ne ha voglia

[Lucked]

Ciao a tutti. Ho fatto un esercizio di java, che penso ci sia più di una soluzione, inoltre la mia(credo non sia l'unica) non mi piace molto.
Se ne avete voglia vi scrivo il testo, sono poche righe ma ben pensate, cosi oltre a esercitarvi, poi potremmo confrontarlo.

metodo statico che presi come paramentri un array di interi e un intero faccia in modo che tutti gli elementi minori di x precedano quelli maggiori di x. IL METODO DEVE USARE SOLO UN CICLO e non avere array aggiuntivi.

[pippo75]

Quick Sort

[Lucked]

Non è vero :bubu:

[LeleFT]

Beh... c'è andato vicino: è la procedura Partition del QuickSort.

  private static int partition(int[] a, int pivot) {
    int i = 0; 
    int j = a.length - 1;
    while (i < j) {
      while (a[i] < pivot) i++;
      while (a[j] > pivot) j--;
      if (i < j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
      }
    }
    return i; 
  }

[Lucked]

apparte che prendere i metodi confezionati era fuori spirito di come l'avevo proposto, inoltre deve avere solo un ciclo, ciò vuol dire che se scegli un while poi hai esaurito la scorta di cicli che puoi usare.

[LeleFT]

Ok... allora modifichiamo il codice, rendendolo un po' più bruttino:

private static int partition(int[] a, int pivot) {
  int i = 0; 
  int j = a.length - 1;
  while (i < j) {
    if (a[i] < pivot) {
      i++;
    } else {
      if (a[j] > pivot) {
        j--;
      } else {
        if (i < j) {
          int tmp = a[i];
          a[i] = a[j];
          a[j] = tmp;
        }
      }
    }
  }
  return i; 
}

Ciao.

[anx721]

I precedenti algoritmi comunque funzionano solo se non ci sono ripetizioni all'interno dell'array, una versione che funziona anche in questo caso è:

void part(int array[], int x){
    int last = array.length - 1;
    int first = 0;
    int swap = 1;
    for(; ((first < last) && (swap <= last)); ){
        //primo elemento maggiore del pivot
        if(array[first] > x){
            int temp = array[first];
            array[first] = array[last];
            array[last] = temp;
            last--;
        }
        //primo elemento minore del pivot
        else if(array[first] < x){
            first++;
            swap++;
        }//primo elemento uguale al pivot
        //cerco tra gli elementi rimasti uno minore del pivot
        else{
            if(array[swap] < array[first]){
                int temp = array[first];
                array[first] = array[swap];
                array[swap] = temp;
                first++;
                swap = first + 1;
            }
            else
                swap++;
        }
        
    }
} 

[LeleFT]

Beh... a dire il vero quella è la procedura effettiva della Partition del QuickSort (non l'ho inventata io)... cosa c'entrano gli elementi ripetuti? Il confronto si basa con un pivot, e se ci sono elementi uguali li posso anche scambiare che non cambia nulla...



Ciao.

[anx721]

Originariamente inviato da LeleFT
cosa c'entrano gli elementi ripetuti? Il confronto si basa con un pivot, e se ci sono elementi uguali li posso anche scambiare che non cambia nulla...

Bhè, se l'elemento pivot è presente piu volte nell'array l'algoritmo potrebbe non funzionare, pensa al caso in cui il primo e l'ultimo elemento siano uguali al pivot: l'algoritmo continuerebbe a scambiarli l'uno con l'altro senza sbloccarsi,

[anx721]

Piccolo aggiustamento:

void part(int array[], int x){
    int last = array.length - 1;
    int first = 0;
    int swap = 1;
    while((first < last) && (swap <= last)){
        //primo elemento maggiore del pivot
        if(array[first] > x){
            int temp = array[first];
            array[first] = array[last];
            array[last] = temp;
            last--;
        }
        //primo elemento minore del pivot
        else if(array[first] < x){
            first++;
            swap++;
        }
        //primo elemento uguale al pivot
        //cerco tra queli rimanenti un elemento diverso
        //dal pivot e lo scambio col primo elemento
        else{
            if(array[swap] != x){
                array[first] = array[swap];
                array[swap] = x;
            }
            else
                swap++;
        }
    }
}