Lesson 5.1 - Sort Methods
Purpose: To learn how to sort numbers and text stored in arrays
Sort of... We will now take data (numbers or text) stored in arrays and sort it. There are two orders in which to sort - ascending (lowest to highest) and descending (highest to lowest). In addition, there are numerous methods which can be use to sort an array. Let's learn three: BUBBLE, SELECTION, and INSERTION.
For each of the following, we assume that list is defined as follows:
int[] list = new int[n]; // n = some integer
THE BUBBLE SORT ALGORITHM - descending order
int i, j, temp;
for(i=n-1; i>0; i--)
for(j=0; j<i; j++)
if(list[j]<list[j+1])
{
temp=list[j];
list[j]=list[j+1];
list[j+1]=temp;
}
THE SELECTION SORT ALGORITHM - descending order
int i, j, temp, maxIndex;
for(i=0; i<len-1; i++)
{
maxIndex=i;
for(j=i+1; j<len; j++)
if(list[j]>list[maxIndex])
maxIndex=j;
temp=list[maxIndex];
list[maxIndex]=list[i];
list[i]=temp;
}
THE INSERTION SORT ALGORITHM - descending order
int i, j, temp;
for(i=1; i<len; i++)
{
j=i;
while(j>0 && list[j]>list[j-1])
{
temp=list[j];
list[j]=list[j-1];
list[j-1]=temp;
j--;
}
}
Note that to change any of these to an ascending order sort, all we have to do is change the direction of the inequality symbol in the condition of the if.
In closing, each sort method has its own technique for sorting. While the end result is the same, the path to that point isn't. Understand the general idea of how each sort works and don't bother memorizing the Java algorithm. Lastly, the bubble sort is fine for small arrays, but gets bogged down with too many comparisons and switches when we encounter a large collection of data. The selection and insertion are much faster in this case. Use either with approximately equal results in efficiency.
|