Let's understand QuickSort the easy way

#typescript #javascript

Hello devs,

This is my first post on dev.to (any edit suggestions welcomed) but since everyone wants to skip to the material right away so let's get to it.

QuickSort

I'm gonna be doing everything with TypeScript but you could change this to whatever you'd like.

Let's assume you have an array of numbers

const items: number[] = [1, 4, 2, 8, 6];

And you'd like to sort them, the obvious way is to do items.sort() and it just works. There's really no need for you to do the sorting yourself, almost all languages include sorting and I think they are more optimized than what we would implement.

But for the sake of argument let's say you're in an interview and interviewer asks you to write quick sort.

Adding requirements:

First let's get requirements out of the way, what's better than to just write some test cases:

describe("sort", () => {
  it("should be able to sort empty array", () => {
    expect(sort([])).toStrictEqual([]);
  });
  it("should be able to sort array with just 1 item", () => {
    expect(sort([5])).toStrictEqual([5]);
  });
  it("should be able to sort array with multiple items", () => {
    expect(sort([1, 4, 2, 8, 6])).toStrictEqual([1, 2, 4, 6, 8]);
  });
});

The way QuickSort works is by selecting a pivot element (any element, generally we pick the first one because of simplicity), and putting smaller items than the pivot to the left and larger items to the right, and this is done for each parts.

Let's do a QuickSort manually:

const items: number[] = [1, 4, 2, 8, 6];
// pivot = 1
// there are no smaller items,
// [1, 4, 2, 8, 6]
// let's do second pass for the rest of elements
// pivot = 4
// smaller = 2
// larger = 8, 6
// arranging: [1, 2, 4, 8, 6]
// another pass:
// pivot = 8
// smaller = 6
// there's no larger element
// final sorted array: [1, 2, 4, 6, 8]

Did you notice a pattern there? It's simple, take a pivot, get items lesser items than pivot from rest of items, take remaining items which are larger, and put them together and repeat.

Let's write some pseudo code:

pivot = first element, rest = rest of elements
smallerItems = elements in rest lesser than pivot
largerItems = remaining items in rest
sort(smallerItems), pivot, sort(largerItems)

Let's write a function that does just that,

const sort = (items: number[]): number[] => {
  const [pivot, ...rest] = items;
  const smaller = rest.filter(x => x < pivot);
  const larger = rest.filter(x => x >= pivot);
  return [...sort(smaller), pivot, ...sort(larger)];
};

This is a recursive function and will never return, we're missing a exit condition, which should return same items if array has less than or equal to 1 items if (items.length <= 1)return items; Now our final function becomes:

const sort = (items: number[]): number[] => {
  if (items.length <= 1) {
    return items;
  }
  const [pivot, ...rest] = items;
  const smaller = rest.filter(x => x < pivot);
  const larger = rest.filter(x => x >= pivot);
  return [...sort(smaller), pivot, ...sort(larger)];
};

Let's do a quick check if this is actually working, to do that, I'll go to typescript playground and copy and run the code on browser, and it works:

Obviously this isn't how you'd write any code if you were doing a pair programming, you'd want to do some level of TDD with feedback, since that can't be done on a dev.to post, so here's a video, but before you watch there's something I'd like to make clear:

On video when I'm adding first test which says for empty arrays and second test which checks for arrays with 1 items, I already added if condition on code, which is wrong, I should have simply returned the items, and on next iteration I should have added if condition, I kinda cheated on TDD, please overlook that

I hope this was a nice read, please give feedback in comments, also let me know if you have seen more readable quicksort.

Top comments (3)

Arswaw • Dec 10 '19

Amazing implementation! I was just thinking about how I would write quicksort in JavaScript and I wouldn't have thought about using the spread and comparison operators that way!

Thank you for the article.