$35
DS Lab 4 Sorting Solved
Lab 4
Sorting
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 understand 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.
dcquang@it.tdt.edu.vn 1 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
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, alreadysorted 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).
This is the code which implement merge sort algorithm in Java:
private static void merge(int arr[], int l, int m, int r){
{
// Find sizes of two sub-arrays to be merged int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays int L[] = new int [n1]; int R[] = new int [n2]; // Copy data to temp arrays for (int i = 0; i < n1; i++)
L[i] = arr[l + i]; for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays */
// Initial indexes of first and second sub-arrays int i = 0, j = 0;
// Initial index of merged sub-array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
} else
{
arr[k] = R[j];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
j++;
} k++;
}
// Copy remaining elements of L[] if any while (i < n1)
{
arr[k] = L[i];
i++; k++;
}
// Copy remaining elements of R[] if any while (j < n2)
{
arr[k] = R[j];
j++; k++;
}
}
// Main function of merge sort that sorts arr[first..last] using merge() method
public static void mergeSort(int[] arr, int first, int last)
{
if (first < last)
{
// Find the middle point int middle = (first + last)/2; // Sort first and second halves mergeSort(arr, first, middle); mergeSort(arr, middle + 1, last); // Merge the sorted halves
merge(arr, first, middle, last);
}
}
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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.
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
/* 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 */
private static int partition(int[] arr, int low, int high)
{
int pivot = arr[high]; // index of smaller element int i = (low - 1);
for (int j = low; j < high; j++)
{
// If current element is smaller than or equal to pivot if (arr[j] <= pivot)
{
1
2
3
4
5
6
7
8
9
10
11
12
i++;
// swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot) int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
return i+1;
}
// The main function that implements QuickSort algorithm
// arr[] -- Array to be sorted,
// low -- Starting index, // high -- Ending index public static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
// pi is partitioning index, arr[pi] is now at right place int pi = partition(arr, low, high);
// Recursively sort elements before partition and after partition
QuickSort(arr, low, pi - 1);
QuickSort(arr, pi + 1, high);
}
}
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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
public class Fraction { private int num; private int denom;
public Fraction()
{
this.num = 0;
1
2
3
4
5
6
7
}
this.denom = 1;
}
public Fraction(int num, int denom)
{
this.num = num;
this.denom = denom;
}
public double getRatio()
{
return (double) this.num / this.denom;
}
@Override public String toString()
{
return this.num + "/" + this.denom;
}
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2.2. FractionComparator class
import java.util.Comparator;
public class FractionComparator implements Comparator {
@Override public int compare(Object o1, Object o2)
{
Fraction f1 = (Fraction) o1;
Fraction f2 = (Fraction) o2;
// for ascending order
double ratio = f1.getRatio() - f2.getRatio();
if(ratio 0) return 1; if(ratio < 0) return -1;
return 0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2.3. Test.java program
import java.util.Arrays;
public class Test { public static void print(Fraction[] arr) { for(Fraction f : arr) {
System.out.print(f + "\t");
}
System.out.println();
}
public static void main(String[] args) { Fraction[] fractions = new Fraction[5]; fractions[0] = new Fraction(5, 6);
1
2
3
4
5
6
7
8
9
10
11
12
fractions[1] =
new
Fraction(1, 2);
fractions[2] =
new
Fraction(7, 3);
fractions[3] =
new
Fraction(3, 5);
fractions[4] =
new
Fraction(2, 3);
print(fractions);
Arrays.sort(fractions, new FractionComparator()); print(fractions);
}
}
13
14
15
16
17
18
19
20
21
22
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: 𝑎𝑣𝑔 = (𝑚𝑎𝑡ℎ𝑒𝑚𝑎𝑡𝑖𝑐𝑠 +𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑚𝑖𝑛𝑔 +𝐷𝑆𝐴1)
