Java Chapter 13 - Sorting

A sorting algorithm puts elements in a list or array into a certain order.  Common orders include numeric and alphabetical.  There are many types of sorting algorithms including loops and recursion. 

13.1  Stability

A sorting algorithm is said to be stable if two elements with equal keys appear in the same order after being sorted.  This could be important if sorting records with multiple fields.  The Bubble and Merge sorts are stable.

13.2  Bubble Sort

The bubble sort is an inefficient sorting algorithm that is seldom used in practice.  It is very simple to write and is a therefore a good introduction to sorting.  It's growth rate is O(n²).  It steps through the data n times and repeatedly compares adjacent numbers and swaps them if needed.  You may reference the Wiki for a demonstration.  The algorithm can be written as follows:
 

// n is the dataset size
int Temp;
for (int x=0; x<n; x++)
{
   for (int y=0; y<n-1-x; y++)
   {
      // compare data[y] & data[y+1] and swap if needed
      if (data[y] > data[y+1])
      {
         Temp = data[y];
         data[y] = data[y+1];
         data[y+1] = Temp; 
      }
   }
}
 

13.3  Selection Sort

The is a more efficient nested for loop algorithm than the bubble sort.  Its growth rate is also O(n²).  It divides the data into two parts: the part already sorted on the left, and the unsorted part on the right.  It steps through the unsorted part and searches for the smallest item and moves it to the left.  You may reference the Wiki for a demonstration.  The algorithm can be written as follows:

for (int x=0; x<n; x++)
{
   min = x;  // data[x] will start as the smallest value
   for (int y=x; y<n; y++)
   {
      if (data[y] < data[min])
      {
         min = y;
      }
   }
   // swap data[x] with data[min]
   Temp = data[x];
   data[x] = data[min];
   data[min] = Temp;       
}


13.4  Merge Sort

The merge sort is a more efficient sort than the previous two with a growth rate of O(n(log n)).  Since it is a recursive sort it will use a more memory than other sorts.  It begins by dividing the data set into two halves - the Left half and Right half.  It then recurses and keeps dividing the data set into halves until the parts get down to one element.  The recursion begins merging the sorted pieces until you are left with a single sorted dataset.  It takes two methods - one that divides the data and one that merges the pieces into sorted lists.  Assuming you are using an ArrayList, the methods are below.

static ArrayList<Integer> MergeSort(ArrayList<Integer> dataset)
{
   if (dataset.size() == 1) return dataset;
   else
   {
      // split data into 2 parts
      ArrayList<Integer> LeftData = new ArrayList<Integer>(dataset.subList(0,dataset.size()/2));
      ArrayList<Integer> RightData = new ArrayList<Integer>(dataset.subList(dataset.size()/2,dataset.size()));
      dataset = Merge(MergeSort(LeftData), MergeSort(RightData));
   }
   return dataset;
}

// merge the left and right lists together
static ArrayList<Integer> Merge(ArrayList<Integer> LeftData, ArrayList<Integer> RightData)
{
   ArrayList<Integer> MergedData = new ArrayList<Integer>();
   while (LeftData.size() > 0 || RightData.size() > 0)
   {
      if (RightData.size() == 0)
      {
         MergedData.add(LeftData.get(0));
         LeftData.remove(0);
      }
      else if (LeftData.size() == 0)
      {
         MergedData.add(RightData.get(0));
         RightData.remove(0);
      }
      else if (LeftData.get(0) < RightData.get(0))
      {
         MergedData.add(LeftData.get(0));
         LeftData.remove(0);
      }
      else
      {
         MergedData.add(RightData.get(0));
         RightData.remove(0);
      }
   }
   return MergedData;
}
 

13.5  Radix Sort

Below is the Radix sort method.  You may need to change the condition in the first for loop to a higher or lower value for k.

static ArrayList<Integer> RadixSort(ArrayList<Integer> dataset)
{
	ArrayList<Integer> dataset2 = new ArrayList<Integer>();
	for (int k=1; k<=1000000; k*=10)
	{
		for (int i=0; i<=9; i++)
		{
			for (int j=0; j<dataset.size(); j++)
			{
				if (dataset.get(j)/k%10 == i)
					dataset2.add(dataset.get(j));
			}
		}

		dataset.clear();
		for (int m=0; m<dataset2.size(); m++)
		{
			dataset.add(dataset2.get(m));
		}
		dataset2.clear();
	}
	return dataset;    
}