Ταξινόμηση quickshort με αναδρομή σε java...

[free4you]

Καλησπέρα παιδιά, έχω γράψει σε άλλο topic για το πρόβλημα που αντιμετωπίζω αλλά τελικά είναι κάπως άσχετο το topic με το θέμα μου οπότε είπα να ανοίξω νέο και για να μην χαλάσω το άλλο αλλά και για να βοηθηθώ εγώ καλύτερα...

 

Η εκφώνηση αυτού που θέλω να υλοποιήσω είναι αυτή:

 

 

Η qsort: είναι μια υλοποίηση της quicksort θέσης. Για την υλοποίηση καλεί την
μέθοδο diamerisi (με παραμέτρους τον πίνακα, τη θέση του πρώτου στοιχείου και το
πλήθος των στοιχείων) και επιστρέφει την θέση του pivot που επιλέχθηκε. Επίσης
έχει διαμερίσει τον πίνακα σύμφωνα με το επιλεγμένο pivot.

 

Η diamerisi: είναι η μέθοδος που καλύπτει τις παραπάνω απαιτήσεις της qsort

 

Και αυτό έχω κάνει μέχρι τώρα:

public static void qsort(int [] data, int f, int n) {
int na;
int nb;
int pivot;
if (n>1)
{
pivot = diamerisi(data, f, n);
na=pivot-f;
nb=n-na-1;
qsort(data, f, na);
qsort(data, pivot+1, nb);
}
}


private static int diamerisi(int [] data, int f, int n) {

int w = f + (int)(Math.random() * (n + 1));
int pivot=data[w];
int i=f;
int j=f+n;

while (i <= j)
{

     while (data[i] < pivot){
     i++;
     }
     while (data[j] > pivot){
     j--;
     }

  if (i <= j){
  int temp = data [i];
  data[i] = data[j];
  data[j] = temp;
  i++;
  j--;
  }
}
return w;
} 

