DEV Community: Javid Asgarov

QuickSort Algorithm

Javid Asgarov — Fri, 01 Mar 2019 19:40:50 +0000

Quick Intro. I am in the process of studying algorithms and data structures myself. I write this to understand it a little better myself and with hope it might help somebody else. If something is to be improved, or not correct, please share.

The quicksort algorithm is the one I didn't get right away and had to spent a little more time on it to understand every moving piece. This probably happens with a lot of algorithms that involve recursion. So, here we go.

Overview

This is one of those algorithms that uses "Divide and conquer" technique. The point here is, that we solve this problem constantly dividing our input until it's solved fully.

This is also an "in place" algorithm, meaning that we move elements in the array, mutating the array, and we're not creating any new arrays to hold sorted values, and don't use any extra space for elements.

The whole idea revolves around the pivot element. This is the first step. Pick a pivot. It can be the first element, or the last one, or something in the middle. Doesn't really matter, but I'm going to be using the first one in the examples.

Now, that the pivot is picked. The next part is to place everything less than the pivot to the left of the pivot, and anything bigger to the right. This part also is called partition.

This means, that the element you picked first, your pivot, moves around, swaps places with elements bigger and smaller than itself, until it finds it's place in the array.

And then you call the function again for the part of the array that's to the right of the pivot, and to the left.
For this reason you should also keep track of the pivot index.

To recap, let's look at it step by step:

Declare a function, that accepts 3 arguments: array, starting index, ending index
Pick a pivot point
Keep track of the left and right indices. We will go to our pivot either from left to right, or from right to left. For this reason, we need to know, where we stand. Start by assigning left to starting index, right to ending index (I mean the start and end arguments passed into the function).
Now the partition process, which will continue while left index is less than the right one.
If a value you're looking at right index is less than pivot, it means it's in the wrong place. Swap them and update the pivot index.
Else if value at the left index is more than the value at the pivot index, swap them. Update the pivot index.
In this partition process keep track whether to move the right pointer further to the left, or the left pointer to the right. It's pretty simple, if the right index is more than the pivot, then decrement it. If the left one is less than the pivot, then increment that one. This works in my implementation, where the pivotIndex is the first element.
Do this until left index is smaller than the right index.
Now the recursive part. Call that function twice for the part of the array right of the right index, and for the part of the array left of the left index.

Code

