Good morning, New York!

Good morning, fellow teens!

Sorting Out Sorting

EmpireJS 5/5/2014

Jenn Schiffer

College :(

College :)

Computer science
!=
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."

Let's talk about sort, bb!

Who in here is a JavaScript developer?

Some assumptions

"Understanding algorithms and their analysis is friggin hard!"
"Understanding algorithms and their analysis is friggin hard!"

-NYC Mayor Bill De Blasio probably

Some assumptions

Wanna hear a sorting joke?

When is 10 less than 7?

...in JavaScript!

lol JavaScript jokes amirite!

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

// [1, 10, 7]

¸,ø¤º°`°º¤ whyyy tho °º¤ø,¸¸,ø¤º°

¸,ø¤º°` bc it's lexicographical °º¤ø,¸¸,ø

We should probably rename sort() to sort_lexicographically() or sortLexicographically()

We should probably rename sort() to sort_lexicographically() or sortLexicographically()

js is basically php without all the question marks

We should probably rename sort() to sort_lexicographically() or sortLexicographically()

ARE YOU HAVING FUN YET?

What algorithm does Array.prototype.sort() use?

"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/

This is how we sort() integers

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

// [1, 7, 10]

How Array.prototype.sort() work

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]

How do we do descending sort?

This is how we do descending sort

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

// [10, 7, 1]

How many of you thought this wasn't going to be a serious talk?

Important characteristics of sorting

Stability

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

Imagine sorting this array by first letter only...

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

Stability

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

Stability

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

Runtime analysis

What's the deal with Big O?

 constantlogarithmiclinear quadraticcubic
nO(1)O(log N)O(N)O(N log N)O(N2)O(N3)
11 1 1 1 1 1
21 1 2 2 4 8
41 2 4 8 16 64
81 3 8 24 64 512
161 4 16 64 256 4,096
1,0241101,02410,2401,048,5761,073,741,824
1,048,5761201,048,57620,971,52010121016
source: http://www.leepoint.net/notes-java/algorithms/big-oh/bigoh.html

What's the deal with Big O?

http://bigocheatsheet.com/

Have I ruined your conference experience yet?

3 kinds of sorting algorithms we're going to implement today

For each algorithm, we will look at:

Some assumptions

Insertion sort

Insertion sort - pseudo code

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]

Insertion sort - pseudo example

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**

Insertion sort - runtime analysis

Insertion sort - JavaScript'd

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

Bubble sort

Bubble sort - pseudo

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]

Bubble sort - pseudo example

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

Bubble sort - JavaScript'd

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]

Bubble sort - runtime analysis

"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

Merge sort

Merge sort - pseudo

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++]

merge sort - pseudo example

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

Merge sort - runtime analysis

Merge sort - JavaScript'd

// 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]

Merge sort - JavaScript'd

// 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/

Intro to Sorting Final Exams cheatsheet

 O(n)ProsCons
InsertionO(n2)low resources needed, fast for nearly-sorted dataslow when data is reverse ordered
BubbleO(n2)easy to implement, cool nameslow as eff, not stable
MergeO(n log n)both fast stableneeds resources for temp space and arrays from recursive calls

Congrats, you now officially have a degree in Super Simple and Dirty Sorting Algorithmic Analysis™

shell • quicksort • cocktail • heapsort • shell • counting • comb • bucket • radix • shear • shuttle • lucky • etc.

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

How can we use this to increase our SEO?

YES.

Thank you!