Java Data Structures - Contents
A D V E R T I S E M E N T
Sorting, in general, means arranging something in
some meaningful manner. There are TONS of ways of sorting things, and we will only look at
the most popular ones. The one we won't cover here (but one you should know) is Quick
Sort. You can find a really good Quick Sort example in the JDK's sample applets. We have
also learned that we can sort using binary trees, thus, in this section, we won't cover
that approach.
We will be using JDK 1.2's java.lang.Comparable
interface in this section, thus, the examples will not work with earlier versions of the
JDK. The sorting algorithms we'll look at in this section are: Bubble Sort, Selection
Sort, Insertion Sort, Heap Sort, and lastly, Merge Sort.
If you think that's not enough, you're welcome to find other algorithms from other
sources. One source I'd recommend is the JDK's sources. The JDK has lots of code, and lots
of algorithms that may well be very useful.
We won't exactly cover the algorithms; I will simply
illustrate them, and you'll have to figure out how they work from the source. (By tracing
them.) I don't have the time to go over each and every algorithm; I'm just taking my old C
source, converting it to Java, and inserting it into this document ;-)
import java.io.*;
import java.util.*;
import java.lang.*;
public class pGeneralSorting{
public static void BubbleSort(Comparable[] a){
boolean switched = true;
for(int i=0;i<a.length-1 && switched;i++){
switched = false;
for(int j=0;j<a.length-i-1;j++)
if(a[j].compareTo(a[j+1]) > 0){
switched = true;
Comparable hold = a[j];
a[j] = a[j+1];
a[j+1] = hold;
}
}
}
public static void SelectionSort(Comparable[] a){
for(int i = a.length-1;i>0;i--){
Comparable large = a[0];
int indx = 0;
for(int j = 1;j <= i;j++)
if(a[j].compareTo(large) > 0){
large = a[j];
indx = j;
}
a[indx] = a[i];
a[i] = large;
}
}
public static void InsertionSort(Comparable[] a){
int i,j;
Comparable e;
for(i=1;i<a.length;i++){
e = a[i];
for(j=i-1;j>=0 && a[j].compareTo(e) > 0;j--)
a[j+1] = a[j];
a[j+1] = e;
}
}
public static void HeapSort(Comparable[] a){
int i,f,s;
for(i=1;i<a.length;i++){
Comparable e = a[i];
s = i;
f = (s-1)/2;
while(s > 0 && a[f].compareTo(e) < 0){
a[s] = a[f];
s = f;
f = (s-1)/2;
}
a[s] = e;
}
for(i=a.length-1;i>0;i--){
Comparable value = a[i];
a[i] = a[0];
f = 0;
if(i == 1)
s = -1;
else
s = 1;
if(i > 2 && a[2].compareTo(a[1]) > 0)
s = 2;
while(s >= 0 && value.compareTo(a[s]) < 0){
a[f] = a[s];
f = s;
s = 2*f+1;
if(s+1 <= i-1 && a[s].compareTo(a[s+1]) < 0)
s = s+1;
if(s > i-1)
s = -1;
}
a[f] = value;
}
}
public static void MergeSort(Comparable[] a){
Comparable[] aux = new Comparable[a.length];
int i,j,k,l1,l2,size,u1,u2;
size = 1;
while(size < a.length){
l1 = k = 0;
while((l1 + size) < a.length){
l2 = l1 + size;
u1 = l2 - 1;
u2 = (l2+size-1 < a.length) ?
l2 + size-1:a.length-1;
for(i=l1,j=l2;i <= u1 && j <= u2;k++)
if(a[i].compareTo(a[j]) <= 0)
aux[k] = a[i++];
else
aux[k] = a[j++];
for(;i <= u1;k++)
aux[k] = a[i++];
for(;j <= u2;k++)
aux[k] = a[j++];
l1 = u2 + 1;
}
for(i=l1;k < a.length;i++)
aux[k++] = a[i];
for(i=0;i < a.length;i++)
a[i] = aux[i];
size *= 2;
}
}
public static void main(String[] args){
Integer[] a = new Integer[10];
System.out.print("starting...\nadding:");
for(int i=0;i<a.length;i++){
a[i] = new Integer((int)(Math.random()*100));
System.out.print(" " + a[i]);
}
BubbleSort(a);
System.out.print("\nprinting:");
for(int i=0;i<a.length;i++){
System.out.print(" " + a[i]);
}
System.out.println("\nDone ;-)");
}
}
The above program both illustrates the algorithms,
and tests them. Some of these may look fairly complicated; usually, the more complicated a
sorting algorithm is, the faster and/or more efficient it is. That's the reason I'm not
covering Quick Sort; I'm too lazy to convert that huge thing! Some sample output from the
above program follows:
starting...
adding: 22 63 33 19 82 59 70 58 98 74
printing: 19 22 33 58 59 63 70 74 82 98
Done ;-)
I think you get the idea bout sorting. You can
always optimize the above sorting methods, use native types, etc. You can also use these
in derived classes from java.util.Vector, using the java.util.Vector
data directly. And just when you though we were done with sorting, here we go again...
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
|
Add to Favorites
Make Home Page
