Ton Duc Thang University

Faculty of Information Technology Data Structures and Algorithms, Fall 2020-2021

Lab 4
Sorting
Quang D. C.
[email protected]

September 14, 2020

In this tutorial, we will approach some basic sorting algorithms, i.e., Selection sort, Bubble
sort, Insertion sort, Merge sort, Quicksort; and use Java method to perform sorting.

1. Sorting Algorithms
We will focus on implementing Selection sort, Bubble sort, Insertion sort and un-
derstand the main ideas of Merge sort and Quick sort.

1.1. Selection sort

The algorithm involves finding the minimum or maximum element in the unsorted
portion of the array and then placing it in the correct position of the array. In this tutorial,
we implement Selection sort by finding the minimum element in the unsorted portion of
the array.
Given an array of n items

1. Find the index of the smallest unsorted item.

2. Swap the current item with the smallest unsorted one.

3. Exclude the smallest item which we found in step 2 and go to step 1.

[email protected] 1
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2020-2021

This is Selection Sort pseudocode:

SelectionSort(int a[])
Input: array 𝑎[0], ..., 𝑎[𝑛 − 1]
Output: Sorted array
𝑛 ← 𝑎.𝑙𝑒𝑛𝑔𝑡ℎ
for 𝑖 ← 0, 𝑖 < 𝑛 − 1 do
// Find the minimum element in unsorted array
𝑚𝑖𝑛_𝑖𝑑𝑥 = 𝑖
for 𝑗 ← 𝑖 + 1, 𝑖 < 𝑛 do
if 𝑎[𝑗] < 𝑎[𝑚𝑖𝑛_𝑖𝑑𝑥] then
𝑚𝑖𝑛_𝑖𝑑𝑥 ← 𝑗
end
end
// Swap the found minimum element with the first element
𝑡𝑒𝑚𝑝 ← 𝑎[𝑚𝑖𝑛_𝑖𝑑𝑥]
𝑎[𝑚𝑖𝑛_𝑖𝑑𝑥] ← 𝑎[𝑖]
𝑎[𝑖] ← 𝑡𝑒𝑚𝑝
end

1.2. Bubble sort

Like selection sort, bubble sort is also a brute-force approach to the sorting problem.
The idea of bubble sort is to compare adjacent elements of the list and exchange them if
they are out of order. By doing it repeatedly, we end up ”bubbling up” the largest element
to the last position on the list. The next pass bubbles up the second largest element, and
so on, until after 𝑛 − 1 passes the list is sorted. Pass � (0 ≤ 𝑖 ≤ 𝑛 − 2) of bubble sort can
be represented by the following diagram:

This is Bubble Sort pseudocode:

BubbleSort(int a[])
Input: array 𝑎[0], ..., 𝑎[𝑛 − 1]
Output: Sorted array
𝑛 ← 𝑎.𝑙𝑒𝑛𝑔𝑡ℎ
for 𝑖 ← 0, 𝑖 < 𝑛 − 1 do
for 𝑗 ← 0, 𝑖 < 𝑛 − 𝑖 − 1 do
if 𝑎[𝑗] > 𝑎[𝑗 + 1] then
// Swap 𝑎[𝑗] and 𝑎[𝑗 + 1]
𝑡𝑒𝑚𝑝 ← 𝑎[𝑗]
𝑎[𝑗] ← 𝑎[𝑗 + 1]
𝑎[𝑗 + 1] ← 𝑡𝑒𝑚𝑝
end
end
end

[email protected] 2
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2020-2021

1.3. Insertion sort

The principle of the insertion sort is quite simple: Each successive element in the
array to be sorted is inserted into its proper place with respect to the other, already-
sorted elements. As with the previous sorts, we divide our array into a sorted part and an
unsorted part.
Initially, the sorted portion contains only one element: the first element in the array. Now
we take the second element in the array and put it into its correct place in the sorted part;
that is, values[0] and values[1] are in order with respect to each other. Now the value
in values[2] is put into its proper place, so values[0] . . values[2] are in order with
respect to each other. This process continues until all the elements have been sorted. The
following figure illustrates this process, which we describe in the following algorithm.

This is Insertion Sort pseudocode:

