How to partition linked list around minimum value

Question

I am trying to perform a selection sort on a linked list using recursion and I am having some trouble partitioning my linked list around the node with the smallest value on each pass through my recursive sort function. I am trying to get the node with the smallest value, partition the linked list around the smallest value, append the smallest to the front, join the two partitioned lists, and then perform the sort again on the joined partitioned list until the entire linked list is sorted. For example:

 q w  e  r t // partition around e
 e  -> q w r t // join the partitions
 eq -> w r t // append q to e
 eq -> w r t // partition around r

and so forth.

My sort method:

 Node.prototype.sort = function(){
   if(!next){
      return this;
 } else {
    var a = null;
    var b = null;
    var smallest = this.smallest();
    splitIt(smallest, a, b);
    appendSmallest(smallest);
    a.join(b);
    a.sort();
  }
}

I get the smallest node like so:

 Node.prototype.smallest = function(){
   if(!next) return this;
   var sm = next.smallest();
   if(sm.data < this.data){
      return sm;
   }
   return this;
 }

Here are my append and join methods:

 Node.prototype.appendSmallest = function(smallest){
    if(!next) next = smallest;
 }


 Node.prototype.join = function(otherNode){
     if(!next) next = otherNode;
     else next.join(otherNode);
 }

I am having some trouble implementing the splitIt method recursively. What would the pseudocode be for such operation?

If your `.smallest` function returned a pair of `[previous_node, the_smallest_node]`, splitting would be trivial. If the first node is the smallest, `previous_node` is `null`. — 9000, Feb 07 '17 at 17:09

score 1 · Accepted Answer · edited May 23 '17 at 12:17

I'm assuming you are using pure JavaScript, as there is no indication otherwise.

In your code you use several times the word Node as kind of a variable type in a way that is not valid JS. You declare variables with the word var (and in ECMAScript6 let for block scoped variables). Look at this question. So for example in smallest you write:

var sm = next.smallest();

In sort you have two additional problems: first, you pass null variables as parameters in hope that the function will assign objects that will replace them (see the explanation here regarding the nature of reference valued variables (not primitive valued) in JS). Second, assuming you forgot but meant to have this line in appendSmallest

else { next.appendSmallest(smallest);}

then I think you have an infinite loop, as smallest is appended to this linked list, which is (if splitIt works properly) is the same as a.

My suggestion is doing the split and join together as a "spitSmallest" function:

Node.prototype.spitSmallest = function(smallest){
    //we know that this node is not smallest
    if (this.next  == smallest){
        this.next = this.next.next;
        smallest.next = null; //again not really needed
    } else {
        this.next.spitSmallest(smallest);
    }
}

Node.prototype.sort = function(){
   if(!this.next){
      return this;
 } else {
    var smallest = this.smallest();
    var restHead;
    if (smallest==this){
        restHead = this.next;
        this.next = null; //not needed but makes it more readable
    } else {
        restHead = this;
        this.spitSmallest(smallest);
    }
    smallest.next = restHead.sort();
    return smallest;
  }
}

Thank you for catching the Node type declaration. I was also programming the same program in Java and I think I got mixed up when writing my question. — Mahmud Adam, Feb 07 '17 at 23:55
Running this code given list with data fields as: bob, ant, dave, camp results in ant, camp, dave, bob... — Mahmud Adam, Feb 08 '17 at 18:35
It works for me. I get ant-bob-camp-dave. Look at this [JSFiddle](https://jsfiddle.net/et_l/v7uovvjv/). Also - I've updated the code above, as you need the `this` keywords every time you reference a property belonging to the object you are working as. — et_l, Feb 08 '17 at 21:12
Oh yes, it does work. I was accidentally setting smallest to var smallest = next.smallest(). Thanks! — Mahmud Adam, Feb 08 '17 at 21:48

How to partition linked list around minimum value

1 Answers1