Sorting Algorithms

[InDiO]

Λοιπόν έχω μια αρκετά μεγάλη εργασία για το Πανεπ. και θα σας πρήξω λίγο ρε παιδιά. Όποιος μπορεί ας βοηθήσει, πιστεύω ότι δεν είναι τπτ εξειζητημένο...

Αρχικά για τον Quicksort, όπως αυτός υλοποιείται στο Introduction to Algorithms(το γνωστό άσπρο γκουμούτσι-βίβλος), ή όπως αλλιώς τσπ. Ο αλγόριθμος είναι αναδρομικός. Παρόλα αυτά, δεν αναφέρεται πουθενά τί αρχικές τιμές δίνει στις μεταβλητές(που σπάει το array) και έτσι ψιλοκωλύομαι να κατανοήσω πλήρως από τί φάση ξεκινάει ο αλγ.

thnx,

Waiting for your help.

[HdkiLLeR]

Koitaxe na deis ean anaferese ston Quicksort pou diatipothike apo ton Hoare iparxoun liga pragmata ta opoia borei na se voithisoun:

I vasiki idea einai to spasimo toy pinaka se ipopinakes eos otou o kathenas apo tous ipipinakes poy exei ginei i diamerisi na einai taxinomimenos i na exei mono ena stoixeio.I diadikasia auti borei na oristei anadromika afou oti kaneis gia ton arxiko pinaka kaneis kai gia tous ipopinakes...Prokeimenou na diameristei o pinakas orizetai enas odigos (pivot) o opoios einai kapio stoixeio toy pinaka(sinithos to mesaio) i toy ipopinaka.Akoma xrisimopoioude alloi 2 metrites (left) kai (right) o opoioi diatrexoun ton pinaka o enas apo ta aristera pros ta dexia kai o allos apo ta dexia pros ta aristera.Kathe fora poy o deiktis left sinadaei ena stoixeio poy einai megalitero i iso apo ton odigo kai o deiktis right sinada ena stoixeio poy einai mikrotero i iso apo ton odigo,adalasodai ta periexomena twn thesewn left kai right kai oi diktes proxwroun kata mia thesi o kathenas sinexizodas tin idia douleia mexris otou to left ginei megalitero toy right.Tote se ekeino to simio ginetai diamerismos toy pinaka se ipopinakes stous opoious boreis na efarmoseis tin idia diadikasia anexartita.Sto stoixeio diladi toy left>right tha kaneis 2 kliseis toy quicksort gia left=1 kai right=tin thesi poy egeine left>right kai gia left=thesi left>rigth+1 kai right=[n](n=megethos toy pinaka) kai stin sinexeia oi ipiponakes autoi tha xanadierethoun me ton idio akrivws tropo se ipopinakes klp...etsi ilopoieitai i anadromi ston quicksort.---Elpizw na voithisa.

[InDiO]

Thanx re file hdkiller. Exo ilopoiisei se java ton algorithmo ayto, stin ousia metafrasa ton psedokodika(me kapoies allages), alla gia tin ora pairno mono exceptions.Tha to prospathiso akomi ligo + an do oti den ginetai tpt, tha postaro ton kodika na mou peite ti gnomi sas gia to ti paei strava...

[HdkiLLeR]

Ama ginetai tha ithela na mou ton steileis ean den exeis adirisi vevaia kai ean to exeis grapsei se java.---> [email protected]

[Γηρυόνης]

Εγώ θα σου πρότεινα να τον καταχωρήσεις εδώ μήπως και μπορέσουμε να σε βοηθήσουμε όλοι.

[InDiO]

Yo guys, thanx gia to endiaferon...

Here's the code:

<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">code:</font><hr><pre>int k;

public void quickSort(int A[],int l,int r)

{

i=l;

k=r+1;

int s=A[l];

while(i<k)

{

for(;A>=s;i++);

for(;A[k]<=s;k--);

if(k>i)

{

int temp=A[k];

A[k]=A;

A=temp;

}

}

int temp=A[l];

A[l]=A[k];

A[k]=temp;

if(l<k-1) quickSort(A,l,k-1);

if(k+1<r) quickSort(A,k+1,r);

} </pre><hr></blockquote><p>Mporo na ton bro etoimo + na douleyei, alla tha me endiefere perissotero na katalavo giati den douleyei aytos...tnx<p>[ 15-12-2001: Message edited by: InDiO ]</p>

[Γηρυόνης]

