# Computer science in JavaScript: Selection sort

Not too long ago, I wrote about the bubble sort algorithm, which is typically the starting point for sorting algorithm instruction. Bubble sort is a pretty inefficient algorithm with O(n^{2}) complexity and its algorithm calls for comparing each array item to its neighbor in order to “bubble” the smallest value to the top (front) of the array.

The selection sort algorithm, also with O(n^{2}) complexity, augments that algorithm slightly. Instead of comparing each array item to its neighbor, the goal is to locate the smallest remaining value and drop it into the correct place in the array. The basic algorithm looks like this:

- Assume the first item is the smallest value.
- Compare this item to the second item.
- If the second item is smaller than the first, set the second item as the new minimum.
- Continue until the end of the data set is reached.
- If the minimum value is not the item you started with, swap them.

This process is repeated by moving to the second item, then the third, etc. until the entire array has been sorted. To better illustrate the algorithm, consider an array `["b", "a", "d", "c", "e"]`

.

If this array were to be sorted into ascending order, the first step would be to set the minimum as index 0. Next, compare “b” to “a”. Since “a” comes before “b”, the minimum is set to index 1. The letter “a” is then compared to each item in the array, but since it is the smallest value, the minimum index remains at 1. Once this pass has been made, the minimum index of 1 is compared to the starting index of 0, and since they’re different, the values in these two positions are swapped, giving a result of `["a", "b", "d", "c", "e"]`

.

Next, the algorithm starts at the second position, “b”, and the minimum index is set to 1. The value is compared to each of the others and no change is made because “b” is already in the correct position. Since the starting index and the minimum index are both 1, no swap is made. The third pass starts at “d” and compares against “c”, changing the minimum to 3. At the end of the pass, 2 and 3 are swapped, resulting in `["a", "b", "c", "d", "e"]`

. The last two passes result in no swaps because everything is in the correct location. To make it clearer,Â check out this video for an example using playing cards.

The selection sort uses the same `swap()`

function as the bubble sort:

```
function swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
```

An implementation of selection sort is pretty easy. Similar to bubble sort, it uses two loops to accomplish the task (ultimately resulting in the O(n^{2}) complexity):

```
function selectionSort(items){
var len = items.length,
min;
for (i=0; i < len; i++){
//set minimum to this position
min = i;
//check the rest of the array to see if anything is smaller
for (j=i+1; j < len; j++){
if (items[j] < items[min]){
min = j;
}
}
//if the minimum isn't in the position, swap it
if (i != min){
swap(items, i, min);
}
}
return items;
}
```

The outer loop controls the starting point for each pass, beginning at the first item in the array and making its way towards the last item. The inner loop controls which items are being compared. After each pass, the items at the beginning of the array are already in their correct spots and so there is no need to re-evaluate them.

You can download the source code from my GitHub project, Computer Science in JavaScript.

As with bubble sort, selection sort isn’t something you’re likely to use in a real-world environment. This post is just a discussion of the algorithm for instructional purposes only. There is rarely a time when the built-in `Array.prototype.sort()`

method isn’t suitable, so always use that first.

Disclaimer: Any viewpoints and opinions expressed in this article are those of Nicholas C. Zakas and do not, in any way, reflect those of my employer, my colleagues, Wrox Publishing, O'Reilly Publishing, or anyone else. I speak only for myself, not for them.

Both comments and pings are currently closed.

## 4 Comments

yes,selection sort is rarely used ,Array.prototype.sort uses quick sort ,generally speaking ,quick sort is better than others.

yiminghe on September 8th, 2009 at 9:40 pm

Actually, it’s incorrect to say that Array.prototype.sort uses quicksort, as ECMA-262 does not define the sorting algorithm that should be used. Each JavaScript engine may be different. Mozilla traditionally has used a merge sort, which is stable whereas quicksort is not.

Nicholas C. Zakas on September 12th, 2009 at 12:22 am

Thanks for your time and that link , got it , recently i use chrome a lot and saw its sort implementation code once( the way is really easy ,just document.writeln(Array.prototype.sort) ), generally it uses quicksort ,so I think other browsers is the same way mistakenly .

Here is my understanding of chrome : chrome use quick sort for a large dataset ( >22) ,and for a smaller dataset (<=22) chrome use insert sort but modified to use binary search to find insert point ,so traditionally insert sort is stable ,but chrome make it faster and unstable , in conclusion chromeâ€™s sort is quick and unstable .

yiminghe on September 15th, 2009 at 10:36 pm

[...] åŽŸæ–‡(è‹±æ–‡): http://www.nczonline.net/blog/2009/09/08/computer-science-in-javascript-selection-sort/ [...]

æ•°ç»„æŽ’åºç®—æ³•ä¹‹é€‰æ‹©æŽ’åº - æ¼«æ¥ä¸çš„Tcer… on November 29th, 2009 at 3:50 am

Comments are automatically closed after 14 days.