Κάτι πάει στραβά και δεν μπορώ να βρω τι :-( !!! Καμιά ιδέα για να βοηθηθώ???

[pmav99]

1. Μάθε να χρησιμοποιείς τον debugger του IDE σου.

2. Γράψε tests

[free4you]

Το πρώτο δεν ξέρω τι είναι...

Για το δεύτερο καταλαβαίνω ότι εννοείς να το τρέξω με κάποια παραδείγματα σωστά? Έχω φτιάξει μια main που χρησιμοποιεί την Quickshort για ένα πίνακα και βάσει αυτού ξέρω ότι δεν είναι σωστό γιατί δεν μου τον βγάζει τα στοιχεία στη σωστή σειρά!

[pmav99]

Για το 1. δες εδώ: http://bit.ly/17kSyaG

 

Για το 2, ναι αυτό εννοώ αλλά πιο αναλυτικά για να καλύπτεις πολλές περιπτώσεις. Πχ τι γίνεται αν δώσεις ένα άδειο πίνακα; Τι γίνεται αν δώσεις έναν πίνακα με 1 στοιχείο; Τι γίνεται αν δώσεις έναν πίνακα με 2 στοιχεία που δεν χρειάζονται σορτάρισμα κτλ κτλ. Εξετάζεις δηλαδή σε κάθε περίπτωση αν το output του κώδικα σου είναι σωστό ή όχι.

 

Επιπλέον θα γράψεις διαφορετικά tests για την diamerisi και διαφορετικα tests για την qsort. Έτσι θα βρεις που είναι και το λάθος και θα είσαι σίγουρος ότι αυτό που θα παραδώσεις δουλεύει σωστά.

[nucleus]

int w = f + (int)(Math.random() * (n + 1));
int pivot=data[w];

Αυτό σίγουρα σου επιλέγει σωστά το pivot?

[free4you]

Για το 1. δες εδώ: http://bit.ly/17kSyaG

 

Για το 2, ναι αυτό εννοώ αλλά πιο αναλυτικά για να καλύπτεις πολλές περιπτώσεις. Πχ τι γίνεται αν δώσεις ένα άδειο πίνακα; Τι γίνεται αν δώσεις έναν πίνακα με 1 στοιχείο; Τι γίνεται αν δώσεις έναν πίνακα με 2 στοιχεία που δεν χρειάζονται σορτάρισμα κτλ κτλ. Εξετάζεις δηλαδή σε κάθε περίπτωση αν το output του κώδικα σου είναι σωστό ή όχι.

 

Επιπλέον θα γράψεις διαφορετικά tests για την diamerisi και διαφορετικα tests για την qsort. Έτσι θα βρεις που είναι και το λάθος και θα είσαι σίγουρος ότι αυτό που θα παραδώσεις δουλεύει σωστά.

 

 

Δυστυχώς δεν έχω αυτή την στιγμή τον χρόνο να κάτσω να μάθω τον debugger γι' αυτό προσπαθώ με μπακαλίστικο τρόπο.

Όσο για τα test θα τα κάνω αλλά θέλω πρώτα να δω ότι δουλεύει για την συγκεκριμένη περίπτωση και μετά θα πάρω και άλλες περιπτώσεις για να σιγουρευτώ ότι τρέχει καλά γενικά.

 

int w = f + (int)(Math.random() * (n + 1));
int pivot=data[w];

Αυτό σίγουρα σου επιλέγει σωστά το pivot?

 

 

Η math.random εξάγει τυχαία αριθμό στο διάστημα [0,1) και από την στιγμή που εγώ θέλω έναν ακέραιο αριθμό στο διάστημα [f,n+f] η εντολή αυτή μου δίνει έναν ακέραιο αριθμό στο διάστημα [f, n+f+1)!!! Καλά δεν τα λέω???

[nucleus]

http://docs.oracle.com/javase/7/docs/api/java/lang/Math.html

static double random()
Returns a double value with a positive sign, greater than or equal to 0.0 and less than 1

Αν η συνάρτηση είναι αυτή τοτε επιστρέφει double.

 

double * ( n+1) = double το οποίο μετά κάνεις cast σε int. Σίγουρα το κάνει σωστά? Δυστυχώς δεν έχω java εδώ.

[free4you]

Ναι σωστά πρέπει να το κάνει!!! Με την διαμέριση του πίνακα κάτι δεν κάνω καλά!!!

[nucleus]

Αν στην πρώτη κλήση της qsort η diamerisi σου επιστρέψει σαν pivot το πρώτο στοιχείο του αρχικού πίνακα τότε όπως το έχεις μετά

na=pivot-f;
nb=n-na-1;
qsort(data, f, na);
qsort(data, pivot+1, nb);

σε ποιό μέρος του data θα κάνεις αναδρομική κλήση με το qsort(data, f, na);

Αντίστοιχα αν σου επιστρέψει σαν pivot το τελευταίο στοιχείο του πίνακα τότε σε ποιό μέρος του data θα κάνεις  αναδρομική κλήση με qsort(data, pivot+1, nb);

 

Αν σου επιστρέψει οποιοδήποτε άλλο στοιχείο λογικά πρέπει να παίζει σωστά.

 

Οπότε πριν κάνεις αναδρομή θα πρέπει να ελέγχεις αν υπάρχει λόγος να κάνεις αναδρομή.Αν υπάρχουν 0 ή 1 στοιχεία "δεξιά" (μεγαλύτερα του pivot) ή "αριστερά" (μικρότερα του pivot) η αναδρομή σταματά.

[free4you]

Αυτό που ξέχασα να αναφέρω (και αυτό είναι που με δυσκολεύει περισσότερο) είναι ότι η qsort μου έχει δοθεί όπως είναι και δεν μπορώ να την πειράξω... Πρέπει να φτιάξω την diamerisi έτσι ώστε να κολλήσει στην qsort και να την κάνει να δουλέψει...

[nucleus]

Οπότε μήπως πρέπει να ψάξεις μια άλλη συνάρτηση για την "τυχαία" επιλογή του pivot μέσα στα όρια που σου περνάνε σαν όρισμα την συνάρτηση της διαμέρισης?

 

Το θέμα είναι να αποφύγεις τις "ακραίες" τιμές το f και το f+n. Ίσως χρησιμοποιώντας την παρακάτω

 

http://docs.oracle.com/javase/7/docs/api/java/util/Random.html#nextInt%28int%29

[free4you]

Μα δεν θέλω να τις αποφύγω τις ακραίες τιμές, θέλω να μπορώ να διαλέξει για pivot την πρώτη τιμή ή την τελευταία!!!

ουσιαστικά θέλω να κάνει αυτό:

 

Δηλαδή να βρίσκει pivot να χωρίζει αριστερά του pivot τα μικρότερα του στοιχεία, δεξιά του τα μεγαλύτερα του και να δουλεύει αναδρομικά κάθε φορά για το αριστερό και το δεξί κομμάτι του pivot!!!

 

Στην περίπτωση που διαλέξει ακραία τιμή θα δουλέψει αναδρομικά μόνο για το ένα άκρο!!!

[nucleus]

Άλλαξε το τι επιστρέφει η συνάρτηση σου τότε. Πρέπει να επιστρέφει την θέση του pivot στοιχείου μέσα στο πίνακα data αφού κάνει τις αντιμεταθέσεις για να το sortάρει.

 

Αν δεις την εικόνα στο root έχεις αυτό σαν data 7 2 9 4 3 7 6 1. To 6 είναι το pivot στοιχείο.

 

Η συνάρτηση σου όπως είναι τώρα θα επιστρέψει το w = 6 ενώ κανονικά πρέπει να επιστρέψει την τιμή 4 που είναι η θέση του 6 αφού ξεχωρίσει δεξιά και αριστερά του τους μεγαλύτερους και μικρότερους αριθμούς από αυτό. 1 2 3 4 6 7 7 9

[free4you]

  public static void qsort(int [] data, int f, int n) {
        int na;
        int nb; 
        int pivot;
        if (n>1)
        { 
            pivot = diamerisi(data, f, n);
            na=pivot-f;
            nb=n-na-1;
            qsort(data, f, na);
            qsort(data, pivot+1, nb);
}
}
    

private static int diamerisi(int [] data, int f, int n) {
   
   int w = f + (int)(Math.random() * (n + 1));
   int pivot=data[w]; 
   int i=f;
   int j=f+n-1;
while (i < j)
{
   
   while (data[i] < pivot){
       i++;
    }
   while (data[j] > pivot){
        j--;
    }
    if (i < j){
   int temp = data [i];
   data[i] = data[j];
   data[j] = temp;
}
}
   return j;
}

Έκανα διάφορες αλλαγές στο diamerisi οι οποίες στο χαρτί μου δουλεύουν πάρα πολύ καλά αλλά στο Bluej δεν το τρέχει καν!!! Δεν μπορώ να καταλάβω!!!