1

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

Improve this question
2
  • Most probably you have some logic error. There's nothing special about recursion in javascript. Commented Sep 6, 2013 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++;. Commented Sep 6, 2013 at 22:40

3 Answers 3

Reset to default
1

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++)
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Oh, why thank you for accepting. Good luck in your future coding endeavors!
1

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.

Improve this answer

1 Comment

Thanks a lot! It works. I did it right in Go but stupidly I did that wrong in Javascript. Thanks millions!
0

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)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.