fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		var list = new DoublyLinkedList<Integer>();
  13.         var tempList = new ArrayList<Integer>();
  14.  
  15.         var random = new Random();
  16.  
  17.         for (int i = 0; i < 10; i++) {
  18.             var value = random.nextInt(10);
  19.             list.pushBack(value);
  20.             tempList.add(value);
  21.         }
  22.  
  23.         System.out.println("Initial :" + list.toString());
  24.  
  25.         list.sort(Integer::compare);
  26.         tempList.sort(Integer::compare);
  27.  
  28.         System.out.println("Expected:" + tempList.toString());
  29.         System.out.println("Actual:  " + list.toString());
  30. 	}
  31. }
  32.  
  33. class Node<T> {
  34.     protected T data;
  35.  
  36.     protected Node<T> next, prev;
  37.  
  38.     public Node(T d, Node n, Node p) {
  39.         data = d;
  40.         next = n;
  41.         prev = p;
  42.     }
  43. }
  44.  
  45. class DoublyLinkedList<T extends Comparable<T>> {
  46.     protected Node<T> front;
  47.     protected Node<T> back;
  48.     protected int size;
  49.  
  50.     public void pushBack(T val) {
  51.         var nptr = new Node<T>(val, null, null);
  52.         if (front == null) {
  53.             front = nptr;
  54.             back = front;
  55.         } else {
  56.             nptr.prev = back;
  57.             back.next = nptr;
  58.             back = nptr;
  59.         }
  60.         size++;
  61.     }
  62.  
  63.     @Override
  64.     public String toString() {
  65.         var builder = new StringBuilder("[");
  66.  
  67.         var curr = front;
  68.         while (curr != null) {
  69.             builder.append(curr.data).append(", ");
  70.             curr = curr.next;
  71.         }
  72.         builder.delete(builder.length() - 2, builder.length());
  73.         builder.append("]");
  74.  
  75.         return builder.toString();
  76.     }
  77.  
  78.     public void sort(Comparator<T> comparator) {
  79. 	    quickSort(front, back, comparator);
  80. 	}
  81.  
  82. 	private void quickSort(Node<T> begin, Node<T> end, Comparator<T> comparator) {
  83. 	    if (end != null && begin != end && begin != end.next) {
  84. 	        var temp = partition(begin, end, comparator);
  85. 	        quickSort(begin, temp.prev, comparator);
  86. 	        quickSort(temp.next, end, comparator);
  87. 	    }
  88. 	}
  89.  
  90. 	private Node<T> partition(Node<T> begin, Node<T> end, Comparator<T> comparator) {
  91. 	    var pivot = end.data;
  92.  
  93. 	    var i = begin.prev;
  94. 	    Node<T> next;
  95.  
  96. 	    for (var j = begin; j != end; j = next) {
  97. 	        next = j.next;
  98. 	        if (comparator.compare(j.data, pivot) < 0) {
  99. 	            i = (i == null) ? begin : i.next;
  100.  
  101. 	            //swapData(i, j);
  102. 	            swapNodes(i, j);
  103. 	            i = j;
  104. 	        }
  105. 	    }
  106.  
  107. 	    i = (i == null) ? begin : i.next;
  108. 	    //swapData(i, end);
  109. 	    swapNodes(i, end);
  110.  
  111. 	    //return i;
  112. 	    return end;
  113. 	}
  114.  
  115. 	private void swapData(Node<T> a, Node<T> b) {
  116. 	    var temp = a.data;
  117. 	    a.data = b.data;
  118. 	    b.data = temp;
  119. 	}
  120.  
  121. 	private void swapNodes(Node<T> a, Node<T> b) {
  122. 	    if (a == b) return;
  123.  
  124. 	    if (a == null || b == null) {
  125. 	        throw new NullPointerException();
  126. 	    }
  127.  
  128. 	    if (a.next == b) {
  129. 	        var before = a.prev;
  130. 	        var after = b.next;
  131.  
  132. 	        link(before, b);
  133. 	        link(b, a);
  134. 	        link(a, after);
  135. 	    } else if (b.next == a) {
  136. 	        var before = b.prev;
  137. 	        var after = a.next;
  138.  
  139. 	        link(before, a);
  140. 	        link(a, b);
  141. 	        link(b, after);
  142. 	    } else {
  143. 	        var aPrev = a.prev;
  144. 	        var aNext = a.next;
  145. 	        var bPrev = b.prev;
  146. 	        var bNext = b.next;
  147.  
  148. 	        link(aPrev, b);
  149. 	        link(b, aNext);
  150. 	        link(bPrev, a);
  151. 	        link(a, bNext);
  152. 	    }
  153. 	}
  154.  
  155. 	private void link(Node<T> a, Node<T> b) {
  156. 	    if (a != null)
  157. 	        a.next = b;
  158. 	    else
  159. 	        front = b;
  160. 	    if (b != null)
  161. 	        b.prev = a;
  162. 	    else
  163. 	        back = a;
  164. 	} 
  165. }
Success #stdin #stdout 0.1s 36068KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Initial :[1, 1, 1, 3, 5, 2, 1, 6, 1, 4]
Expected:[1, 1, 1, 1, 1, 2, 3, 4, 5, 6]
Actual:  [1, 1, 1, 3, 2, 1, 1, 4, 5, 6]
https://ideone.com/UQrzY1
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!