function swap(arr, left, right) {
  let temp = arr[left];
  arr[left] = arr[right];
  arr[right] = temp;
}

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (arr.length <= 1 || high < 0 || low >= high) {
    return arr;
  }
  let pivotIndex = low;
  let left = low;
  let right = high;
  while (left < right) {
    if (arr[right] < arr[pivotIndex]) {
      swap(arr, pivotIndex, right);
      pivotIndex = right;
    } else if (arr[left] > arr[pivotIndex]) {
      swap(arr, pivotIndex, left);
      pivotIndex = left;
    }
    if (right > pivotIndex) {
      right--;
    } else if (left < pivotIndex) {
      left++;
    }
  }
  if (low < high) {
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

Other resources

Hungarian Folk Dance QuickSort

I've also made a video, if you prefer this format

React Testing Cases

Javid Asgarov — Sun, 17 Jun 2018 19:59:09 +0000

UPDATE: When I was writing this, I was using the 3.1.3 version of the library I think, now I've updated and some things have changed. I have revised the article, if I missed something tell me in the comments.
If you're using the actual version, above 5, then here are some changes to these snippets:

No renderIntoDocument. Use render method
No need to change the values first, and then use fireEvent. Use it like this:


    fireEvent(component.getByLabelText("Some label"), {target: { value: "20"}});

You dont check checkboxes with .change on fireEvent, use .click.

I think I've got them all.

Disclaimer: I am describing some use cases, I would consider myself useful. I hope this post helps somebody, and if not, maybe it will help myself when I forget something.

What I use to test react is: Jest and react-testing-library for unit tests and cypress for integration (or end to end, I'm not sure how should I call these). I'm not going to talk about cypress here, though.

localStorage is not defined

One of the first problems I stumbled upon was that localstorage is not defined, when you run tests.
And that was when I got to know about mocks. Basically, you can substitute (mock) some code if you don't really need to test it, at least not in this test case.
In this instance, browser APIs like localstorage are not defined in your testing environment, and you can mock it the following way:

    //browserMocks.js
    var localStorageMock = (function() {
        var store = {};

        return {
            getItem: function(key) {
                return store[key] || null;
            },
            setItem: function(key, value) {
                store[key] = value.toString();
            },
            clear: function() {
                store = {};
            }
        };

    })();
    Object.defineProperty(window, 'localStorage', {
        value: localStorageMock
    });

After that you're going to need to tell jest to use this file in your testing environment. For that, open your package.json file and edit it according to the following snippet:

"jest": {
"setupFiles": [
      "./some_path/browserMocks.js",
    ]
}

Mocking with Jest

Like in the example above, you sometimes have to mock some of your code. It either slows down the testing, because it makes API calls, or it's too hard to set up, it gives errors, whatever. You can isolate your test and mock everything non-essential to it. You can do it like this:


    jest.mock("../path/module", () => {
        return jest.fn();
    });

More Mocking

One time I needed to mock only one method on a class. I didn't want to substitute a whole class with a mock like presented above. I could've written a mock class for it, and define methods there, and tell jest to use that, but that seemed like too much work.

What I did was the following:

ClassName.prototype.method= jest.fn()

Thanks to the user under nickname WickyNilliams from stackoverflow. You can checkout his more detailed answer here

Testing something is in the DOM or not

React-testing-library gives you two methods for accesing rendered elements, one starts with queryBy and the other with getBy. There are a few of those methods, like getByTestId or queryByTestId.

You can read more about it in the readme of the library, which methods you need particularly. But the difference between getting an element with a method that starts with queryBy is that it can be null and getBy always should return an element or it will throw an error.

So, if you want to test that something is not in the DOM, you can do the following:

  const component = renderIntoDocument(<Component />);
  expect(component.queryByTestId("testid-of-element")).toBeNull();

But, what if you want to test that something is in the DOM. For that you need to install jest-dom/extend-expect, and then you can do this:

  const component = renderIntoDocument(<Component />);
  expect(component.queryByTestId("row-34")).toBeInTheDOM();

Test that some element has a certain class

    const component = renderIntoDocument(<Component />);
    expect(component.getByTestId("testid-element")
            .classList.contains("class-name")).toBe(true);

Of course you can pass false and test that it doesn't have some class.

You don't have testids

Suppose, you don't have testids for these elements within rendered component, and you want to test something.


    const component = renderIntoDocument(<Component />);
    const elements = component.container.getElementsByClassName("class-name");

There are other ways to access elements, exposed by react-testing-library. Like getByLabelText and a few others, you can see here. But sometimes none of them apply, so I use classes like I presented above. But, it's probably not a good idea, or at least not a best practice. Because someone can rename that class, or remove it, and your tests will fail. I just thought, I should mention that there are other ways. You can also use getElementsByTagName.

Events

From react-testing-library you can import fireEvent and trigger some events for react to handle. This is really useful, because a lot of times I need to test the state of the component after something happened. Triggering the click is pretty easy, but the others are a bit tricky. Well, at least for me, I spent some time trying to figure out how to trigger the change in some cases.

    const component = renderIntoDocument(<Component />);
    fireEvent.click(component.getByTestId('testid-element'));

The interesting thing is, that if you want to trigger onChange handler, you have to make the change first in your testing code and then trigger onchange. Like, let's say you have an input and want to test it's onChange handler:

    const component = renderIntoDocument(<Component />); 
    component.getByTestId("input").value = "20";
    fireEvent.change(component.getByTestId("input"), {});

If you want to test a checkbox, there is a thing I stumbled upon. You can trigger onchange like this:

        const component = renderIntoDocument(<Component />);
        component.getByLabelText("Label Text").setAttribute("checked", "");
        fireEvent.change(component.getByLabelText("Label Text"));

But, this method didn't work for me, when my input had defaultChecked property.
What did work in that situation for me is this:

        const component = renderIntoDocument(<Component />);
        component.getByLabelText("Label Text").checked = true;
        fireEvent.change(component.getByLabelText("Label Text"));

I have no idea why this happens, I would probably go with the last one every time for safety.

Timers

In case something in your code should happen after a number of seconds, for example, you're using setTimeout method, you can use fake timers and just see the result. For that, use jest's method:

        jest.useFakeTimers();

After you've executed this method, you can use it in your tests:


        jest.runAllTimers();

Unmount components in tests

I used renderIntoDocument in the examples, if you're going to use this method, don't forget to clean up with unmount method.

        const component = renderIntoDocument(<Component />);
        /// testing
        component.unmount();