current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 4.7 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 0 down vote favorite

I am trying to code sorting algorithm with Javascript. The pseudocode is in my link. This is my Go Playground link. http://play.golang.org/p/wQwO6Wvd7b

As you see, it works in other languages. (I tried with Python, C, C++, Ruby, Go with the same code and they all work perfect.) So I did the exact same thing with Javascript but it is not working, and I can't figure out why. Thanks for Chris in my previous posting: Javascript Sorting. Allocation fail process out of memory error

I figured out my code in Javascript goes beyond the index limit with recursion but I have no clue why and how it is possible in Javascript while other languages just do the right job as I code. I am definitely missing something fundamental in Javascript and in recursion. Could any body help me figure out? (Not homework, just independent self-studying) I am pretty new to Javascript.

I don't think I would need to do sorting in Javascript but I want to know what I am doing wrong.

Below is my code for the purpose of error checking. 

  var arr = [-1, 5, 7, 4, 0, 1, -5];
  console.log("Unsorted Array:", arr);
  console.log("# of elements in array:", arr.length)

  function Partition(arr, first_index, last_index) {
        console.log("---")  
        console.log("# of elements in array:", arr.length)
        console.log("First index is", first_index);
        console.log("Last index is", last_index);
        console.log("---")  
        var x = arr[last_index];
        var i = first_index - 1;

        for (var j = 0; j < arr.length-1; j++) {
              if (j > 100) {
                    console.log("Looping way too much.");
                    return;
              }
              if (arr[j] <= x) {
                    i += 1;
                    console.log("Swap index:", i, j);
                    var temp_1 = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp_1;
              }
        }
        console.log("Swap index:", (i+1), last_index);
        var temp_2 = arr[i+1];
        arr[i+1] = arr[last_index];
        arr[last_index] = temp_2;

        return i+1;
  }

  function QSort(arr, first_index, last_index) {
        console.log("QuickSort index:", first_index, last_index);

        if (first_index < last_index) {
              var mid = Partition(arr, first_index, last_index);
              QSort(arr, first_index, mid-1);
              QSort(arr, mid+1, last_index);
        }
  }

  QSort(arr, 0, arr.length-1);
  console.log("Sorted Array:", arr);

And I am guessing why this is looping too much is below. I found out I am doing something wrong with recursion.

number of elements in array: 8
First index is 2
Last index is 6

Swap index: 2 0
Swap index: 3 2
Swap index: 4 3
Swap index: 5 4
Swap index: 6 5
Swap index: 7 6
Swap index: 8 6
QuickSort index: 2 7

number of elements in array: 9
First index is 2
Last index is 7

on and on

share|improve this question
    
Most probably you have some logic error. There's nothing special about recursion in javascript. – kirilloid Sep 6 '13 at 22:40
1  
I didn't get that into it, but there may be a possibility that your array length is changing. Maybe try for(var j=0,l=arr.length-1; j<l; j++){. Either way, this should be technologically faster. Also i+=1; is the same as i++;. – PHPglue Sep 6 '13 at 22:40
up vote 0 down vote accepted

I don't how this would work in other languages because this is written incorrectly. The loop in the partition method goes to work on the entire array, when really it should only be working on the part that it is told to work on (in between first_index and last_index)

This line of code:

for (var j = 0; j < arr.length-1; j++)

Should be:

for (var j = first_index; j < last_index; j++)
share|improve this answer
    
Thanks! It works – user2702047 Sep 6 '13 at 22:59
    
Oh, why thank you for accepting. Good luck in your future coding endeavors! – mdenton8 Sep 7 '13 at 0:46
up vote 1 down vote

The for loop inside of the Partition function should be written as :

for (var j = first_index; j < last_index; j++) {...}

instead of

for (var j = 0; j < arr.length-1; j++) {...}

Looping from 0 to arr.length-1 makes it create new elements inside of the original array instead of just swapping them.

share|improve this answer
    
Thanks a lot! It works. I did it right in Go but stupidly I did that wrong in Javascript. Thanks millions! – user2702047 Sep 6 '13 at 22:59
up vote 0 down vote

SPOILER ALERT - this fiddle has a working version of quicksort. I kinda struggled with your version so I wrote my own.

Algorithms like quicksort provide lots of opportunity for errors (lots of places to be off by one, etc.)

As a general suggestion, you might want to make a quicksort method that you call by just passing the array:

function quick_sort(array) {
    qsort(array, 0, array.length);
    console.log(array);
}

Hope this helps

http://jsfiddle.net/mwa4G/

http://en.literateprograms.org/Quicksort_(JavaScript)

share|improve this answer
    
Yep, quicksort is really error-prone thing. – kirilloid Sep 6 '13 at 22:43
    
Thanks a lot. jsfiddle is good to know. Thanks! – user2702047 Sep 6 '13 at 23:00
    
yeah definitely a good resource! happy coding – Tore Hanssen Sep 6 '13 at 23:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.