Implements selection, bubble, insertion, quick and heap sort algorythms in Array prototype

js-array-sort.js

/*

	(c) 2010~2013 Alessandro Ramos dos Santos
	[email protected]

	This file implements selection, bubble, insertion, quick and heap sort algorythms in Array prototype.
	It adds a swap() method for use with these algorythms.

	Hope you like it. :)
	Forgive my bad English. :(

	Usage:

	array.swap(p1, p2); // if you wish to swap p1 element with p2 element.

	array.selectionSort();
	array.bubbleSort();
	array.insertionSort();
	array.quickSort();
	array.heapSort();

*/

(function () {

	'use strict';

	// Prototypes

	// Swap the values in two positions of Array
	Array.prototype.swap = function (p1, p2) {

		var sw = this[p1];
		this[p1] = this[p2];
		this[p2] = sw;

	};

	// Sort Array using Selectin Sort algorythm
	Array.prototype.selectionSort = function () {

		var
			i, // Counter
			j, // Counter
			m; // Minimal occurrence

		for (i = 0; i < this.length - 1; i += 1) {

			m = i;

			for (j = i + 1; j < this.length; j += 1) {

				if (this[j] < this[m]) {

					m = j;

				}

			}

			this.swap(i, m);

		}

	};

	// Sort Array using Bubble Sort algorythm
	Array.prototype.bubbleSort = function () {

		var
			i, // Counter
			j; // Counter

		for (i = this.length; i >= 0; i -= 1) {

			for (j = 0; j < i; j += 1) {

				if (this[j] > this[j + 1]) {

					this.swap(j, j + 1);

				}

			}

		}

	};

	// Sort Array using Insertion Sort algorythm
	Array.prototype.insertionSort = function () {

		var
			i, // Counter
			j, // Counter
			a; // Reference value

		for (i = 1; i < this.length; i += 1) {

			a = this[i];

			for (j = i; j > 0 && a < this[j - 1]; j -= 1) {

				this[j] = this[j - 1];

			}

			this[j] = a;

		}

	};

	// Sort Array using Quick Sort algorythm
	Array.prototype.quickSort = function () {

		this.qsPartition = function (begin, end, pivot) {

			var
				piv = this[pivot], // Pivot
				store = begin, // New pivot
				ix; // Counter

			this.swap(pivot, end - 1);

			for (ix = begin; ix < end - 1; ix += 1) {

				if (this[ix + 1] <= piv) {

					this.swap(store, ix + 1);
					store += 1;

				}

			}

			this.swap(end - 1, store);

			return store;

		};

		this.qsSort = function (begin, end) {

			var
				pivot; // Pivot

			if (end - 1 > begin) {

				pivot = begin + Math.floor(Math.random() * (end - begin));
				pivot = this.qsPartition(begin, end, pivot);

				this.qsSort(begin, pivot);
				this.qsSort(pivot + 1, end);

			}

		};

		this.qsSort(0, this.length);

	};

	// Sort Array using Heap Sort algorythm
	// I didn't wrote this prototype myself, just based on the link below
	// Reference: http://tide4javascript.com/?s=Heapsort
	Array.prototype.heapSort = function () {

		this.hsHeapSize = 0; // Heap size, i think

		this.hsLeftChild = function (i) {

			return 2 * i + 1;

		};

		this.hsRightChild = function (i) {

			return 2 * i + 2;

		};

		this.hsMaxHeapify = function (i) {

			var
				largest,
				l = this.hsLeftChild(i), // Left child
				r = this.hsRightChild(i); // Right child

			if (l <= this.hsHeapSize && this[l] > this[i]) {

				largest = l;

			} else {

				largest = i;

			}

			if (r <= this.hsHeapSize && this[r] > this[largest]) {

				largest = r;

			}

			if (largest !== i) {

				this.swap(i, largest);
				this.hsMaxHeapify(largest);

			}

		};

		this.hsBuildMaxHeap = function () {

			this.hsHeapSize = this.length - 1;

			var
				i, // Counter
				mid = Math.floor(this.hsHeapSize / 2); // Middle of Heap

			for (i = mid; i >= 0; i -= 1) {

				this.hsMaxHeapify(i);

			}

		};

		this.hsSort = function () {

			this.hsBuildMaxHeap();

			var
				i; // Counter

			for (i = this.length - 1; i > 0; i -= 1) {

				this.swap(0, i);
				this.hsHeapSize -= 1;
				this.hsMaxHeapify(0);

			}

		};

		this.hsSort();

	};

}());