No matter what sorting algorithm we are using, it’s more likely than not that we’ll need to rely on some swapping techniques, let’s explore a couple of in-place swapping helpers.
The memo swap technique relies on a variable to temporarily hold one of the two values that we want to swap.
Bitwise swap - Integers only
Bitwise operators can be used to solve different problems (it’s worth reading this paper by Martin Richards, where among others things he suggests an interesting algorithm based on bitwise operators to solve the n-queens problem). A more common usage is to swap integers in place using the bitwise operator XOR (exclusive OR).
Note: the bitwise swap method only works with integers
Swap in-place without memo
While the memo technique may look simple and to the point, sometime we just want to avoid creating an extra variable just to hold one of the values that we are going to swap. To solve this we can rely on swapping helpers that don’t need an extra variable to do their job.
If you wonder how the swapInPlaceWithoutMemo() function works:
the expression (list[iA] = list[iB]) does two things:
- it assigns to list[iA] the value stored at list[iB]
- returns the value stored at list[iB]
Swap in-place using Splice
We could also rely on the native splice method, to swap in place without need of a memo variable:
Destructuring swap - ES6 only
ES6, come with an awesome feature called destructuring assignment, that we can take advantage of for putting together an awesome in-place swapping helper function:
Note: the destructuring swap method only work with ES6, check compatibility or use an ES6 transpiler like babel that will compile the deconstructuring swap to a memo swap.
####Other ES6 related posts:
- ES6: JS’s Prototype-based inheritance and classes demystified
- ES6: Arrows, array-like objects and defaults
- Tail-recursive processes in JS