I asked the free version of ChatGPT to implement quicksort in JS. I can't really see much wrong...

keeda • today at 3:00 AM • 1 reply • view on HN

I asked the free version of ChatGPT to implement quicksort in JS. I can't really see much wrong with it, but maybe I'm missing something? (Ugh, I just can't get HN to format code right... pastebin here: https://pastebin.com/tjaibW1x)

----

function quickSortInPlace(arr, left = 0, right = arr.length - 1) { if (left < right) { const pivotIndex = partition(arr, left, right); quickSortInPlace(arr, left, pivotIndex - 1); quickSortInPlace(arr, pivotIndex + 1, right); } return arr; }

function partition(arr, left, right) { const pivot = arr[right]; let i = left;

  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }

  [arr[i], arr[right]] = [arr[right], arr[i]]; // Move pivot into place
  return i;
}

Replies

josephg • today at 3:51 AM

This is exactly the level of code I've come to expect from chatgpt. Its about the level of code I'd want from a smart CS student. But I'd hope to never use this in production:

- It always uses the last item as a pivot, which will give it pathological O(n^2) performance if the list is sorted. Passing an already sorted list to a sort function is a very common case. Good quicksort implementations will use a random pivot, or at least the middle pivot so re-sorting lists is fast.

- If you pass already sorted data, the recursive call to quickSortInPlace will take up stack space proportional to the size of the array. So if you pass a large sorted array, not only will the function take n^2 time, it might also generate a stack overflow and crash.

- This code: ... = [arr[j], arr[i]]; Creates an array and immediately destructures it. This is - or at least used to be - quite slow. I'd avoid doing that in the body of quicksort's inner loop.

- There's no way to pass a custom comparator, which is essential in real code.

I just tried in firefox:

    // Sort an array of 1 million sorted elements
    arr = Array(1e6).fill(0).map((_, i) => i)
    console.time('x')
    quickSortInPlace(arr)
    console.timeEnd('x')

My computer ran for about a minute then the javascript virtual machine crashed:

    Uncaught InternalError: too much recursion

This is about the quality of quicksort implementation I'd expect to see in a CS class, or in a random package in npm. If someone on my team committed this, I'd tell them to go rewrite it properly. (Or just use a standard library function - which wouldn't have these flaws.)

alt Hacker News

Replies