The sorting algorithm affects application performance because CPU and memory resources are consumed depending on the algorithm and the size and characteristics of the dataset. The developer must choose the right algorithm for the data because the dataset has individual characteristics. The developer analyzes data and then chooses a sorting algorithm.
Problem
The client has reported to the development team that upon clicking the sort button in the application, there is a significant delay in displaying the data table on the screen.
Discussion
The development team analyzed a problem and found that the default sort algorithm and the size of the dataset were the issue. Affects the performance of the application significantly.
Implementation
The developer team decided to change the sort algorithm and query statement to reduce the dataset fetch from the database.
The development team expected that this solution would solve a problem.
How do you find out if it works or not? The development team must experiment with various datasets within the application.
Explore some of the most commonly used sorting algorithms
Bubble Sort
- Description: Bubble sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
- Efficiency: Bubble sort has a time complexity of O(n²), making it inefficient for large datasets.
- Best Use Case: Bubble sort is useful for educational purposes or for sorting small datasets due to its simplicity.
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array:"+ Arrays.toString(arr));
bubbleSort(arr);
System.out.println("Sorted array:"+ Arrays.toString(arr));
}
// Bubble Sort function
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
System.out.println("Pass "+(i+1)+":");
for (int j = 0; j < n-i-1; j++) {
// Swap if current element is greater than the next element
System.out.println("Comparing "+arr[j]+" and "+arr[j+1]+": "+Arrays.toString(arr));
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}Original array:[64, 34, 25, 12, 22, 11, 90] Pass 1: Comparing 64 and 34: [64, 34, 25, 12, 22, 11, 90] Comparing 64 and 25: [34, 64, 25, 12, 22, 11, 90] Comparing 64 and 12: [34, 25, 64, 12, 22, 11, 90] Comparing 64 and 22: [34, 25, 12, 64, 22, 11, 90] Comparing 64 and 11: [34, 25, 12, 22, 64, 11, 90] Comparing 64 and 90: [34, 25, 12, 22, 11, 64, 90] Pass 2: Comparing 34 and 25: [34, 25, 12, 22, 11, 64, 90] Comparing 34 and 12: [25, 34, 12, 22, 11, 64, 90] Comparing 34 and 22: [25, 12, 34, 22, 11, 64, 90] Comparing 34 and 11: [25, 12, 22, 34, 11, 64, 90] Comparing 34 and 64: [25, 12, 22, 11, 34, 64, 90] Pass 3: Comparing 25 and 12: [25, 12, 22, 11, 34, 64, 90] Comparing 25 and 22: [12, 25, 22, 11, 34, 64, 90] Comparing 25 and 11: [12, 22, 25, 11, 34, 64, 90] Comparing 25 and 34: [12, 22, 11, 25, 34, 64, 90] Pass 4: Comparing 12 and 22: [12, 22, 11, 25, 34, 64, 90] Comparing 22 and 11: [12, 22, 11, 25, 34, 64, 90] Comparing 22 and 25: [12, 11, 22, 25, 34, 64, 90] Pass 5: Comparing 12 and 11: [12, 11, 22, 25, 34, 64, 90] Comparing 12 and 22: [11, 12, 22, 25, 34, 64, 90] Pass 6: Comparing 11 and 12: [11, 12, 22, 25, 34, 64, 90] Sorted array:[11, 12, 22, 25, 34, 64, 90]
Selection Sort
- Description: The selection sort divides the input list into sorted and unsorted sublists. It repeatedly selects the smallest (or largest) element from the unsorted sublist and moves it to the sorted sublist.
- Efficiency: The selection sort also has a time complexity of O(n²), making it inefficient for large datasets.
- Best Use Case: Similar to bubble sort, selection sort is suitable for small datasets or situations where memory usage is a concern.
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array:"+ Arrays.toString(arr));
selectionSort(arr);
System.out.println("Sorted array:"+ Arrays.toString(arr));
}
// Selection Sort function
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
System.out.println("\nPass " + (i + 1) + ":");
int minIndex = i;
System.out.println("Selected element at index " + minIndex + ": " + arr[minIndex]);
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
System.out.println("New minimum element found at index " + minIndex + ": " + arr[minIndex]);
}
}
if (minIndex != i) {
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
System.out.println("Swapping elements: " + arr[i] + " and " + arr[minIndex]);
} else {
System.out.println("No need to swap. Minimum element already at index " + minIndex);
}
}
}
}Original array:[64, 34, 25, 12, 22, 11, 90] Pass 1: Selected element at index 0: 64 New minimum element found at index 1: 34 New minimum element found at index 2: 25 New minimum element found at index 3: 12 New minimum element found at index 5: 11 Swapping elements: 11 and 64 Pass 2: Selected element at index 1: 34 New minimum element found at index 2: 25 New minimum element found at index 3: 12 Swapping elements: 12 and 34 Pass 3: Selected element at index 2: 25 New minimum element found at index 4: 22 Swapping elements: 22 and 25 Pass 4: Selected element at index 3: 34 New minimum element found at index 4: 25 Swapping elements: 25 and 34 Pass 5: Selected element at index 4: 34 No need to swap. Minimum element already at index 4 Pass 6: Selected element at index 5: 64 No need to swap. Minimum element already at index 5 Sorted array:[11, 12, 22, 25, 34, 64, 90]
Insertion Sort
- Description: Insertion sort builds the final sorted list one element at a time. It iterates over the input list, removing one element and inserting it into the correct position in the sorted sublist.
- Efficiency: Insertion sort has an average and worst-case time complexity of O(n²), but it can be efficient for small datasets and nearly sorted lists.
- Best Use Case: Insertion sort is often used in scenarios where the input list is already partially sorted or when the list size is small.
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array:"+ Arrays.toString(arr));
insertionSort(arr);
System.out.println("Sorted array:"+ Arrays.toString(arr));
}
// Insertion Sort function
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
System.out.println("\nPass " + i + ":");
int key = arr[i];
System.out.println("Current element to insert: " + key);
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
System.out.println("Inserted element " + key + " at index " + (j + 1));
}
}
}Original array:[64, 34, 25, 12, 22, 11, 90] Pass 1: Current element to insert: 34 Inserted element 34 at index 0 Pass 2: Current element to insert: 25 Inserted element 25 at index 0 Pass 3: Current element to insert: 12 Inserted element 12 at index 0 Pass 4: Current element to insert: 22 Inserted element 22 at index 1 Pass 5: Current element to insert: 11 Inserted element 11 at index 0 Pass 6: Current element to insert: 90 Inserted element 90 at index 6 Sorted array:[11, 12, 22, 25, 34, 64, 90]
Merge Sort
- Description: Merge sort is a divide-and-conquer algorithm that recursively divides the input list into smaller sublists, sorts them independently, and then merges them in the correct order.
- Efficiency: Merge sort has a time complexity of O(n log n) in all cases, making it efficient for large datasets.
- Best Use Case: Merge sort is suitable for sorting large datasets and is often used as the basis for more advanced sorting algorithms.
public class MergeSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array:"+ Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:"+ Arrays.toString(arr));
}
// Merge Sort function
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
System.out.println("\nSplitting array from index " + left + " to " + right);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
// Merge function
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data to temporary arrays L[] and R[]
for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}
// Merge the temporary arrays back into arr[l..r]
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
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++;
}
System.out.println("Merging from index " + left + " to " + right);
System.out.println(Arrays.toString(arr));
}
}Original array:[64, 34, 25, 12, 22, 11, 90] Splitting array from index 0 to 6 Splitting array from index 0 to 3 Splitting array from index 0 to 1 Merging from index 0 to 1 [34, 64, 25, 12, 22, 11, 90] Splitting array from index 2 to 3 Merging from index 2 to 3 [34, 64, 12, 25, 22, 11, 90] Merging from index 0 to 3 [12, 25, 34, 64, 22, 11, 90] Splitting array from index 4 to 6 Splitting array from index 4 to 5 Merging from index 4 to 5 [12, 25, 34, 64, 11, 22, 90] Merging from index 4 to 6 [12, 25, 34, 64, 11, 22, 90] Merging from index 0 to 6 [11, 12, 22, 25, 34, 64, 90] Sorted array:[11, 12, 22, 25, 34, 64, 90]
Quick Sort
- Description: Quick sort is a divide-and-conquer algorithm that partitions the input list into two sublists based on a pivot element. It then recursively sorts the sublists.
- Efficiency: Quick sort has an average-case time complexity of O(n log n), but can degrade to O(n²) in the worst case.
- Best Use Case: Quick sort is widely used in practice due to its efficiency and is often the default choice for sorting.
public class QuickSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array:" + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:" + Arrays.toString(arr));
}
// Quick Sort function
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// Partition the array, arr[pivot] is now at its correct position
int pivotIndex = partition(arr, low, high);
System.out.println("\nPivot element " + arr[pivotIndex] + " is now at index " + pivotIndex);
// Recursively sort elements before and after partition
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
// Partition function
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
System.out.println("Swap " + arr[i] + " and " + arr[j] + " : " + Arrays.toString(arr));
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (or pivot)
System.out.println("Swap " + arr[i+1] + " and " + arr[high] + " : " + Arrays.toString(arr));
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}Original array:[64, 34, 25, 12, 22, 11, 90] Swap 64 and 64 : [64, 34, 25, 12, 22, 11, 90] Swap 34 and 34 : [64, 34, 25, 12, 22, 11, 90] Swap 25 and 25 : [64, 34, 25, 12, 22, 11, 90] Swap 12 and 12 : [64, 34, 25, 12, 22, 11, 90] Swap 22 and 22 : [64, 34, 25, 12, 22, 11, 90] Swap 11 and 11 : [64, 34, 25, 12, 22, 11, 90] Swap 90 and 90 : [64, 34, 25, 12, 22, 11, 90] Pivot element 90 is now at index 6 Swap 64 and 11 : [64, 34, 25, 12, 22, 11, 90] Pivot element 11 is now at index 0 Swap 34 and 34 : [11, 34, 25, 12, 22, 64, 90] Swap 25 and 25 : [11, 34, 25, 12, 22, 64, 90] Swap 12 and 12 : [11, 34, 25, 12, 22, 64, 90] Swap 22 and 22 : [11, 34, 25, 12, 22, 64, 90] Swap 64 and 64 : [11, 34, 25, 12, 22, 64, 90] Pivot element 64 is now at index 5 Swap 34 and 12 : [11, 34, 25, 12, 22, 64, 90] Swap 25 and 22 : [11, 12, 25, 34, 22, 64, 90] Pivot element 22 is now at index 2 Swap 34 and 25 : [11, 12, 22, 34, 25, 64, 90] Pivot element 25 is now at index 3 Sorted array:[11, 12, 22, 25, 34, 64, 90]
Heap Sort
- Description: Heap sort builds a heap data structure from the input list, then repeatedly extracts the maximum (or minimum) element from the heap and rebuilds the heap until the list is sorted.
- Efficiency: Heap sort has a time complexity of O(n log n) and is often used when space is limited.
- Best Use Case: Heap sort is suitable for sorting large datasets and is commonly used in embedded and operating systems.
public class HeapSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array:"+ Arrays.toString(arr));
heapSort(arr);
System.out.println("Sorted array:"+ Arrays.toString(arr));
}
// Heap Sort function
public static void heapSort(int[] arr) {
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
System.out.println("\nHeap created:");
System.out.println(Arrays.toString(arr));
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
System.out.println("\nSwapping " + arr[0] + " with " + arr[i]);
System.out.println("Heapifying root element...");
// Call max heapify on the reduced heap
heapify(arr, i, 0);
System.out.println("After heapifying:");
System.out.println(Arrays.toString(arr));
}
}
// To heapify a subtree rooted with node i which is an index in arr[]
public static void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2*i + 1
int right = 2 * i + 2; // right = 2*i + 2
System.out.println("\nHeapifying node: " + arr[i]);
System.out.println("Current left child: " + (left < n ? arr[left] : "null"));
System.out.println("Current right child: " + (right < n ? arr[right] : "null"));
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
System.out.println("Swapping " + arr[i] + " with " + arr[largest]);
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
}Original array:[64, 34, 25, 12, 22, 11, 90] Heapifying node: 25 Current left child: 11 Current right child: 90 Swapping 25 with 90 [64, 34, 90, 12, 22, 11, 25] Heapifying node: 25 Current left child: null Current right child: null Heapifying node: 34 Current left child: 12 Current right child: 22 Heapifying node: 64 Current left child: 34 Current right child: 90 Swapping 64 with 90 [90, 34, 64, 12, 22, 11, 25] Heapifying node: 64 Current left child: 11 Current right child: 25 Heap created: [90, 34, 64, 12, 22, 11, 25] Swapping 25 with 90 Heapifying root element... Heapifying node: 25 Current left child: 34 Current right child: 64 Swapping 25 with 64 [64, 34, 25, 12, 22, 11, 90] Heapifying node: 25 Current left child: 11 Current right child: null After heapifying: [64, 34, 25, 12, 22, 11, 90] Swapping 11 with 64 Heapifying root element... Heapifying node: 11 Current left child: 34 Current right child: 25 Swapping 11 with 34 [34, 11, 25, 12, 22, 64, 90] Heapifying node: 11 Current left child: 12 Current right child: 22 Swapping 11 with 22 [34, 22, 25, 12, 11, 64, 90] Heapifying node: 11 Current left child: null Current right child: null After heapifying: [34, 22, 25, 12, 11, 64, 90] Swapping 11 with 34 Heapifying root element... Heapifying node: 11 Current left child: 22 Current right child: 25 Swapping 11 with 25 [25, 22, 11, 12, 34, 64, 90] Heapifying node: 11 Current left child: null Current right child: null After heapifying: [25, 22, 11, 12, 34, 64, 90] Swapping 12 with 25 Heapifying root element... Heapifying node: 12 Current left child: 22 Current right child: 11 Swapping 12 with 22 [22, 12, 11, 25, 34, 64, 90] Heapifying node: 12 Current left child: null Current right child: null After heapifying: [22, 12, 11, 25, 34, 64, 90] Swapping 11 with 22 Heapifying root element... Heapifying node: 11 Current left child: 12 Current right child: null Swapping 11 with 12 [12, 11, 22, 25, 34, 64, 90] Heapifying node: 11 Current left child: null Current right child: null After heapifying: [12, 11, 22, 25, 34, 64, 90] Swapping 11 with 12 Heapifying root element... Heapifying node: 11 Current left child: null Current right child: null After heapifying: [11, 12, 22, 25, 34, 64, 90] Sorted array:[11, 12, 22, 25, 34, 64, 90]
In Java, the default sort algorithm used Collections.sort() for sorting objects that implement the Comparable interface is a modified version of merge sort called “TimSort.” Java provides various classes and methods for sorting data.
Sort Array
public static void timSort() {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
//Sort by Array
System.out.println("Original array:"+ Arrays.toString(arr));
Arrays.sort(arr);
System.out.println("Sorted array:"+ Arrays.toString(arr));
}Original array:[64, 34, 25, 12, 22, 11, 90] Sorted array:[11, 12, 22, 25, 34, 64, 90]
Sort the array list using the Collections class
public static void timSort() {
//Sort by ArrayList
List<Integer> list = new ArrayList<>(Arrays.asList(64, 34, 25, 12, 22, 11, 90));
System.out.println("Original list:"+ Arrays.toString(list.toArray()));
Collections.sort(list);
System.out.println("Sorted list:"+ Arrays.toString(list.toArray()));
}Original list:[64, 34, 25, 12, 22, 11, 90] Sorted list:[11, 12, 22, 25, 34, 64, 90]
Sort objects using the collections class
import lombok.Data;
import lombok.Getter;
import lombok.Setter;
@Getter
@Setter
@Data
public class UserProfile {
private String firstName;
private String lastName;
private int age;
public UserProfile(String firstName,String lastName, int age){
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
}
public static void timSort() {
List<UserProfile> profiles = new ArrayList<>();
profiles.add(new UserProfile("John", "Doe", 28));
profiles.add(new UserProfile("Alice", "Smith", 31));
profiles.add(new UserProfile("Bob", "Johnson", 45));
System.out.println("Before sorting:");
profiles.forEach(profile -> System.out.println(profile.toString()));
Collections.sort(profiles, Comparator.comparing(UserProfile::getFirstName));
System.out.println("\nAfter sorting by first name:");
profiles.forEach(profile -> System.out.println(profile.toString()));
}Before sorting: UserProfile(firstName=John, lastName=Doe, age=28) UserProfile(firstName=Alice, lastName=Smith, age=31) UserProfile(firstName=Bob, lastName=Johnson, age=45) After sorting by first name: UserProfile(firstName=Alice, lastName=Smith, age=31) UserProfile(firstName=Bob, lastName=Johnson, age=45) UserProfile(firstName=John, lastName=Doe, age=28)
Sort objects using the stream and the sorted method
import lombok.Data;
import lombok.Getter;
import lombok.Setter;
@Getter
@Setter
@Data
public class UserProfile {
private String firstName;
private String lastName;
private int age;
public UserProfile(String firstName,String lastName, int age){
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
}
public static void timSort() {
List<UserProfile> profiles = new ArrayList<>();
profiles.add(new UserProfile("John", "Doe", 28));
profiles.add(new UserProfile("Alice", "Smith", 31));
profiles.add(new UserProfile("Bob", "Johnson", 45));
System.out.println("Before sorting:");
profiles.forEach(profile -> System.out.println(profile.toString()));
profiles = profiles.stream().sorted(Comparator.comparing(UserProfile::getAge).reversed()).toList();
System.out.println("\nAfter sorting by age:");
profiles.forEach(profile -> System.out.println(profile.toString()));
}Before sorting: UserProfile(firstName=John, lastName=Doe, age=28) UserProfile(firstName=Alice, lastName=Smith, age=31) UserProfile(firstName=Bob, lastName=Johnson, age=45) After sorting by age: UserProfile(firstName=Bob, lastName=Johnson, age=45) UserProfile(firstName=Alice, lastName=Smith, age=31) UserProfile(firstName=John, lastName=Doe, age=28)
Finally
While sorting algorithms may not be directly implemented in every project, developers should learn them to broaden their skill set and deepen their understanding of software development principles. By understanding sorting algorithms’ underlying processes and complexities, developers can optimize application performance, enhance problem-solving abilities, and make informed decisions when designing and implementing software solutions.
