Created
October 20, 2016 16:44
-
-
Save YarGnawh/bca4fb8e92b83780abd58e02fc63fb63 to your computer and use it in GitHub Desktop.
Sorts in Javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Helper function to clone array | |
function cloneArray(arr) { | |
return arr.slice(); | |
} | |
// Helper function to generate random number array | |
function randomArray(min, max, len) { | |
// Set default values | |
min = min || 0; | |
max = max || 10; | |
len = len || 10; | |
// Create blank array | |
var arr = new Array(len); | |
// Set array values | |
for (var i=0; i<len; i++) { | |
arr[i] = min + Math.round(Math.random() * max); | |
} | |
return arr; | |
} | |
// Generate long random array | |
var data = randomArray(0, 10, 20000); | |
// Bubble Sort | |
var bubbleSortArr = cloneArray(data); | |
function bubbleSort(arr) { | |
// Declare variable to remember whether | |
// any swaps have been made | |
var swap; | |
do { | |
// Assume no swaps have been made in the beginning | |
swap = false; | |
// Loop through the items in the array | |
for (var i=0; i<arr.length-1; i++) { | |
// Check if the current item is greater than the next | |
if (arr[i] > arr[i+1]) { | |
// Swap the items if true | |
var temp = arr[i]; | |
arr[i] = arr[i+1]; | |
arr[i+1] = temp; | |
// Remember that a swap has been made | |
swap = true; | |
} | |
} | |
// If items swapped, check again | |
} while (swap); | |
} | |
console.time('BubbleSort'); | |
bubbleSort(bubbleSortArr); | |
console.timeEnd('BubbleSort'); | |
// Selection Sort | |
var selectionSortArr = cloneArray(data); | |
function selectionSort(arr){ | |
var len = arr.length, // Length of array | |
min; // Variable to remember the index of the smallest item | |
// Loop through all the items | |
for (var 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 (var j=i+1; j <len; j++){ | |
if (arr[j] < arr[min]){ | |
min = j; | |
} | |
} | |
// If the minimum isn't in the position, swap it | |
if (i != min){ | |
var temp = arr[i]; | |
arr[min] = arr[i]; | |
arr[i] = temp; | |
} | |
} | |
} | |
console.time('SelectionSort'); | |
bubbleSort(selectionSortArr); | |
console.timeEnd('SelectionSort'); | |
// Insertion Sort | |
var insertionSortArr = cloneArray(data); | |
function insertionSort(arr) { | |
var len = arr.length, // Number of items in the array | |
value, // The value currently being compared | |
i, // Index into unsorted section | |
j; // Index into sorted section | |
for (i=0; i < len; i++) { | |
// Store the current value because it may shift later | |
value = arr[i]; | |
// Whenever the value in the sorted section is greater than the value | |
// in the unsorted section, shift all items in the sorted section over | |
// by one. This creates space in which to insert the value. | |
for (j=i-1; j > -1 && arr[j] > value; j--) { | |
arr[j+1] = arr[j]; | |
} | |
arr[j+1] = value; | |
} | |
} | |
console.time('InsertionSort'); | |
insertionSort(insertionSortArr); | |
console.timeEnd('InsertionSort'); | |
// Shell Sort | |
function shellSort (arr) { | |
var len = arr.length; | |
for (var h = len; h = parseInt(h / 2);) { | |
for (var i = h; i < a.length; i++) { | |
var k = a[i]; | |
for (var j = i; j >= h && k < a[j - h]; j -= h) | |
a[j] = a[j - h]; | |
a[j] = k; | |
} | |
} | |
return a; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment