MOD 7 - sorting - implemented in forked linklist code

by SHELDON PASCIAK

HTML

<p id='output'></p>
<input type="text" id="newItem" placeholdere="New Value" />
<input type="button" id="addItem" value="Add" />
<input type="button" id="bubbleSort" value="bubble sort" />

<!--

Module 7 - Sorting Part 1
 
Introduction
 
Here is your practical application of data structures; sorting. There are literally hundreds of sorting algorithms and Topic - Sorting Techniques covers most of the important ones. Sorting is also tied very closely to searching, as it is much easier to search a sorted list. 

We are going to return to your Chain and Links code from Module 3 - Lists . You will need to fork your JSFiddle into a new Fiddle. In this Fiddle we are going to add a Chain function -  Sort(). I would like you to add 2 sort functions, you can use any sort method that you desire for each of the sort functions. You can also delineate the functions by the name of the Sort function - so your functions might be QuickSort() and MergeSort() - if you chose to implement those 2 algorithms.
 
Once the Chain is sorted - we want to keep it sorted. You have a couple of ways to do that; (1) insert elements into the correct location in the Chain based on sort order or (2) re-sort the chain after every insertion. If you choose (2) you will need to pick an algorithm that is highly efficient for a pre-sorted array with one item out of place (look at all the algorithms - it is there).
 
You will now need an interface to add Links to your chain. Just create either a text box and a button or a button and any type of input. I should be able to add elements to your chain and see the new chain output each time I add an element.

-->

JavaScript

/*      Module 7 - SORTING - SHELDON PASCIAK - VERSION 1 USING LINKED LIST
AND NO BACK STORAGE ARRAY

OBSERVATIONS 

NOTE: BIG TROUBLES NOTED by not using a back storage array ..(look for a version 2 soon)
note: this version uses only in place linked list nodes

*** NOTE: A btter quicksort algorithm works in place, by swapping elements within the array, to avoid the memory allocation of more arrays. 

REF: https://en.wikipedia.org/wiki/Abstraction_%28computer_science%29

        NOTE: Unfortunately, Quicksort's performance degrades as the input list becomes more ordered. (don't use this one for resorting each time!)

*/

//uses doubly linked list

var LinkedList = function () {
    this.head = null;
    this.tail = null; 

    var LinkedListNode = function (content) {
        this.next = null;
        this.prev = null;
        this.content = content;   
    };

    this.compareNode = function (n1,n2) {
        if (n1.content==n2.content) return 0;
        if (n1.content<n2.content) return -1;
        if (n1.content>n2.content) return 1;        
    }

    this.compareIndex = function (ind1,ind2) {        
        // (O(n) walking to find index)
        var n1 = ll.findIndex(ind1);
        var n2 = ll.findIndex(ind2);    
        if (n1.content==n2.content) return 0;
        if (n1.content<n2.content) return -1;
        if (n1.content>n2.content) return 1;       
    };  

    this.add = function (content) {        
        this.size++;        
        // No head - create one
        if (this.head == null) {
            this.head = new LinkedListNode(content);
            return this.head;
        }

        // No  tail - create one & set its prev to the head
        if (this.tail == null) {
            this.tail = new LinkedListNode(content);
            this.tail.prev = this.head;
            this.head.next = this.tail;
            return this.tail;
        };

        this.tail.next = new LinkedListNode(content);    
        this.tail.next.prev = this.tail;
   ...