> -----Original Message-----
> From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-project.org]
> On Behalf Of peter dalgaard
> Sent: Sunday, September 04, 2011 11:09 AM
> To: warc
> Cc: r-help@r-project.org
> Subject: Re: [R] 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).
>
I think Peter is correct that there is a problem with the stopping rules.
However, there is also a problem in that quick sort is designed to sort in
place, and therefore the recursive calls must pass the vector to be sorted by
reference (and R passes by value). Otherwise, changes are only being made to
copies and will be lost when returning from the partition function.
I am reluctant to provide a solution, because (1) R already has a sort routine,
therefore (2) this may be homework, and (3) I am not a skilled R programmer.
However, I did successfully write a quick sort routine using a standard
algorithm with 2 changes:
1. don't pass the vector to be sorted to the partition function,
2. use the <<- operator when swapping elements to make changes in place
If appropriate, I would be willing to post my solution for discussion. I could
probably benefit from such a discussion myself.
Hope this is helpful,
Dan
Daniel Nordlund
Bothell, WA USA
>
> >
> >
> > 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 <conny-cla...@gmx.de> 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.
> >>>
> >>> ______________________________________________
> >>> R-help@r-project.org 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.
> >>
> >> ______________________________________________
> >> R-help@r-project.org 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.
> >
> > ______________________________________________
> > R-help@r-project.org 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: pd....@cbs.dk Priv: pda...@gmail.com
> "Døden skal tape!" --- Nordahl Grieg
>
> ______________________________________________
> R-help@r-project.org 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.
______________________________________________
R-help@r-project.org 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.
