")
this.$sort.append(this._createController().element)
this.container = $("
")
this.$sort.append(this.container)
viewElement.append(this.$sort)
this.displayBars()
},
displayBars: function(){
clearTimeout(this.currentTaskId)
this.bars = Bars(this.length, this.container)
this.values = this.bars.values
this.container.empty().append(this.bars.elements)
this._initTask()
profile.start()
this._setTimeout()
},
complete: function(){
this.container.find("span").removeClass("highlight")
if(this.sortFunc.name === "bogoSort"){
if(this.bogoSortCompleted === false){
this._initTask()
this._setTimeout()
return
}
}
profile.end()
},
_createController: function(){
this.controller = Controller({
speed: this.speed,
length: this.length
})
return this._setEventToController(this.controller)
},
_setEventToController: function(controller){
var self = this
controller.onLengthChange = function(length){
self.length = length
self.displayBars()
}
controller.onSpeedChange = function(speed){
self.speed = speed
}
controller.restart = function(){
self.displayBars()
}
return controller
},
_initTask: function(){
this.task = Queue()
this.sortFunc()
},
_next: function(){
var order = this.task.get()
if(order === undefined){
this.complete()
return
}
var command = order[2]
if(command === C.insert){
this.bars.insert(order[0], order[1])
}else{
this.bars.swap(order[0], order[1], command)
}
this._setTimeout()
},
_setTimeout: function(){
var self = this
var interval = 2000 / this.speed
this.currentTaskId = setTimeout(function(){
self._next()
}, interval)
}
})
})();
$(function(){
// -----------------------------------------
// Bubble sort
// -----------------------------------------
function bubbleSort(){
var array = this.values
var length = array.length
for(var i = length - 1; 0 < i; i--){
for(var j = 0; j < i; j++){
this.compare(j, j + 1)
}
}
}
// -----------------------------------------
// Selection sort
// -----------------------------------------
function selectionSort(){
var array = this.values
var length = array.length
for(var i = 0; i < length - 1; i++){
var minIndex = i
var minValue = array[minIndex]
for (var j = i + 1; j < length; j++) {
this.highlight(j, minIndex)
if (array[j] < minValue) {
minIndex = j
minValue = array[minIndex]
}
}
this.compare(i, minIndex)
}
return array
}
// -----------------------------------------
// Shaker Sort
// -----------------------------------------
function shakerSort(){
var array = this.values
var length = array.length
var left = 0
var right = length - 1
var lastSwappedLeft = left
var lastSwappedRight = right
while(left < right){
lastSwappedRight = 0
for(var i = left; i < right; i++){
if(array[i] > array[i + 1]){
this.swap(i, i + 1)
lastSwappedRight = i
}else{
this.highlight(i, i + 1)
}
}
right = lastSwappedRight
lastSwappedLeft = length - 1
for(var j = right; left < j; j--){
if(array[j - 1] > array[j]){
this.swap(j - 1, j)
lastSwappedLeft = j
}else{
this.highlight(j - 1, j)
}
}
left = lastSwappedLeft
}
}
// -----------------------------------------
// Insertion sort
// -----------------------------------------
function insertionSort(){
var array = this.values
var length = array.length
for(var i = 1; i < length; i++){
for(var j = i; 0 < j; j--){
if(array[j - 1] > array[j]){
this.swap(j - 1, j)
}else{
this.highlight(j - 1, j)
break
}
}
}
}
// -----------------------------------------
// Shell Sort
// -----------------------------------------
function shellSort(){
var array = this.values
var length = array.length
var gap = 1
while(gap < length) {
gap = 3 * gap + 1
}
while(gap > 1){
gap = Math.floor(gap / 3)
for(var i = gap; i < length; i++){
for(var j = i; 0 < j; j -= gap){
if(array[j - gap] > array[j]){
this.swap(j - gap, j)
}else{
this.highlight(j - gap, j)
break
}
}
}
}
}
// -----------------------------------------
// Quick sort
// -----------------------------------------
function quickSort(first, last){
// TODO: あとで書き直す
var array = this.values
first = (first === undefined) ? 0 : first
last = (last === undefined) ? (array.length - 1) : last
var pivotIndex = Math.floor((first + last) / 2)
var pivotValue = array[pivotIndex]
var f = first, l = last
while(true){
while(true){
this.highlight(f, pivotIndex)
if(!(array[f] < pivotValue)) break
f++
}
while(true){
this.highlight(l, pivotIndex)
if(!(pivotValue < array[l])) break
l--
}
if(l <= f){
break
}
if(pivotIndex === l){
pivotIndex = f
}
if(pivotIndex === l){
pivotIndex = l
}
this.compare(f, l)
f++; l--
}
if(first < f - 1) quickSort.call(this, first, f - 1)
if(l + 1 < last) quickSort.call(this, l + 1, last)
}
// -----------------------------------------
// Merge sort
// -----------------------------------------
function mergeSort(first, last){
var array = this.values
first = (first === undefined) ? 0 : first
last = (last === undefined) ? array.length - 1 : last
if (last - first < 1) {
return
}
var middle = Math.floor((first + last) / 2)
mergeSort.call(this, first, middle)
mergeSort.call(this, middle + 1, last)
var f = first
var m = middle
while (f <= m && m + 1 <= last) {
this.highlight(f, m + 1)
if (array[f] >= array[m + 1]) {
this.insertBefore(m + 1, f)
m++
}
f++
}
}
// -----------------------------------------
// Heap sort
// -----------------------------------------
function swapUp(array, current){
var parent = Math.floor((current - 1) / 2)
while(current != 0){
if (!(array[current] > array[parent])) {
this.highlight(current, parent)
break
}
this.swap(current, parent)
current = parent
parent = Math.floor((current - 1) / 2)
}
}
function swapDown(array, current, length){
var child = current * 2 + 1
while(true){
if(array[child] < array[child + 1]){
child += 1
}
if(array[current] >= array[child]){
this.highlight(current, child)
break
}
if(length <= child){
break
}
this.swap(current, child)
current = child
child = current * 2 + 1
}
}
function heapify(array){
for(var i = 0; i < array.length; i++){
swapUp.call(this, array, i)
}
}
function heapSort(){
var array = this.values
heapify.call(this, array)
for(var i = array.length - 1; 0 < i; i--){
if(array[0] > array[i]){
this.swap(0, i)
}else{
this.highlight(0, i)
}
swapDown.call(this, array, 0, i)
}
}
// -----------------------------------------
// Bogo sort
// -----------------------------------------
function bogoSort(){
var array = this.values
this.bogoSortCompleted = false
var length = array.length
// shffle
for(var i = 0; i < length; i++){
var j = Math.floor(Math.random() * length)
this.swap(i, j)
}
// check
for(var i = 0; i < length - 1; i++){
this.highlight(i, i + 1)
if(array[i] > array[i + 1]){
return // incomplete
}
}
this.bogoSortCompleted = true
}
bogoSort.name = "bogoSort"
// -----------------------------------------
// Main
// -----------------------------------------
var sort = GraphicalSort()
// default sort function
sort.sortFunc = bubbleSort
var view = $("#view")
view.width($(window).width()).height($(window).height() - 125)
sort.show(view)
// -----------------------------------------
// Sort menu
// -----------------------------------------
var sortMenu = {
"Bubble": bubbleSort,
"Selection": selectionSort,
"Shaker": shakerSort,
"Insertion": insertionSort,
"Shell": shellSort,
"Quick": quickSort,
"Merge": mergeSort,
"Heap": heapSort,
"Bogo": bogoSort
}
var menu = $("
").insertBefore(view).css({
height: 65,
margin: "10px 0px",
fontSize: 12
})
$.each(sortMenu, function(name, func){
var radio = $("
").attr("id", name).appendTo(menu)
var label = $("