WIP: Javascript sorting!

I’m choosing to kick off learning sorting and data algorithms with these lectures . They cost: $10.

I’m estimating a 10 day effort (9 for each type of sorting, 1 day for reflection and additional practice).

I’m expecting to: – Crash course sorting sorting algorithms – Develop initial opinions re: what data patterns fit each type of algo, performance of each algo assuming certain conditions.

What do I think makes a ‘GOOD’ sorting algorithm? I’d guess this comes down to: – Time (to process) – Space (memory)

Recursion – Roughly, when a function calls itself. Here’s what this looks like in code

The sorting algorithms – Selection Sort – Bubble Sort – Merge Sort – Quick Sort

Selection sort Inner monologue: – Take an array. – Divide the array into “sorted” and “unsorted” parts. Initially, the “sorted” part is empty. – Take the first number in the array. – Compare first number to each of the numbers in the array. Once you reach a number smaller than the number you have (What about even-to?) then select that number. Continue right until you reach the end of the array. Using this method, you’ll result in finding the smallest number in the array. – Append this number to the sorted part. – Select the, now, first number in the unsorted range. – Compare this number in a similar fashion, ultimately ending in the smallest number in the unsorted part. Append this ot the sorted part. – Repeat this process until there is only one element in the unsorted part. – The remaining unsorted part is your largest number in the array, and can be appended to the sorted array.

Here’s what this looks like in code

Is this fast? Time dependent on length of array.

Is this memory intensive? Guessing looped nature allows for memory to be thrown out when the loop finishes, thereby allowing for low memory creation and life span. Verify.

This seems to be good for? – Numbers – What about other data types?

What makes this algorithm appealing to use? – Easy to implement

What makes this algorithm unappealing to use? – Limited in function by weakly typed javascript’s comparison operator conversions of non-numeric values. Explain more.

Bubble Sort Inner monologue: – Start on first item. – Is item bigger than next item? Swap. Continue that item’s swapping with the subsequent items until that item isn’t bigger than its compared item. – Perform the same operation for the next item at the start of the array. – Eventually, the largest items will float to the right, in order.

Here’s what this looks like in code

Is this fast? Time dependent on length of array. Feels similar in nature to selection sort.

Is this memory intensive? Same as selection sort. Guessing looped nature allows for memory to be thrown out when the loop finishes, thereby allowing for low memory creation and life span. Verify.

This seems to be good for? – Numbers – What about other data types?

What makes this algorithm appealing to use? – Easy to implement

What makes this algorithm unappealing to use? – Limited in function by weakly typed javascript’s comparison operator conversions of non-numeric values. Explain more.

Merge Sort – TBDocumented!

Quick Sort – TBDocumented!

Time Complexity Factors that change completion time: – Device run on – Input size

Use functions: – Length of input -> Number of operations

sorting.gif

Random finds – MDN suggested this mapsort library for . – Object.isExtensible and Object.preventExtension/Object.freeze (! like freezing an object in Ruby!) to create immutability of object children.

Tangental Questions – I wonder what javascript’s array sort function is based off of?

  • Here’s the ECMA sort spec .
  • Array.prototype.sort defines the return value of the compareFunction must be -1 or 1. I’m assuming this will allow the sort function to perform a selection sort. This needs to be validated, though.

– What is a bitwise operator (scroll down) ?

  • To be documented

– What’s a good method to A/B test algorithms to track run time of each algo? Here’s what this looks like in code

No Comments Yet