Transcript Sorting (Chapter 24)

SORTING


Concept: putting a group of objects that are out of order,
into their correct order
Objects that might need to be sorted should:


Implement a Comparable interface
Provide a public int compareTo(Object o) method that:
Returns >0 if the current object is greater than the one being
compared
 Returns <0 if the current object is less than the one being compared
 Returns 0 if the objects are equal


Provide an equals method (public boolean equals(Object
o) that returns true if the two objects are equal.
APPROACHES
Use generic sort methods provided by Java
 Create your own sorting methods

 Bubble
Sort
 Shell Sort
 Many other faster sorts, some faster, some not
 Quick
sort
 Radix sort
 Merge sort
 Heap sort
 Insertion sort
BUBBLE SORT




Requires a double for
loop that swaps adjacent
entries if they are out of
order
If there are n elements to
sort, it requires at most
n-1 passes through the
data
It works fine but is one of
the slowest sorts
Each pass


Maximum number drops
to the bottom
Minimum number goes up
one spot
BUBBLE SORT CODE
Simple version
Comparable temp;
int n = data.length;
for (int i=01 i<n; i++)
{
for (int j=0; j<n-1; j++)
{
if (data[j].compareTo(data[j+1])>0)
{
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
Optimized version
boolean swap= true;
Comparable temp;
int n = data.length;
for (int i=0; i<n-1 && swap==true; i++)
{ swap = false;
for (int j=0; j<n-i; j++)
{ if (data[j].compareTo(data[j+1])>0)
{ swap = true;
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
SHELL SORT


Faster than bubble, but still
not optimal
Idea:



Preprocessing of the data
Move smaller entries towards the top faster
Efficiency


Bubble requires n2/2 steps
Shell (described here) normally requires n3/2 steps
SHELL SORT CODE
boolean swap= true;
Comparable temp;
int n = data.length, gap = n/2;
while (gap>0)
{ while (swap)
{ swap = false;
for (int j=0; j<n-gap; j++)
{ if (data[j].compareTo(data[j + gap])>0)
{ swap=true; temp=data[j]; data[j]=data[j+gap]; data[j+gap]=temp; }
}
}
gap = gap /2; swap = true;
}
GENERIC SORTS IN JAVA
import java.util.ArrayList;
import java.util.Collections;
public class Sort
{ public static void main(String[] args)
{ ArrayList<String> data = new ArrayList<String>();
data.add("1"); data.add("3"); data.add("5"); data.add("2"); data.add("4");
Collections.sort(data);
System.out.println("Data sorted in ascending order : ");
for (Comparable temp: data) System.out.println(temp);
}
}