[R] what is wrong with my quicksort?

[Daniel Nordlund]

> -----Original Message-----
> From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org]
> On Behalf Of peter dalgaard
> Sent: Sunday, September 04, 2011 11:09 AM
> To: warc
> Cc: r-help at 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-clauss at 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 at 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 at 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 at 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.mes at cbs.dk  Priv: PDalgd at gmail.com
> "Døden skal tape!" --- Nordahl Grieg
> 
> ______________________________________________
> R-help at 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.