Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
var assert = require('assert')
function Node(){
this.parent
this.data
this.next
this.index
}
function sort(a, index, p){
if(index === a.length+1){
return a
}
if(a.length === 0) return []
if(typeof index === 'undefined') index = a.length-1
if(index<0){
return traversal(a)
}
if(index === a.length-1){
var node = new Node
node.parent = null
node.data = a[index]
node.index = index
node.next = null
a[index] = node
return sort(a, index-1, index)
}else{
if(a[index] === a[p].data){
var node = new Node
node.parent = p
node.data = a[index]
node.index = index
node.next = a[p].next
a[index] = node
a[p].next = index
if(a[index].next !== null) a[a[index].next].parent = index
return sort(a, index-1, index)
}else if(a[index] > a[p].data){
if(a[p].parent === null){
var node = new Node
node.parent = null
node.data = a[index]
node.index = index
node.next = p
a[index] = node
a[p].parent = index
return sort(a, index-1, index)
}else if(a[index] > a[p].data && a[index] < a[a[p].parent].data){
var node = new Node
node.parent = a[p].parent
node.data = a[index]
node.index = index
node.next = a[p].index
a[index] = node
a[p].parent = index
a[a[index].parent].next = index
return sort(a, index-1, index)
}else return sort(a, index, a[p].parent)
}else{
if(a[p].next === null){
var node = new Node
node.parent = p
node.data = a[index]
node.index = index
node.next = null
a[p].next = index
a[index] = node
return sort(a, index-1, index)
}else return sort(a, index, a[p].next)
}
}
}
function traversal(a, index, res){
if(typeof index === 'undefined') index = a.length-1
if(a[index].next === null){
if(print(a, index)) return print(a, index)
}else return traversal(a, a[index].next)
}
function print(a, index, res){
if(!res){
res = []
res[0] = a[index].data
return print(a, a[index].parent, res)
}else{
if(index === null){
return sort(res, res.length+1)
}else{
res[res.length] = a[index].data
return print(a, a[index].parent, res)
}
}
}
function arrayEqual(arrayA, arrayB) {
if(arrayA.length!=arrayB.length) return false
for(var i=0; i<arrayA.length; ++i) {
if(arrayA[i]!=arrayB[i])
return false
}
return true
}
assert(arrayEqual(sort([]), []))
assert(arrayEqual(sort([1]), [1]))
assert(arrayEqual(sort([1, 1]), [1, 1]))
assert(arrayEqual(sort([1, 2]), [1, 2]))
assert(arrayEqual(sort([1, 2, 3]), [1, 2, 3]))
assert(arrayEqual(sort([3, 2, 1]), [1, 2, 3]))
assert(arrayEqual(sort([3, 1, 2]), [1, 2, 3]))
assert(arrayEqual(sort([1, 3, 2]), [1, 2, 3]))
assert(arrayEqual(sort([5, 3, 2, 6, 8, 9, 4, 3 ,5, 1]), [1, 2, 3, 3, 4, 5, 5, 6, 8, 9]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.