Bubble Sort Example

Demonstrates bubbling in sort function

by Jake Jernigan

HTML

Demonstration of Sorted Insertion <br/>
Add to List <input type="textbox" id="content"/>
<input type="button" id = "addToSortedList" onclick="addToList();" value = "Add to List"/>
<br/><br/>
To see a bubble sort in action (1) Click Generate Random List and then (2) Click Demonstrate Bubble Sort. Each click will generate a single bubble sort pass. Continue to click until the before list is the same as the after (no changes made) and that is the sorted list.
<p id="list"></p><br/><br/>
Demonstration of a Random Generated List
<input type="button" id="generateRandomList" onclick="generateRandomList()" value="Generate Random List"/><br/><br/>
Demonstration of a Bubble Sort Pass
<input type="button" id="bubbleSort" onclick="bubbleSort()" value="Demonstrate bubble sort"/><br/><br/>
<br/>
<p id="steps"></p>

JavaScript

var SortedLinkedList = function() {
  this.head = null;
}

var SortedLinkedListNode = function(_content) {
  this.content = _content;
  this.next = null;
}

SortedLinkedList.prototype.add = function(_content) {
  var node = new SortedLinkedListNode(_content);
  
  // no head - make head
  if (this.head == null) {
     this.head = node;
     return this;
     }
  
  // make new head if less than head   
  if (node.content < this.head.content) {
       node.next = this.head;
       this.head = node;
       return this;
     }
  
  this.head.add(this.head, node);
  return this;
}

SortedLinkedListNode.prototype.add = function(p, n){
   // put in front if less than
   if (n.content < this.content) {
     p.next = n;
     n.next = this;
     return this;
   }
     
   // put at tail if greater than and no next
   if (this.next == null) {
     p.next = this;
     this.next = n;
     return this;
   }
   
    // pass to next node if greater than and next exists
   return this.next.add(this, n); 
}

SortedLinkedListNode.prototype.sort = function() {
     
// sorts this.next with this.next.next
    if (this.next == null) {return null;}
    if (this.next.next == null) {return null;}

    var a = this.next;
    var b = this.next.next;
      
    if (b.content < a.content) {
     
     this.next = b; 
     a.next = b.next;
     b.next = a; 
  }
}

SortedLinkedList.prototype.bubbleSort = function() {

  if (this.head == null) {return this;}
  
  var a = this.head;
  var b = this.head.next;
  var c = this.head.next;
  
  if (b.content < a.content) {
     
     document.getElementById("steps").innerHTML += 
      "Swapping " + a.content + " and " + b.content + "</br>";          
     a.next = b.next;
     b.next = a; 
     this.head = b;
  }  
  
  var current = this.head;
  while (current.next != null && current.next.next != null) {
  current.sort();
  current = current.next;
  }
  
}

SortedLinkedList.prototype.create = function(n) {
for (var i = 1; i < n; i++) {
  var letter...