Williammer
7/9/2014 - 8:37 AM

## sort algorithms: bubbleSort: bubble swap each adjacent item pair one step for each loop -> until length N-1 loop for worst case. |||

sort algorithms: bubbleSort: bubble swap each adjacent item pair one step for each loop -> until length N-1 loop for worst case. |||

selectionSort: find min item from first pos to the last. 外层为pos遍历，内层遍历pos后的元素，找到最小的与pos当前元素交换。|||

insertSort: 最外层n遍历，内层与之前所有元素比较，并和较大的交换。 |||

shellSort: A better way of insertSort, 最外层遍历所有gaps，次外层以gap遍历数组并比较交换各组元素。 |||

mergeSort: it works by merging sorted sublists together to form a larger, completely sorted list. 1.把数组递归地化作sorted子数组直到单元素；2.两组两组merge, 奇数组以空填充。 |||

quickSort: find a pivot number each time（从0开始），遍历数组元素并比较交换， and do the same for each subset. |||

``````function qSort(arr) {
if (arr.length == 0) {
return [];
}
var left = [];
var right = [];
var pivot = arr[0];
for (var i = 1; i < arr.length; i++) {

if (arr[i] < pivot) {

left.push(arr[i]);
} else {

right.push(arr[i]);
}
}
return qSort(left).concat(pivot, qSort(right));
}
var a = [];
for (var i = 0; i < 10; ++i) {
a[i] = Math.floor((Math.random() * 100) + 1);
}
print(a);
print();
print(qSort(a));``````
``````/******************************************************************************
*  Compilation:  javac Quick.java
*  Execution:    java Quick < input.txt
*  Dependencies: StdOut.java StdIn.java
*  Data files:   http://algs4.cs.princeton.edu/23quicksort/tiny.txt
*                http://algs4.cs.princeton.edu/23quicksort/words3.txt
*
*  Sorts a sequence of strings from standard input using quicksort.
*
*  % more tiny.txt
*  S O R T E X A M P L E
*
*  % java Quick < tiny.txt
*  A E E L M O P R S T X                 [ one string per line ]
*
*  % more words3.txt
*
*  % java Quick < words3.txt
*  all bad bed bug dad ... yes yet zoo    [ one string per line ]
*
*
*  Remark: For a type-safe version that uses static generics, see
*
*    http://algs4.cs.princeton.edu/23quicksort/QuickPedantic.java
*
******************************************************************************/

package edu.princeton.cs.algs4;

/**
*  The <tt>Quick</tt> class provides static methods for sorting an
*  array and selecting the ith smallest element in an array using quicksort.
*  <p>
*  For additional documentation, see <a href="http://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of
*  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
*  @author Robert Sedgewick
*  @author Kevin Wayne
*/
public class Quick {

// This class should not be instantiated.
private Quick() { }

/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
assert isSorted(a);
}

// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
assert isSorted(a, lo, hi);
}

// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {

// find item on lo to swap
while (less(a[++i], v))
if (i == hi) break;

// find item on hi to swap
while (less(v, a[--j]))
if (j == lo) break;      // redundant since a[lo] acts as sentinel

// check if pointers cross
if (i >= j) break;

exch(a, i, j);
}

// put partitioning item v at a[j]
exch(a, lo, j);

// now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}

/**
* Rearranges the array so that a[k] contains the kth smallest key;
* a[0] through a[k-1] are less than (or equal to) a[k]; and
* a[k+1] through a[N-1] are greater than (or equal to) a[k].
* @param a the array
* @param k find the kth smallest
*/
public static Comparable select(Comparable[] a, int k) {
if (k < 0 || k >= a.length) {
throw new IndexOutOfBoundsException("Selected element out of bounds");
}
StdRandom.shuffle(a);
int lo = 0, hi = a.length - 1;
while (hi > lo) {
int i = partition(a, lo, hi);
if      (i > k) hi = i - 1;
else if (i < k) lo = i + 1;
else return a[i];
}
return a[lo];
}

/***************************************************************************
*  Helper sorting functions.
***************************************************************************/

// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}

// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

/***************************************************************************
*  Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}

private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}

/**
* Reads in a sequence of strings from standard input; quicksorts them;
* and prints them to standard output in ascending order.
* Shuffles the array and then prints the strings again to
* standard output, but this time, using the select method.
*/
public static void main(String[] args) {
Quick.sort(a);
show(a);

// shuffle
StdRandom.shuffle(a);

// display results again using select
StdOut.println();
for (int i = 0; i < a.length; i++) {
String ith = (String) Quick.select(a, i);
StdOut.println(ith);
}
}

}