Για αρχή θα σου πρότεινα να καταχωρήσεις τυχών μηνύματα λάθους... Καθώς και τις αρχικές τιμές που δίνεις στις μεταβλητές σου.<p> Επίσης είσαι σίγουρος ότι αυτό το πρόγραμμα γίνεται compile; Η σύνταξη<p><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">code:</font><hr><pre>

for(;A>=s;i++);

</pre><hr></blockquote><p> είναι λάθος γιατί το Α είναι πίνακας και όχι ακέραιος. Ελπίζω να είναι συντακτικό λάθος και μόνο.<p> Κάνε αυτές τι αλλαγές και ξανακάνε μία καταχώρηση με πιο πολλές πληροφορίες.

[InDiO]

minima lathous aytou tou kodika einai to (gnosto) arrayIndexOutOfBoundsException, otan prospatho na kano quickSort(Array,int,int).

Oso gia tis arxikes times einai ena apo ta provlimata mou, kathos den ksero se ti thesi prepei na einai ta arxika indexes...(arxi-telos tou array?).

O kodikas kanei compile, ayto pou eipes girioni einai ontos lathos pou egine kata to copy paste. Se ayti tin grammi einai

<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">code:</font><hr><pre>

while(i<k)

{

for(;A>=s;i++);

for(;A[k]<=s;k--);

if(k>i)

</pre><hr></blockquote>

kai ta loipa...

[Γηρυόνης]

Το ArrayIndexOutOfBoundsException πρέπει να βγαίνει στην παρακάτω γραμμή:<p><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">code:</font><hr><pre>

for(;A>=s;i++);

</pre><hr></blockquote><p> Ο λόγος πίσω από αυτό είναι ότι ο for βρόχος προσπαθεί να υπολογίσει την τιμή της μεταβλητής i βασιζόμενος στην πράξη A >= s. Αυτός ο βρόχος θα τελειώσει μόνο αν ο αριθμός στην i-κοστή θέση του πίνακα Α είναι μικρότερος του s. Από τη στιγμή που είναι τότε θα τελειώσει και το i θα έχει μία τιμή η οποία θα είναι ο αριθμός των επαναλήψεων του βρόχου + την αρχική του τιμή.<p> Αν υποθέσουμε ότι αρχικώς το l έχει μία τιμή (ας πούμε 0) και ο Α[] έχει τις τιμές 1, 2, 8, 4, 13 τότε Α[0] = 1, Α[1] = 2, Α[2] = 8, Α[3] = 4, Α[4] = 13, οπότε ο βρόχος δε θα εγκαταλειφθεί ποτέ διότι το i = l => i = 0, s = A[l] => s = A[0] => s = 1 και A = A[0] = 1. Οπότε βλέπουμε ότι και το s και το A ικανοποιούνε τη συνθήκη A>=s. Αυτή η συνθήκη θα ικανοποιείται παντοτινά (στο συγκεκριμένο παράδειγμα) από τη στιγμή που όλοι οι αριθμοί στον πίνακα Α είναι μεγαλύτεροι από το 1. Για να σταματήσει θα πρέπει να υπάρξει μία τιμή μικρότερη του 1.<p> Αυτό που γίνεται και σου βγάζει ArrayIndexOutOfBoundsException είναι ότι από τη στιγμή που ο βρόχος τρέχει ατελείωτα, σε κάποια στιγμή η μεταβλητή i θα έχει μία τιμή η οποία θα είναι μεγαλύτερη κατά 1 από το μήκος του πίνακα. Δηλαδή όταν το i γίνει 5 τότε η VM θα προσπαθήσει να υπολογίσει την έκτη θέση του πίνακα Α, δηλαδή τη A[5]. Από ότι βλέπουμε όμως στο παράδειγμα δεν υπάρχιε Α[5] και έτσι η VM ρίχνει την ArrayIndexOutOfBoundsException. Για να μην έχεις παρόμοιο πρόβλημα θα πρέπει η πρώτη τιμή του πίνακα Α να μην είναι η μικρότερη.<p>[ 16-12-2001: Message edited by: Γηριόνης ]</p>

[InDiO]

Re paidia thanx gia tin voitheia. Telika ton eftiaksa-ftiaxame me tin voitheia tou symfoititi-syninsomniac greco...Mallon tetoia zitimata den prepei na ta antimetopizeis monos sou!

An kapoios thelei ton kodika, as mou steilei PM...leme tora

thanks again!