Double Linked List Merge Sort
12:47:00 PMKali ini saya mau berbagi ilmu tentang double linked list merge sort.
Codingan ini saya dapat saat browsing-browsing iseng. Oia, saya jelaskan sedikit dulu tentang double linked list.
Double linked list hampir sama dengan linked list, namun dalam satu node dia memiliki prev dan next. Saat merge sort double linked list dapat diurutkan dari depan maupun dari belakang.
Dibandingkan dengan single linked list, memodifikasi sebuah double linked list biasanya membutuhkan perubahan pointer lebih banyak, tetapi kadang-kadang sederhana karena tidak perlu melacak alamat dari node sebelumnya.
Langsung saja, ini codingannya
import java.util.List;
import java.util.LinkedList;
/**
* This class implements the mergesort operation, trying to stay
* as close as possible to the implementation described on the
* Wikipedia page for the algorithm. It is meant to work well
* even on lists with non-constant random-access performance (i.e.
* LinkedList), but assumes that {@code size()} and {@code get(0)}
* are both constant-time.
*
* @author jasonmp85
* @see Merge sort
*/
public class doubly {
/**
* Keeps track of the call depth for printing purposes
*/
private static int depth = 0;
/**
* Creates a list of 10 random Longs and sorts it
* using {@link #sort(List)}.
*
* Prints out the original list and the result.
*
*/
public static void main(String[] args) {
LinkedList
for(int i = 0; i < 10; i++) {
list.add((long)(Math.random() * 100));
}
System.out.println("ORIGINAL LIST\n" +
"=================\n" +
list + "\n");
List
System.out.println("\nFINAL LIST\n" +
"=================\n" +
sorted + "\n");
}
/**
* Performs a merge sort of the items in {@code list} and returns a
* new List.
*
* Does not make any calls to {@code List.get()} or {@code List.set()}.
*
* Prints out the steps, indented based on call depth.
*
* @param list the list to sort
*/
public static
depth++;
String tabs = getTabs();
System.out.println(tabs + "Sorting: " + list);
if(list.size() <= 1) {
depth--;
return list;
}
List
List
List
int middle = list.size() / 2;
int added = 0;
for(T item: list) {
if(added++ < middle)
left.add(item);
else
right.add(item);
}
left = sort(left);
right = sort(right);
result = merge(left, right);
System.out.println(tabs + "Sorted to: " + result);
depth--;
return result;
}
/**
* Performs the oh-so-important merge step. Merges {@code left}
* and {@code right} into a new list, which is returned.
*
* @param left the left list
* @param right the right list
* @return a sorted version of the two lists' items
*/
private static
List
String tabs = getTabs();
System.out.println(tabs + "Merging: " + left + " & " + right);
List
while(left.size() > 0 && right.size() > 0) {
if(left.get(0).compareTo(right.get(0)) < 0)
result.add(left.remove(0));
else
result.add(right.remove(0));
}
if(left.size() > 0)
result.addAll(left);
else
result.addAll(right);
return result;
}
/**
* Returns a number of tabs based on the current call depth.
*
*/
private static String getTabs() {
StringBuffer sb = new StringBuffer("");
for(int i = 0; i < depth; i++)
sb.append('\t');
return sb.toString();
}
}
0 komentar