Quicksort in Javascript Bug

Question

Hoping to get some help with this Quicksort algorithm in Javascript (it's not for homework or anything, just fun) - it's not working and I'm not sure where I'm going wrong.

function quicksort ( arr ) {
        // Launch the sorting process.
        sort(arr, 0, arr.length - 1 );

        /**
         * swap
         * takes in an array and two indexes,
         * swaps the elements in the array at those indexes
         */
        function swap ( arr, a, b ) {
            var temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

        function partition ( arr, l, r) {
            var p = arr[r],
                i = l - 1,
                j = l;
            while ( j < r - 1) {
                if (arr[j] <= p) {
                    swap ( arr, ++i, j );
                }
                j++;
            }

            swap (arr, i + 1, r);
            return i + 1;
        }

        function sort ( arr, l, r ) {
            var p;
            if (l < r) {
                p = partition( arr, l, r );
                sort( arr, l, p - 1);
                sort( arr, p + 1, r);
            } else {
                console.log(arr);    
            }
        }
    }

I give it quicksort( [8,3,2,1,5,1,3] ) and it returns: [ 1, 3, 2, 3, 5, 8, 1 ] — graemeboy
– graemeboy, Commented Oct 2, 2014 at 15:47
Sorry, pressed enter without shift and triggered a premature post — graemeboy
– graemeboy, Commented Oct 2, 2014 at 15:47
Have you tried putting any sort of trace statements (e.g. console.log() statements) in the code to see what's happening? — APerson
– APerson, Commented Oct 2, 2014 at 15:49
Yes, thanks, I actually figured it out by adding those checks and analyzing them. — graemeboy
– graemeboy, Commented Oct 2, 2014 at 16:05

graemeboy · Accepted Answer · 2014-10-02 16:04:52Z

1

Okay, I think I found it. The problem as just in my partition loop, I was ending it too early. Here is the complete code:

  function quicksort ( arr ) {
        // Launch the sorting process.
        sort(arr, 0, arr.length - 1 );

        /**
         * swap
         * takes in an array and two indicies,
         * swaps the elements in the array at those indicies
         */
        function swap ( arr, a, b ) {
            var temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

        function partition ( arr, l, r) {
            var p = arr[r],
                i = l - 1,
                j = l;
            while ( j < r) {
                if (arr[j] <= p) {
                    swap ( arr, ++i, j );
                }
                j++;
            }
            // Put the pivot in its correct place
            swap (arr, i + 1, r);
            return i + 1;
        }

        function sort ( arr, l, r ) {
            var p;
            if (l < r) {
                p = partition( arr, l, r );
                sort( arr, l, p - 1);
                sort( arr, p + 1, r);
            } else if (l === arr.length) {
                // Output the sorted array.
                console.log(arr);    
            }
        }
    }

Basic tests:

quicksort( [19,12,1,2,3,123,23,2,5] ) [ 1, 2, 2, 3, 5, 12, 19, 23, 123 ]

quicksort( [8,3,2,1,5,1,3] ) [ 1, 1, 2, 3, 3, 5, 8 ]

Open to suggestions on how to improve! :)

edited Oct 2, 2014 at 16:04

answered Oct 2, 2014 at 15:57

graemeboy

6205 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

BeyelerStudios Over a year ago

+1 very interesting partitioning: a tight bit more locality than the usual left and right bounds approach, I learned something today :D

Collectives™ on Stack Overflow

Quicksort in Javascript Bug

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related