InsertionSort(int a[])
Input: array 𝑎[0], ..., 𝑎[𝑛 − 1]
Output: Sorted array
𝑛 ← 𝑎.𝑙𝑒𝑛𝑔𝑡ℎ
for 𝑖 ← 1, 𝑖 < 𝑛 do
𝑘𝑒𝑦 ← 𝑎[𝑖]
𝑗 ← 𝑖−1
while 𝑗 ≥ 0 and 𝑎[𝑗] > 𝑘𝑒𝑦 do
𝑎[𝑗 + 1] ← 𝑎[𝑗]
𝑗 ← 𝑗−1
end
𝑎[𝑗 + 1] ← 𝑘𝑒𝑦
end

1.4. Merge Sort

The merge sort algorithm involves three steps:

• If the number of items to sort is 0 or 1, return.

• Recursively sort the first and second halves separately.

• Merge the two sorted halves into a sorted group.

The following figure illustrates a recursive merge sort algorithm used to sort an
array of 7 integer values. These are the steps a human would take to emulate merge sort
(top-down).

[email protected] 3
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2020-2021

This is the code which implement merge sort algorithm in Java:

1 private static void merge (int arr [], int l, int m, int r){
2 {
3 // Find sizes of two sub - arrays to be merged
4 int n1 = m - l + 1;
5 int n2 = r - m;
6 // Create temp arrays
7 int L[] = new int [n1 ];
8 int R[] = new int [n2 ];
9 // Copy data to temp arrays
10 for (int i = 0; i < n1; i++)
11 L[i] = arr[l + i];
12 for (int j = 0; j < n2; j++)
13 R[j] = arr[m + 1 + j];
14 /* Merge the temp arrays */
15 // Initial indexes of first and second sub - arrays
16 int i = 0, j = 0;
17 // Initial index of merged sub - array
18 int k = l;
19 while (i < n1 && j < n2)
20 {
21 if (L[i] <= R[j])
22 {
23 arr[k] = L[i];
24 i++;
25 }
26 else
27 {
28 arr[k] = R[j];

[email protected] 4
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2020-2021

29 j++;
30 }
31 k++;
32 }
33 // Copy remaining elements of L[] if any
34 while (i < n1)
35 {
36 arr[k] = L[i];
37 i++;
38 k++;
39 }
40 // Copy remaining elements of R[] if any
41 while (j < n2)
42 {
43 arr[k] = R[j];
44 j++;
45 k++;
46 }
47 }
48
49
50 // Main function of merge sort that sorts arr[ first .. last] using
merge () method
51 public static void mergeSort (int [] arr , int first , int last)
52 {
53 if (first < last)
54 {
55 // Find the middle point
56 int middle = ( first + last)/2;
57 // Sort first and second halves
58 mergeSort (arr , first , middle );
59 mergeSort (arr , middle + 1, last);
60 // Merge the sorted halves
61 merge (arr , first , middle , last);
62 }
63 }
64

1.5. Quick sort

Quicksort is a divide-and-conquer algorithm. Quicksort first divides a large array
into two smaller subarrays: the low elements and the high elements. Quicksort can then
recursively sort the sub-arrays. The steps are:
• Pick an element, called a pivot, from the array.
• Partitioning: reorder the array so that all elements with values less than the pivot
come before the pivot, while all elements with values greater than the pivot come
after it (equal values can go either way). After this partitioning, the pivot is in its
final position. This is called the partition operation.
• Recursively apply the above steps to the sub-array of elements with smaller values
and separately to the sub-array of elements with greater values.
The base case of the recursion is arrays of size zero or one, which are in order by
definition, so they never need to be sorted.

[email protected] 5
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2020-2021

The pivot selection and partitioning steps can be done in several different ways; the choice
of specific implementation schemes greatly affects the algorithm’s performance.
The following figure illustrates the quicksort algorithm. The shaded element is the pivot.
It is always chosen as the last element of the partition. However, always choosing the last
element in the partition as the pivot in this way results in poor performance, 𝑂(𝑛2 ), on
already sorted arrays, or arrays of identical elements.

Implementation of quick sort algorithm in Java:

Notice: there are many ways to pick the pick the pivot, in this example code we will pick
the high position to make the pivot
1 /* This function takes last element as pivot , places the pivot
element at its correct position in sorted array , and places all
smaller ( smaller than pivot ) to left of pivot and all greater
elements to right of pivot */
2

3 private static int partition (int [] arr , int low , int high)
4 {
5 int pivot = arr[high ];
6 // index of smaller element
7 int i = (low - 1);
8 for (int j = low; j < high; j++)
9 {
10 // If current element is smaller than or equal to pivot
11 if (arr[j] <= pivot )
12 {

[email protected] 6
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2020-2021

13 i++;
14 // swap arr[i] and arr[j]
15 int temp = arr[i];
16 arr[i] = arr[j];
17 arr[j] = temp;
18 }
19 }
20 // swap arr[i+1] and arr[high] (or pivot )
21 int temp = arr[i+1];
22 arr[i+1] = arr[high ];
23 arr[high] = temp;
24 return i+1;
25 }
26
27 // The main function that implements QuickSort algorithm
28 // arr [] --> Array to be sorted ,
29 // low --> Starting index ,
30 // high --> Ending index
31 public static void QuickSort (int [] arr , int low , int high)
32 {
33 if (low < high)
34 {
35 // pi is partitioning index , arr[pi] is now at right place
36 int pi = partition (arr , low , high);
37 // Recursively sort elements before partition and after
partition
38 QuickSort (arr , low , pi - 1);
39 QuickSort (arr , pi + 1, high);
40 }
41 }

2. Using Java method to perform sorting

In this section, we’ll shows the use of java.util.Comparator to sort a Java object
based on its property value.
The following example program will illustrate how-to use Comparator to sort an array of
objects on different attributes. The example is organized as follows:

• Define Fraction class;

• Then, define FractionComparator class to implement the Comparator interface

and it will be used to sort an array of Fraction;

• Finally, define Test.java to test the program.

2.1. Fraction class

1 public class Fraction {

2 private int num;
3 private int denom ;
4
5 public Fraction ()
6 {
7 this.num = 0;

[email protected] 7
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2020-2021

8 this. denom = 1;
9 }
10
11 public Fraction (int num , int denom )
12 {
13 this.num = num;
14 this. denom = denom ;
15 }
16
17 public double getRatio ()
18 {
19 return ( double ) this.num / this.denom ;
20 }
21
22 @Override
23 public String toString ()
24 {
25 return this.num + "/" + this.denom ;
26 }
27 }

2.2. FractionComparator class

1 import java.util. Comparator ;

2 public class FractionComparator implements Comparator {
3 @Override
4 public int compare ( Object o1 , Object o2)
5 {
6 Fraction f1 = ( Fraction ) o1;
7 Fraction f2 = ( Fraction ) o2;
8
9 // for ascending order
10 double ratio = f1. getRatio () - f2. getRatio ();
11
12 if(ratio > 0) return 1;
13 if(ratio < 0) return -1;
14 return 0;
15 }
16 }

2.3. Test.java program

1 import java.util. Arrays ;

2

3 public class Test {

4 public static void print ( Fraction [] arr) {
5 for( Fraction f : arr) {
6 System .out. print (f + "\t");
7 }
8 System .out. println ();
9 }
10 public static void main( String [] args) {
11 Fraction [] fractions = new Fraction [5];
12 fractions [0] = new Fraction (5, 6);

[email protected] 8
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2020-2021

13 fractions [1] = new Fraction (1, 2);

14 fractions [2] = new Fraction (7, 3);
15 fractions [3] = new Fraction (3, 5);
16 fractions [4] = new Fraction (2, 3);
17
18 print ( fractions );
19
20 Arrays .sort(fractions , new FractionComparator ());
21
22 print ( fractions );
23 }
24 }

3. Exercise

Exercise 1
Implement all sorting algorithms presented in this tutorial. (focus on implementing
code of Selection sort, Bubble sort, Insertion sort from their pseudocode)

Exercise 2
Applying the java.util.Comparator to sort a list of Student by the average grade in
ascending and descending order. The attributes of Student:

• Student’s name: name (String);

• Student’s grade: mathematics, programming, DSA1 (double).

• Student’s average grade: 𝑎𝑣𝑔 = 31 (𝑚𝑎𝑡ℎ𝑒𝑚𝑎𝑡𝑖𝑐𝑠 + 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑚𝑖𝑛𝑔 + 𝐷𝑆𝐴1)

[email protected] 9