- twitter: @jennschiffer
- cool stuff: http://make8bitart.com
- engineer at Bocoup (bocoup.com, @bocoup)
- lives in new jersey

!=

web development

"An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output."

- some JavaScript
- some sorting algorithms
- some efficiency and complexities

- we are all JavaScript developers
- we only sort arrays of integers

"Understanding algorithms and their analysis is friggin hard!"

"Understanding algorithms and their analysis is friggin hard!"

-NYC Mayor Bill De Blasio probably

- we are all JavaScript developers
- we only sort arrays of integers
*+ it's like 9am*

```
myArray = [10, 7, 1];
myArray.sort();
// [1, 10, 7]
```

js is basically php without all the question marks

ARE YOU HAVING FUN YET?

"The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y."http://www.ecma-international.org/ecma-262/5.1/

```
myArray = [10, 7, 1];
myArray.sort( function(a,b){return a - b} );
// [1, 7, 10]
```

```
input = [7, 10, 1]
output = array.sort(function(a,b){ return a-b; })
// 1. (a,b) = (7, 10) -> 7-10 < 0
// 2. (a,b) = (10,1) -> 10-1 > 0
// 3. (a,b) = (7,1) -> 7-1 > 0
// output: [1, 7, 10]
```

```
myArray = [7, 10, 1];
myArray.sort( function(a,b){return b - a} );
// [10, 7, 1]
```

- stability
- runtime analysis
- the algorithm's implementation

Stable sorts maintain the relative order of items with equal "values"

Imagine sorting this array by first letter only...

`['alex', 'juan', 'jenn', 'adam']`

Stable sorts maintain the relative order of items with equal "values"

Imagine sorting this array by first letter only...

`['adam', 'alex', 'jenn', 'juan'] // not stable, but feels so good`

Stable sorts maintain the relative order of items with equal "values"

Imagine sorting this array by first letter only...

`['alex', 'adam', 'juan', 'jenn'] // actually stable`

- gives a variable to compare algorithms
- represents complexity in terms of time
- O(x) -> x is number of operations, function of n items
- Big-O, Big-Omega, Big-Theta
- not the be all and end all determinants of best sorting

constant | logarithmic | linear | quadratic | cubic | ||
---|---|---|---|---|---|---|

n | O(1) | O(log N) | O(N) | O(N log N) | O(N^{2}) | O(N^{3}) |

1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 | 1 | 1 | 2 | 2 | 4 | 8 |

4 | 1 | 2 | 4 | 8 | 16 | 64 |

8 | 1 | 3 | 8 | 24 | 64 | 512 |

16 | 1 | 4 | 16 | 64 | 256 | 4,096 |

1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |

1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 10^{12} | 10^{16} |

- insertion
- bubble
- merge

- pseudo code
- overly simple example
- implementation in JavaScript

- we are all JavaScript developers
- we only sort arrays of integers
- it's like 9am
*+ our pseudocode uses a zero-based index*

```
array x with n items
for i = 1:n-1,
for j = i; j > 0 and x[j] < x[j-1]; j--)
swap x[j,j-1]
```

```
x = [3, 2, 1]
i = 1
j = 1, and x[j] (2) < x[j=1] (3), so swap them
x == [2, 3, 1]
i = 2
j = 2, and x[j] (1) < x[j-1] (3), so swap them
x == [2, 1, 3]
j = 1, and x[j] (1) < x[j-1] (2), so swap them
x == [1, 2, 3]
**MIC DROP**
```

- nested for-loop, worst case is O(n
^{2}) - O(n) if array is nearly sorted, so it's good for small data sets (like in our example)
- bonus: stable

```
var insertionSort = function(x) {
for ( i = 1; i < x.length; i++ ) {
for ( j = i; j > 0 && x[j] < x[j-1]; j-- ) {
temp = x[j];
x[j] = x[j-1];
x[j-1] = temp;
}
}
return x;
}
insertionSort( [3, 2, 1] );
// output: [1, 2, 3]
```

source: http://g-than.square7.ch/programming/program.html

```
array x with n items
for i = 0:n-1,
for j = 0:n-2:,
if a[j] > a[j+1],
swap a[j,j+1]
```

```
x = [3, 2, 1]
i = 0
j = 0
x[j] (3) > x[j+1] (2), so swap them
x == [2, 3, 1]
j = 1
x[j] (3) > x[j+1] (1), so swap them
x == [2, 1, 3]
i = 1
j = 0
x[j] (2) > x[j+1] (1), so swap them
x == [1, 2, 3]
j = 1
x[j] (2) < x[j+1] (3), so do nothing
x == [1, 2, 3]
i = 2
j = 0
x[j] (1) < x[j+1] (2), so do nothing
x == [1, 2, 3]
j = 1
x[j] (2) < x[j+1] (3), so do nothing
x == [1, 2, 3]
HOW YOU GONNA ACT
```

```
var bubbleSort = function (arr){
for ( i = 0; i < arr.length; i++ ) {
for ( j = 0; j < arr.length - 1; j++ ) {
if ( arr[j] > arr[j+1] ) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
};
bubbleSort( [5, 4, 3, 2, 1] );
// output: [1, 2, 3, 4, 5]
```

- nested for-loop, worst-case O(n
^{2}) - not stable
- it's easy to implement, but otherwise just whatever

"the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems"

-papa Donald Knuth, "The Art of Programming"

source: http://g-than.square7.ch/programming/program.html

```
array x with n items
m = floor of n / 2
recursive sort x[0, ..., m-1]
recursive sort x[m, ..., n]
y = copy x[1, ..., m]
i = 0, j = m+1, k = 0
while i <= m and j <= n,
x[k++] = (x[j] < y[i]) ? y[j++] : y[i++]
while i <= m,
x[k++] = y[i++]
```

```
x = [3, 2, 1]
m = 1
sort [3]
(sorted, ready to merge)
sort [2, 1]
m = 1
sort [2]
(sorted, ready to merge)
sort [1]
(sorted, ready to merge)
merge -> [1, 2]
(sorted, ready to merge)
merge -> [1, 2, 3]
x == [1, 2, 3]
JERSEY IN THE HOUSE
```

- divide and conquer á la multi-branched recursion
- O(n log n)
- fast *and* stable

```
// part one: the division
var mergeSort = function(x) {
if ( x.length < 2 ) {
return x;
}
var m = Math.floor(x.length / 2);
var left = x.slice(0, m);
var right = x.slice(m);
return sortedArrayMerge(mergeSort(left), mergeSort(right));
}
mergeSort( [3, 2, 1] );
// output: [1, 2, 3]
```

```
// part two: the merging
var sortedArrayMerge = function(left, right) {
var mergedArray = [];
var indexLeft = 0;
var indexRight = 0;
while (indexLeft < left.length && indexRight < right.length){
if (left[indexLeft] < right[indexRight]){
mergedArray.push(left[indexLeft++]);
} else {
mergedArray.push(right[indexRight++]);
}
}
return mergedArray
.concat(left.slice(indexLeft))
.concat(right.slice(indexRight));
}
```

source: http://panthema.net/2013/sound-of-sorting/

O(n) | Pros | Cons | |
---|---|---|---|

Insertion | O(n^{2}) | low resources needed, fast for nearly-sorted data | slow when data is reverse ordered |

Bubble | O(n^{2}) | easy to implement, cool name | slow as eff, not stable |

Merge | O(n log n) | both fast stable | needs resources for temp space and arrays from recursive calls |

"Wait! You're forgetting the real important question that brought all of us here today!"

- @jennschiffer on twitter
- jenn@dotbiz.info
- say hi later, ok