Sorting
32. Write Java programs for implementing the following sorting methods:
(a) Bubble sort
(b) Selection sort
(c) Insertion sort
(d) Quick sort
(e) Merge sort
(f) Heap sort
(g) Radix sort
(h) Binary tree sort
As soon as you create an important database, you will probably think of reasons to sort it in various
ways. You need to arrange names in alphabetical order, students by marks, customers by pin code,
cities in order of increasing population, countries by GNP, and so on.
Sorting data may also be a preliminary step to searching it. As we saw in the previous chapter, a
binary search, which can be applied only to sorted data, is much faster than a linear search.
Because sorting is so important and potentially so time-consuming, it has been the subject of
extensive research in computer science, and some very sophisticated methods have been developed.
First we will look at three of the simpler algorithms: the bubble sort, the selection sort, and the
insertion sort. Besides being easier to understand, they are actually better in some circumstances than
the more sophisticated algorithms. The insertion sort, for example, is preferable to quick sort for small
files and for almost-sorted files. In fact, an insertion sort is commonly used as a part of a quick sort
implementation.
Bubble Sort
The familiar sorting procedure is the bubble sort (exchange sort). This is the widely known among
beginning students of programming and easy to understand and program. Of course, it is probably the
least efficient.
We consider an array, ai of size, n. When this approach is used, there are at most n-1 passes are
required. During the first pass, a0 and a1 are compared, and if they are out of order, then a0 and a1 are
interchanged; this process is repeated for a1 and a2, a2 and a3, and so on. This method will cause small
elements to move or “bubble up”. After the first pass, the array with the largest element will be in the
position n-1 (last location). On each successive pass, the array with the next largest element will be
placed in position n-2, n-3,.., 1, respectively, thereby resulting in a sorted array.
After each pass through the array, a check can be made to determine whether any interchanges
were made during that pass. If no interchanges occurred, then the array must be sorted and no further
passes are required. An example of bubble sort for the array {27, 49, 35, 37, 15, 75, 63, 65} is
illustrated in the Table 9.1.
Program 9(a): Bubble Sort
void bubbleSort(Object[] a)
{
int i, pass, exch, n = a.length;
Object tmp;
for( pass = 0; pass < n; pass++ )
{ exch = 0;
86 Lab Manual Data Structures through Java
for( i = 0; i < n-pass-1; i++ )
if( ((Comparable)a[i]).compareTo(a[i+1]) > 0)
{ tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
exch++;
}
if( exch == 0 ) return; // sorting finished – return early
}
}
Table 9.1: Trace of Bubble sort (elements to be interchanged are shown in red colour)
pass 0 1 2 3 4 5 6 7 Process
- 27 49 35 37 15 75 63 65 Original array
1 27 35 49 37 15 75 63 65 49, 35 interchanged
1 27 35 37 49 15 75 63 65 49, 37 interchanged
1 27 35 37 15 49 75 63 65 49, 15 interchanged
1 27 35 37 15 49 63 75 65 75, 63 interchanged
1 27 35 37 15 49 63 65 75 75, 65 interchanged
2 27 35 15 37 49 63 65 75 37, 15 interchanged
3 27 15 35 37 49 63 65 75 35, 15 interchanged
4 15 27 35 37 49 63 65 75 27, 15 interchanged
Selection Sort
One of the easiest ways to sort a list is by selection. Beginning with the first element in the array, a
search is performed to locate the smallest element. When this item is found, it is exchanged with the
first element. This interchange places the smallest element in the first position of the array. A search
for the second smallest element is then carried out. Examining the items from second position onward
does this. The smallest element is exchanged with the item in second position. This process continues
until all elements of the array have been sorted in ascending order. The following is the selection sort
algorithm.
An example of the selection sort is given in the Table 9.2. The second row (pass 0) of the table
shows the original unordered array.
Table 9.2: Trace of Selection sort (elements to be interchanged are shown in red colour)
0 1 2 3 4 5 6 7 pass min a[pass] a[min] swap a[pass], a[min]
49 27 65 37 15 75 63 60 0 4 49 15 49, 15
min = pass
15 27 65 37 49 75 63 60 1 1 27 27
no exchange
15 27 65 37 49 75 63 60 2 3 65 37 65, 37
15 27 37 65 49 75 63 60 3 4 65 49 65, 49
15 27 37 49 65 75 63 60 4 7 65 60 65, 60
15 27 37 49 60 75 63 65 5 6 75 63 75, 63
15 27 37 49 60 63 75 65 6 7 75 65 75, 65
15 27 37 49 60 63 65 75 Sorted list
9. Sorting 87
Program 9(b): Selection Sort
class SelectionSortDemo
{
public static void main(String[] args)
{
int[] arr = { 49, 27, 65, 37, 15, 75, 63, 60 };
System.out.print("\n Unsorted array: ");
display( arr );
selectionSort( arr );
System.out.print("\n Sorted array: ");
display( arr );
}
static void selectionSort( int a[] )
{
int n = a.length;
for( int pass = 0; pass < n-1; pass++ )
{
int min = pass;
for( int i = pass+1; i < n; i++ )
if( a[i] < a[min] ) min = i;
if( min != pass )
{
int tmp = a[min];
a[min] = a[pass];
a[pass] = tmp;
}
}
}
static void display( int a[] )
{
for( int i = 0; i < a.length; i++ )
System.out.print( a[i] + " " );
}
}
Following output is generated from this program:
Unsorted array: 49 27 65 37 15 75 63 60
Sorted array: 15 27 37 49 60 63 65 75
Insertion Sort
Insertion sort works very fast on small size arrays. The insertion sort procedure scans array, a from
a[0] to a[n-1], inserting each element a[j] into its proper position in the previously sorted sub-array
a[0], a[1], …, a[j-1]. We consider an array of six elements shown in Table 9.3.
88 Lab Manual Data Structures through Java
Table 9.3: Trace of Insertion Sort (inserted elements are shown in red)
pass a[0] a[1] a[2] a[3] a[4] a[5] Process
65 50 30 35 25 45 Original array
1 50 65 30 35 25 45 50 is inserted
2 30 50 65 35 25 45 30 is inserted
3 30 35 50 65 25 45 35 is inserted
4 25 30 35 50 65 45 25 is inserted
5 25 30 35 45 50 65 45 is inserted
Program 9(c): Insertion sort method
void insertionSort(Object a[])
{
int i, j, n = a.length;
Object item;
for( j = 1; j < n; j++ ) // repeat loop starting from a[1] to a[n-1]
{ item = a[j]; // element to be inserted
i = j-1;
while( i >= 0 && ((Comparable)item).compareTo(a[i]) < 0)
{
a[i+1] = a[i]; // shift element to the right
i = i-1;
}
a[i+1] = item; // insert element in proper position
}
}
Quick Sort
The algorithm solely depends on the data it receives. If the data has certain properties, quick sort is one
of the fastest, if not; quick sort can be very slow. Quick sort can perform quite fast, on average about
O(n log n), but its worst case is a degrading O(n2). For quick sort, the worst case is usually when the
data is already sorted.
Quick sort is naturally recursive. We partition the array into two sub-arrays, and then re-start the
algorithm on each of these sub-arrays. The partition procedure involves choosing some object (usually,
already in the array); If some other object is greater than the chosen object, it is added to one of the
sub-arrays, if it is less than the chosen object, it is added to another sub-array. Thus, the entire array is
partitioned into two sub-arrays, with one sub-array having everything that is larger than the chosen
object, and the other sub-array having everything that is smaller.
Variable a is an integer array of size, n. The left and right invoke procedure and they are initialized
with 0 and n -1 respectively; and are the current lower and upper bounds of the sub-arrays. The indices
newleft and newright are used to select certain elements during the processing of each sub-array.
Variable amid is the element which is placed in its final location in the array.
Index left scans the list from left to right, and index right scans the list from right to left. A swap is
performed when left is at an element larger than the pivot and right is at an element smaller than the