/******************************************************************************
*  Copyright 2002-2015, Robert Sedgewick and Kevin Wayne.
*
*  This file is part of algs4.jar, which accompanies the textbook
*
*      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
*      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
*      http://algs4.cs.princeton.edu
*
*
*  algs4.jar is free software: you can redistribute it and/or modify
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  algs4.jar is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with algs4.jar.  If not, see http://www.gnu.org/licenses.
******************************************************************************/
``````
``````// implemented with recursion.
function mergeSort(items) {
if (items.length == 1) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

// implemented with iteration.
function mergeSort(items) {
if (items.length == 1) {
return items;
}
var work = [];
for (var i = 0, len = items.length; i < len; i++) {
work.push([items[i]]);
}
work.push([]); //in case of odd number of items
for (var lim = len; lim > 1; lim = (lim + 1) / 2) {
for (var j = 0, k = 0; k < lim; j++, k += 2) {
work[j] = merge(work[k], work[k + 1]);
}
work[j] = []; //in case of odd number of items
}
return work[0];
}

//publicly shared function
function merge(left, right) {
var result = [];
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}

/****** "Bottom-Up Way"  from js algor book *********/
function mergeSort(arr) {
if (arr.length < 2) {
return;
}
var step = 1;
var left, right;
while (step < arr.length) {
left = 0;
right = step;
while (right + step <= arr.length) {
mergeArrays(arr, left, left + step, right, right + step);
left = right + step;
right = left + step;
}
if (right < arr.length) {
mergeArrays(arr, left, left + step, right, arr.length);
}
step *= 2;
}
}

function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
var rightArr = new Array(stopRight - startRight + 1);
var leftArr = new Array(stopLeft - startLeft + 1);
k = startRight;
for (var i = 0; i < (rightArr.length - 1); ++i) {
rightArr[i] = arr[k];
++k;
}

k = startLeft;
for (var i = 0; i < (leftArr.length - 1); ++i) {
leftArr[i] = arr[k];
++k;
}

rightArr[rightArr.length - 1] = Infinity; // a sentinel value
leftArr[leftArr.length - 1] = Infinity; // a sentinel value
var m = 0;
var n = 0;
for (var k = startLeft; k < stopRight; ++k) {
if (leftArr[m] <= rightArr[n]) {
arr[k] = leftArr[m];
m++;
} else {
arr[k] = rightArr[n];
n++;
}
}
print("left array - ", leftArr);
print("right array - ", rightArr);
}

var nums = [6, 10, 1, 9, 4, 8, 2, 7, 3, 5];
print(nums);
print();
mergeSort(nums);
print();
print(nums);``````
``````/******************************************************************************
*  Compilation:  javac Merge.java
*  Execution:    java Merge < input.txt
*  Dependencies: StdOut.java StdIn.java
*  Data files:   http://algs4.cs.princeton.edu/22mergesort/tiny.txt
*                http://algs4.cs.princeton.edu/22mergesort/words3.txt
*
*  Sorts a sequence of strings from standard input using mergesort.
*
*  % more tiny.txt
*  S O R T E X A M P L E
*
*  % java Merge < tiny.txt
*  A E E L M O P R S T X                 [ one string per line ]
*
*  % more words3.txt
*
*  % java Merge < words3.txt
*  all bad bed bug dad ... yes yet zoo    [ one string per line ]
*
******************************************************************************/

package edu.princeton.cs.algs4;

/**
*  The <tt>Merge</tt> class provides static methods for sorting an
*  array using mergesort.
*  <p>
*  For additional documentation, see <a href="http://algs4.cs.princeton.edu/22mergesort">Section 2.2</a> of
*  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*  For an optimized version, see {@link MergeX}.
*
*  @author Robert Sedgewick
*  @author Kevin Wayne
*/
public class Merge {

// This class should not be instantiated.
private Merge() { }

// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
assert isSorted(a, lo, mid);
assert isSorted(a, mid+1, hi);

// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}

// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if      (i > mid)              a[k] = aux[j++];
else if (j > hi)               a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else                           a[k] = aux[i++];
}

// postcondition: a[lo .. hi] is sorted
assert isSorted(a, lo, hi);
}

// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}

/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
assert isSorted(a);
}

/***************************************************************************
*  Helper sorting functions.
***************************************************************************/

// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}

// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

/***************************************************************************
*  Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}

private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

/***************************************************************************
*  Index mergesort.
***************************************************************************/
// stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {

// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = index[k];
}

// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if      (i > mid)                    index[k] = aux[j++];
else if (j > hi)                     index[k] = aux[i++];
else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
else                                 index[k] = aux[i++];
}
}

/**
* Returns a permutation that gives the elements in the array in ascending order.
* @param a the array
* @return a permutation <tt>p[]</tt> such that <tt>a[p[0]]</tt>, <tt>a[p[1]]</tt>,
*    ..., <tt>a[p[N-1]]</tt> are in ascending order
*/
public static int[] indexSort(Comparable[] a) {
int N = a.length;
int[] index = new int[N];
for (int i = 0; i < N; i++)
index[i] = i;

int[] aux = new int[N];
sort(a, index, aux, 0, N-1);
return index;
}

// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, index, aux, lo, mid);
sort(a, index, aux, mid + 1, hi);
merge(a, index, aux, lo, mid, hi);
}

// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}

/**
* Reads in a sequence of strings from standard input; mergesorts them;
* and prints them to standard output in ascending order.
*/
public static void main(String[] args) {
Merge.sort(a);
show(a);
}
}

/******************************************************************************
*  Copyright 2002-2015, Robert Sedgewick and Kevin Wayne.
*
*  This file is part of algs4.jar, which accompanies the textbook
*
*      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
*      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
*      http://algs4.cs.princeton.edu
*
*
*  algs4.jar is free software: you can redistribute it and/or modify
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  algs4.jar is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with algs4.jar.  If not, see http://www.gnu.org/licenses.
******************************************************************************/
``````
``````/******************************************************************************
*  Compilation:  javac MergeBU.java
*  Execution:    java MergeBU < input.txt
*  Dependencies: StdOut.java StdIn.java
*  Data files:   http://algs4.cs.princeton.edu/22mergesort/tiny.txt
*                http://algs4.cs.princeton.edu/22mergesort/words3.txt
*
*  Sorts a sequence of strings from standard input using
*  bottom-up mergesort.
*
*  % more tiny.txt
*  S O R T E X A M P L E
*
*  % java MergeBU < tiny.txt
*  A E E L M O P R S T X                 [ one string per line ]
*
*  % more words3.txt
*
*  % java MergeBU < words3.txt
*  all bad bed bug dad ... yes yet zoo    [ one string per line ]
*
******************************************************************************/

package edu.princeton.cs.algs4;

/**
*  The <tt>MergeBU</tt> class provides static methods for sorting an
*  array using bottom-up mergesort.
*  <p>
*  For additional documentation, see <a href="http://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of
*  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
*  @author Robert Sedgewick
*  @author Kevin Wayne
*/
public class MergeBU {

// This class should not be instantiated.
private MergeBU() { }

// stably merge a[lo..mid] with a[mid+1..hi] using aux[lo..hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}

// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if      (i > mid)              a[k] = aux[j++];  // this copying is unneccessary
else if (j > hi)               a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else                           a[k] = aux[i++];
}

}

/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
for (int n = 1; n < N; n = n+n) {
for (int i = 0; i < N-n; i += n+n) {
int lo = i;
int m  = i+n-1;
int hi = Math.min(i+n+n-1, N-1);
merge(a, aux, lo, m, hi);
}
}
assert isSorted(a);
}

/***********************************************************************
*  Helper sorting functions.
***************************************************************************/

// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}

// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

/***************************************************************************
*  Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}

/**
* Reads in a sequence of strings from standard input; bottom-up
* mergesorts them; and prints them to standard output in ascending order.
*/
public static void main(String[] args) {
MergeBU.sort(a);
show(a);
}
}

/******************************************************************************
*  Copyright 2002-2015, Robert Sedgewick and Kevin Wayne.
*
*  This file is part of algs4.jar, which accompanies the textbook
*
*      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
*      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
*      http://algs4.cs.princeton.edu
*
*
*  algs4.jar is free software: you can redistribute it and/or modify
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  algs4.jar is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with algs4.jar.  If not, see http://www.gnu.org/licenses.
******************************************************************************/
``````
``````function shellsort() {
for (var g = 0; g < this.gaps.length; ++g) {
for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
var temp = this.dataStore[i];
for (var j = i; j >= this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp; j -= this.gaps[g]) {
this.dataStore[j] = this.dataStore[j - this.gaps[g]];
}
this.dataStore[j] = temp;
}
}
}

