[R] what is wrong with my quicksort?

[Mark Leeds]

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 <conny-clauss at gmx.de> 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 <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.
>