Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Computer Science Algorithms: Sorting and Searching Sorting Algorithms Big-O Run Times of Sorting Algorithms

Andrew Whatmore
seal-mask
.a{fill-rule:evenodd;}techdegree
Andrew Whatmore
Full Stack JavaScript Techdegree Student 13,175 Points
Posted by Andrew Whatmore
.a{fill-rule:evenodd;}techdegree
Andrew Whatmore
Full Stack JavaScript Techdegree Student 13,175 Points

JavaScript Quick Sort with random pivot

The video explains that using a random pivot is more likely to lead to the average case of time efficiency for quick sort, rather than using the first item as the pivot.

So I have amended the included JavaScript code to use a random pivot instead of the first array item - I'm pretty sure this is correct, though anyone can correct me if not. Thanks

// pass in the array of values
function quicksort(values) {
    // BASE CASE
    // If the list passed in is 1 or 0, return the (sorted) list
    if (values.length <= 1) {
        return values;
    }

    // RECURSIVE CASE
    // variables for sublists and pivot
    var lessThanPivot = [];
    var greaterThanPivot = [];
    // get a random pivot between index 0 and the maximum of the array
    var random = Math.floor(Math.random() * values.length)
    var pivot = values[random];
    // remove the pivot from the array, as this will be added back as 'pivot'
    values.splice(random, 1);
    // Loop through this sublist, and sort into the two sublists
    // Start i at 1, because 0 is the pivot
    for (var i = 0; i < values.length; i++) {
        if (values[i] <= pivot) {
            lessThanPivot.push(values[i]);
        } else {
            greaterThanPivot.push(values[i]);
        }
    }
    // recursive calls on the new lists - also join (concat) the less than, pivot ...
    // ... and greater lists to each other.
    return quicksort(lessThanPivot).concat(pivot, quicksort(greaterThanPivot));
}

const testValues = [32, 100, 1, 2, 29, 28, 88, 3, 50, 67, 37, 1, 57, 20];

var sorted = quicksort(testValues);
console.log('Final list: ', sorted);