function shellsort1() {
var N = this.dataStore.length;
var h = 1;
while (h < N / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (var i = h; i < N; i++) {
for (var j = i; j >= h && this.dataStore[j] < this.dataStore[j - h]; j -= h) {
swap(this.dataStore, j, j - h);
}
}
h = (h - 1) / 3;
}
}``````
``````/******************************************************************************
*  Compilation:  javac Shell.java
*  Execution:    java Shell < input.txt
*  Dependencies: StdOut.java StdIn.java
*  Data files:   http://algs4.cs.princeton.edu/21sort/tiny.txt
*                http://algs4.cs.princeton.edu/21sort/words3.txt
*
*  Sorts a sequence of strings from standard input using shellsort.
*
*  Uses increment sequence proposed by Sedgewick and Incerpi.
*  The nth element of the sequence is the smallest integer >= 2.5^n
*  that is relatively prime to all previous terms in the sequence.
*  For example, incs[4] is 41 because 2.5^4 = 39.0625 and 41 is
*  the next integer that is relatively prime to 3, 7, and 16.
*
*  % more tiny.txt
*  S O R T E X A M P L E
*
*  % java Shell < tiny.txt
*  A E E L M O P R S T X                 [ one string per line ]
*
*  % more words3.txt
*
*  % java Shell < words3.txt
*  all bad bed bug dad ... yes yet zoo    [ one string per line ]
*
*
******************************************************************************/

package edu.princeton.cs.algs4;

/**
*  The <tt>Shell</tt> class provides static methods for sorting an
*  array using Shellsort with Knuth's increment sequence (1, 4, 13, 40, ...).
*  <p>
*  For additional documentation, see <a href="http://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of
*  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
*  @author Robert Sedgewick
*  @author Kevin Wayne
*/
public class Shell {

// This class should not be instantiated.
private Shell() { }

/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
int N = a.length;

// 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ...
int h = 1;
while (h < N/3) h = 3*h + 1;

while (h >= 1) {
// h-sort the array
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
exch(a, j, j-h);
}
}
assert isHsorted(a, h);
h /= 3;
}
assert isSorted(a);
}

/***************************************************************************
*  Helper sorting functions.
***************************************************************************/

// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}

// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

/***************************************************************************
*  Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

// is the array h-sorted?
private static boolean isHsorted(Comparable[] a, int h) {
for (int i = h; i < a.length; i++)
if (less(a[i], a[i-h])) return false;
return true;
}

// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}

/**
* Reads in a sequence of strings from standard input; Shellsorts them;
* and prints them to standard output in ascending order.
*/
public static void main(String[] args) {
Shell.sort(a);
show(a);
}

}

/******************************************************************************
*  Copyright 2002-2015, Robert Sedgewick and Kevin Wayne.
*
*  This file is part of algs4.jar, which accompanies the textbook
*
*      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
*      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
*      http://algs4.cs.princeton.edu
*
*
*  algs4.jar is free software: you can redistribute it and/or modify
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  algs4.jar is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with algs4.jar.  If not, see http://www.gnu.org/licenses.
******************************************************************************/
``````
``````function insertionsort(dataStore) {
var temp, inner;
for (var outer = 1; outer <= dataStore.length - 1; ++outer) {
temp = dataStore[outer];
inner = outer;
while (inner > 0 && (dataStore[inner - 1] >= temp)) {
console.log("while - outer: " + outer + " || inner:" + inner + " | dataStore[inner]:" + dataStore[inner] + " | dataStore[inner-1]:" + dataStore[inner - 1] + " | temp: " + temp);
dataStore[inner] = dataStore[inner - 1];
--inner;
console.log("while then - inner:" + inner + " | dataStore:", dataStore);
}
dataStore[inner] = temp;
console.log("while after - temp: " + temp + "| inner:" + inner + " | dataStore:", dataStore);
}
}

var arr = [6, 1, 0, 0, 6, 5, 8, 7, 4, 2, 7];

insertionsort(arr);``````
``````function selectionsort() {
var min, temp;
for (var outer = 0; outer <= this.dataStore.length - 2; ++outer) {
min = outer;
for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
if (this.dataStore[inner] < this.dataStore[min]) {
min = inner;
}
}
temp = this.dataStore[outer];
this.dataStore[outer] = this.dataStore[min];
this.dataStore[min] = temp;
}
}``````
``````function bubblesort() {
var numElements = this.dataStore.length;
var temp;
for (var outer = numElements; outer >= 2; --outer) {
for (var inner = 0; inner <= outer - 1; ++inner) {
if (this.dataStore[inner] > this.dataStore[inner + 1]) {
temp = this.dataStore[inner];
this.dataStore[inner] = this.dataStore[inner + 1];
this.dataStore[inner + 1] = temp;
}
}
}
}``````