Skip to content

Instantly share code, notes, and snippets.

@mbburch
Forked from stevekinney/gist:9e9cfeb225c8133fda73
Last active December 8, 2015 03:21
Show Gist options
  • Save mbburch/c75fdfbae6f8a4356030 to your computer and use it in GitHub Desktop.
Save mbburch/c75fdfbae6f8a4356030 to your computer and use it in GitHub Desktop.
Respond to this question in your fork: "What are some of the balances and trade offs between different sorting algoritms?"
Steve, did you make us watch this solely because they refer to "JerseyScript"??
- Lexicographical sort: if you just call sort on an array of numbers using js sort, (Array.prototype.sort), it doesn't sort by value but lexicographically. Computer doesn't know they are integers unless we tell it. Need to give (a, b) as args and return (a-b) for ascending sort.
-Important characteristics of sorting: stability, runtime analysis, implementation
-stable sort maintains relative order with items that are equal
-runtime analysis compares time and complexity of sorting algorithms. helps determine best sorting algorithm. Big O is worst case.
Insertion sort: downside is nested for loops in worst case O(n2). its okay for small data sets and info that is close to being sorted. It’s stable- items with equal values are relatively positioned. It’s easy to implement in JS.
Sorting algorithm visualizations…. whoa!!
Bubble sort: looks similar to insertion sort. downside… even if array is sorted, we still check through every item. it’s way more operations. Nested for loops. Not stable. Easy to implement, but not really useful. Can be twice as slow as insertion sort, even with less data. Also O(n2).
Merge sort: requires recursion. More lines of code. split the array in two and keep breaking it up to compare two smaller and smaller items. Really fast! Divide and conquer… multi-branched recursion. Fast and stable. Not going to recursively sort large amounts of data in the browser. Insertion sort might be better for that. O(n log n)
@biglovisa
Copy link

Nice work! 🗻

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment