what is wrong with my quicksort?

9 messages
Open this post in threaded view
|

what is wrong with my quicksort?

 Hey guys, I tried to program quicksort like this but somethings wrong. please help         >partition <- function(x, links, rechts){ > > i <- links > j <- rechts > t <- 0 > pivot <- sample(x[i:j],1) > > while(i <= j){ > > while(x[i] <= pivot){ > i = i+1} > > while(x[j] >= pivot){ > j = j-1} > > if( i <= j){ > > t = x[i] > x[i] = x[j] > x[j] = t > > i=i+1 > j=j-1 > > } > print(pivot) > > > } > #Rekursion > > if(links < j){ > partition(x, links, j)} > if(i < rechts){ > partition(x, i, rechts)} > > return(x) > } > > >quicksort <- function(x){ > > > > partition(x, 1, length(x)) >} thx
Open this post in threaded view
|

Re: what is wrong with my quicksort?

 have you tried to debug it yourself.  All you said is that 'it went wrong'.  that is not a very clear statement of the problem.  If I were to start looking at it, I would put some print statements in it to see what is happening on eachpath and with each set of data.  Have you tried this? Sent from my iPad On Sep 3, 2011, at 21:51, warc <[hidden email]> wrote: > Hey guys, > I tried to program quicksort like this but somethings wrong. > > please help > > >     >> partition <- function(x, links, rechts){ >>     >>    i <- links >>    j <- rechts >>    t <- 0                         >>    pivot <- sample(x[i:j],1) >>     >>    while(i <= j){ >>         >>        while(x[i] <= pivot){     >>            i = i+1} >>             >>        while(x[j] >= pivot){     >>            j = j-1} >>             >>        if( i <= j){             >>             >>            t = x[i] >>            x[i] = x[j] >>            x[j] = t >>             >>            i=i+1 >>            j=j-1 >>             >>            } >>            print(pivot)     >>         >>         >>        } >>    #Rekursion >>     >>    if(links < j){                 >>        partition(x, links, j)}             >>    if(i < rechts){                 >>        partition(x, i, rechts)} >>     >>    return(x) >>    } >>     >> >> quicksort <- function(x){ >>         >> >>         >>        partition(x, 1, length(x)) >> } > > > > thx > > -- > View this message in context: http://r.789695.n4.nabble.com/what-is-wrong-with-my-quicksort-tp3788681p3788681.html> Sent from the R help mailing list archive at Nabble.com. > > ______________________________________________ > [hidden email] mailing list > https://stat.ethz.ch/mailman/listinfo/r-help> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html> and provide commented, minimal, self-contained, reproducible code. ______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|

Re: what is wrong with my quicksort?

 Hi: I looked it up in google because I couldn't remember how quicksort worked. ( i'm getting old ). the java code is below. I didn't translate it but what you are doing incorrectly is calling partition recursively when you need to call the quicksort algorithm recursively. you'll see what I mean if you look at the java code below. there are many links on the internet that explains why it works with examples etc. here's one: http://www.algolist.net/Algorithms/Sorting/Quicksort good luck. #============================================================== int partition(int arr[], int left, int right) {       int i = left, j = right;       int tmp;       int pivot = arr[(left + right) / 2];       while (i <= j) {             while (arr[i] < pivot)                   i++;             while (arr[j] > pivot)                   j--;             if (i <= j) {                   tmp = arr[i];                   arr[i] = arr[j];                   arr[j] = tmp;                   i++;                   j--;             }       };       return i; } #=============================================================== void quickSort(int arr[], int left, int right) {       int index = partition(arr, left, right);       if (left < index - 1)             quickSort(arr, left, index - 1);       if (index < right)             quickSort(arr, index, right); } On Sat, Sep 3, 2011 at 10:50 PM, Jim Holtman <[hidden email]> wrote: > have you tried to debug it yourself.  All you said is that 'it went wrong'.  that is not a very clear statement of the problem.  If I were to start looking at it, I would put some print statements in it to see what is happening on eachpath and with each set of data.  Have you tried this? > > Sent from my iPad > > On Sep 3, 2011, at 21:51, warc <[hidden email]> wrote: > >> Hey guys, >> I tried to program quicksort like this but somethings wrong. >> >> please help >> >> >> >>> partition <- function(x, links, rechts){ >>> >>>    i <- links >>>    j <- rechts >>>    t <- 0 >>>    pivot <- sample(x[i:j],1) >>> >>>    while(i <= j){ >>> >>>        while(x[i] <= pivot){ >>>            i = i+1} >>> >>>        while(x[j] >= pivot){ >>>            j = j-1} >>> >>>        if( i <= j){ >>> >>>            t = x[i] >>>            x[i] = x[j] >>>            x[j] = t >>> >>>            i=i+1 >>>            j=j-1 >>> >>>            } >>>            print(pivot) >>> >>> >>>        } >>>    #Rekursion >>> >>>    if(links < j){ >>>        partition(x, links, j)} >>>    if(i < rechts){ >>>        partition(x, i, rechts)} >>> >>>    return(x) >>>    } >>> >>> >>> quicksort <- function(x){ >>> >>> >>> >>>        partition(x, 1, length(x)) >>> } >> >> >> >> thx >> >> -- >> View this message in context: http://r.789695.n4.nabble.com/what-is-wrong-with-my-quicksort-tp3788681p3788681.html>> Sent from the R help mailing list archive at Nabble.com. >> >> ______________________________________________ >> [hidden email] mailing list >> https://stat.ethz.ch/mailman/listinfo/r-help>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html>> and provide commented, minimal, self-contained, reproducible code. > > ______________________________________________ > [hidden email] mailing list > https://stat.ethz.ch/mailman/listinfo/r-help> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html> and provide commented, minimal, self-contained, reproducible code. > ______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|

Re: what is wrong with my quicksort?

 In reply to this post by jholtman the error message I get is:            Error in while (x[j] >= pivot) { : Argument has length 0 so either pivot or x[j] is NULL.  and it somestimes happens the first time the program enters the recursion, sometimes the 6. or anywhere inbetween. jholtman wrote have you tried to debug it yourself.  All you said is that 'it went wrong'.  that is not a very clear statement of the problem.  If I were to start looking at it, I would put some print statements in it to see what is happening on eachpath and with each set of data.  Have you tried this? Sent from my iPad On Sep 3, 2011, at 21:51, warc <[hidden email]> wrote: > Hey guys, > I tried to program quicksort like this but somethings wrong. > > please help > > >     >> partition <- function(x, links, rechts){ >>     >>    i <- links >>    j <- rechts >>    t <- 0                         >>    pivot <- sample(x[i:j],1) >>     >>    while(i <= j){ >>         >>        while(x[i] <= pivot){     >>            i = i+1} >>             >>        while(x[j] >= pivot){     >>            j = j-1} >>             >>        if( i <= j){             >>             >>            t = x[i] >>            x[i] = x[j] >>            x[j] = t >>             >>            i=i+1 >>            j=j-1 >>             >>            } >>            print(pivot)     >>         >>         >>        } >>    #Rekursion >>     >>    if(links < j){                 >>        partition(x, links, j)}             >>    if(i < rechts){                 >>        partition(x, i, rechts)} >>     >>    return(x) >>    } >>     >> >> quicksort <- function(x){ >>         >> >>         >>        partition(x, 1, length(x)) >> } > > > > thx > > -- > View this message in context: http://r.789695.n4.nabble.com/what-is-wrong-with-my-quicksort-tp3788681p3788681.html> Sent from the R help mailing list archive at Nabble.com. > > ______________________________________________ > [hidden email] mailing list > https://stat.ethz.ch/mailman/listinfo/r-help> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html> and provide commented, minimal, self-contained, reproducible code. ______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|

Re: what is wrong with my quicksort?

 On Sep 4, 2011, at 13:18 , warc wrote: > the error message I get is: > >           Error in while (x[j] >= pivot) { : Argument has length 0 > > so either pivot or x[j] is NULL. > and it somestimes happens the first time the program enters the recursion, > sometimes the 6. or anywhere inbetween. > Well, then print out x, j, and pivot just before hitting that test (i.e., before the loop and at the end of it). With sample() in the code, you will naturally get different results at each run. It's your problem, so your debugging, but I'd wager that nothing is keeping j from hitting zero if you sample a pivot equal to min(x). > > > jholtman wrote: >> >> have you tried to debug it yourself.  All you said is that 'it went >> wrong'.  that is not a very clear statement of the problem.  If I were to >> start looking at it, I would put some print statements in it to see what >> is happening on eachpath and with each set of data.  Have you tried this? >> >> Sent from my iPad >> >> On Sep 3, 2011, at 21:51, warc <[hidden email]> wrote: >> >>> Hey guys, >>> I tried to program quicksort like this but somethings wrong. >>> >>> please help >>> >>> >>> >>>> partition <- function(x, links, rechts){ >>>> >>>>   i <- links >>>>   j <- rechts >>>>   t <- 0                         >>>>   pivot <- sample(x[i:j],1) >>>> >>>>   while(i <= j){ >>>> >>>>       while(x[i] <= pivot){     >>>>           i = i+1} >>>> >>>>       while(x[j] >= pivot){     >>>>           j = j-1} >>>> >>>>       if( i <= j){             >>>> >>>>           t = x[i] >>>>           x[i] = x[j] >>>>           x[j] = t >>>> >>>>           i=i+1 >>>>           j=j-1 >>>> >>>>           } >>>>           print(pivot)     >>>> >>>> >>>>       } >>>>   #Rekursion >>>> >>>>   if(links < j){                 >>>>       partition(x, links, j)}             >>>>   if(i < rechts){                 >>>>       partition(x, i, rechts)} >>>> >>>>   return(x) >>>>   } >>>> >>>> >>>> quicksort <- function(x){ >>>> >>>> >>>> >>>>       partition(x, 1, length(x)) >>>> } >>> >>> >>> >>> thx >>> >>> -- >>> View this message in context: >>> http://r.789695.n4.nabble.com/what-is-wrong-with-my-quicksort-tp3788681p3788681.html>>> Sent from the R help mailing list archive at Nabble.com. >>> >>> ______________________________________________ >>> [hidden email] mailing list >>> https://stat.ethz.ch/mailman/listinfo/r-help>>> PLEASE do read the posting guide >>> http://www.R-project.org/posting-guide.html>>> and provide commented, minimal, self-contained, reproducible code. >> >> ______________________________________________ >> [hidden email] mailing list >> https://stat.ethz.ch/mailman/listinfo/r-help>> PLEASE do read the posting guide >> http://www.R-project.org/posting-guide.html>> and provide commented, minimal, self-contained, reproducible code. >> > > > -- > View this message in context: http://r.789695.n4.nabble.com/what-is-wrong-with-my-quicksort-tp3788681p3789080.html> Sent from the R help mailing list archive at Nabble.com. > > ______________________________________________ > [hidden email] mailing list > https://stat.ethz.ch/mailman/listinfo/r-help> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html> and provide commented, minimal, self-contained, reproducible code. -- Peter Dalgaard, Professor, Center for Statistics, Copenhagen Business School Solbjerg Plads 3, 2000 Frederiksberg, Denmark Phone: (+45)38153501 Email: [hidden email]  Priv: [hidden email] "Døden skal tape!" --- Nordahl Grieg ______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|

Re: what is wrong with my quicksort?

 In reply to this post by warc Hi: I sent this yesterday but it must be out there in hyperspace somewhere because it never appeared on the R-list. Also, I had to look quicksort up because it's been too long. Anyway,  your code looks similar to the java code at http://www.algolist.net/Algorithms/Sorting/Quicksort. and I show it below. The difference is that you are calling partition recursively while the code below calls quicksort recursively. that probably makes a difference but I didn't test it. hopefully that's the problem. good luck. # quicksort Java code #================================================================ int partition(int arr[], int left, int right) {       int i = left, j = right;       int tmp;       int pivot = arr[(left + right) / 2];       while (i <= j) {             while (arr[i] < pivot)                   i++;             while (arr[j] > pivot)                   j--;             if (i <= j) {                   tmp = arr[i];                   arr[i] = arr[j];                   arr[j] = tmp;                   i++;                   j--;             }       };       return i; } void quickSort(int arr[], int left, int right) {       int index = partition(arr, left, right);       if (left < index - 1)             quickSort(arr, left, index - 1);       if (index < right)             quickSort(arr, index, right); } On Sun, Sep 4, 2011 at 7:18 AM, warc <[hidden email]> wrote: > the error message I get is: > >           Error in while (x[j] >= pivot) { : Argument has length 0 > > so either pivot or x[j] is NULL. >  and it somestimes happens the first time the program enters the recursion, > sometimes the 6. or anywhere inbetween. > > > > jholtman wrote: >> >> have you tried to debug it yourself.  All you said is that 'it went >> wrong'.  that is not a very clear statement of the problem.  If I were to >> start looking at it, I would put some print statements in it to see what >> is happening on eachpath and with each set of data.  Have you tried this? >> >> Sent from my iPad >> >> On Sep 3, 2011, at 21:51, warc <[hidden email]> wrote: >> >>> Hey guys, >>> I tried to program quicksort like this but somethings wrong. >>> >>> please help >>> >>> >>> >>>> partition <- function(x, links, rechts){ >>>> >>>>    i <- links >>>>    j <- rechts >>>>    t <- 0 >>>>    pivot <- sample(x[i:j],1) >>>> >>>>    while(i <= j){ >>>> >>>>        while(x[i] <= pivot){ >>>>            i = i+1} >>>> >>>>        while(x[j] >= pivot){ >>>>            j = j-1} >>>> >>>>        if( i <= j){ >>>> >>>>            t = x[i] >>>>            x[i] = x[j] >>>>            x[j] = t >>>> >>>>            i=i+1 >>>>            j=j-1 >>>> >>>>            } >>>>            print(pivot) >>>> >>>> >>>>        } >>>>    #Rekursion >>>> >>>>    if(links < j){ >>>>        partition(x, links, j)} >>>>    if(i < rechts){ >>>>        partition(x, i, rechts)} >>>> >>>>    return(x) >>>>    } >>>> >>>> >>>> quicksort <- function(x){ >>>> >>>> >>>> >>>>        partition(x, 1, length(x)) >>>> } >>> >>> >>> >>> thx >>> >>> -- >>> View this message in context: >>> http://r.789695.n4.nabble.com/what-is-wrong-with-my-quicksort-tp3788681p3788681.html>>> Sent from the R help mailing list archive at Nabble.com. >>> >>> ______________________________________________ >>> [hidden email] mailing list >>> https://stat.ethz.ch/mailman/listinfo/r-help>>> PLEASE do read the posting guide >>> http://www.R-project.org/posting-guide.html>>> and provide commented, minimal, self-contained, reproducible code. >> >> ______________________________________________ >> [hidden email] mailing list >> https://stat.ethz.ch/mailman/listinfo/r-help>> PLEASE do read the posting guide >> http://www.R-project.org/posting-guide.html>> and provide commented, minimal, self-contained, reproducible code. >> > > > -- > View this message in context: http://r.789695.n4.nabble.com/what-is-wrong-with-my-quicksort-tp3788681p3789080.html> Sent from the R help mailing list archive at Nabble.com. > > ______________________________________________ > [hidden email] mailing list > https://stat.ethz.ch/mailman/listinfo/r-help> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html> and provide commented, minimal, self-contained, reproducible code. > ______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|

Re: what is wrong with my quicksort?

 In reply to this post by warc Hey again and thanks for all the help this is what i have for now but it still doesn't work, the main problem is the random pivot i think (error in while (x[j] >= pivot) { : Argument has length 0) >partition <- function(x, links, rechts){ > > i <- links > j <- rechts > t <- 0 > pivot <- x[sample((links:rechts),1)] > > > while(i <= j){ > > while(x[i] <= pivot){ >                      i = i+1} > > while(x[j] >= pivot){ > j = j-1} > > if( i <= j){ > > > t = x[i] > x[i] = x[j] > x[j] = t > > i=i+1 > j=j-1 > > } > } > return(pivot) > } > >qsort <- function(x, links, rechts){ > > index <- partition(x, links, rechts) > > if((links < (index+1))&(length(x)>1)){ > qsort(x, links, index+1)} > > > if((index < rechts)&(length(x)>1)){ > qsort(x, index, rechts)} > > return(x) > } > > >quicksort <- function(x){ > > if(length(x) == 0)stop("empty Vector") > > qsort(x, 1, length(x)) >} but whatever i will just keep on trying thank you again