This article describes the differences between searching and sorting algorithms in Java, their distinct purposes, methodologies, and time complexities. It includes practical examples and implementations, such as Merge Sort for organizing data and Binary Search for efficient retrieval, demonstrating their roles in solving real-world problems.
Alexander S. Ricciardi
July 14, 2024
In Java, understanding searching and sorting algorithms and how they differ from each other, is crucial for the correct functionality of the application and for effectively managing data. While searching focuses on locating specific data within a collection, sorting rearranges data. This article explores their differences in purpose, methodology, and applications, by providing examples.
The major differences between searching and sorting in Java lie in their purposes and outputs, as well as their efficiencies and time complexities. Please Table 1 for a detailed comparison.
Table 1
Searching vs Sorting in Java
Choosing between different searching or sorting algorithms often depends on the purpose or output wanted and the specific requirements of your application, such as the size of the dataset, and whether the data is already sorted.
The following table, Table 2, gives examples of pseudocode and time complexity for several searches and sort algorithms:
Table 2
Runtime Complexities for Various Pseudocode Examples
Note: In Java without using the Comparable Interface the code above would only be viable for primitive types. From Programming in Java with ZyLabs , 18.3 O notation, Figure 18.3.2 by Lysecky, R., & Lizarraga, A. (2022).
An example of a sort algorithm is the merge sort, which has the divide-and-conquer approach, it recursively divides a data array into smaller subarrays and sorts those subarrays, then merges the subarrays together to create a sorted array (GeeksforGeeks, 2020a).An example of a search algorithm is the binary search; which operates on a pre-sorted array by repeatedly dividing the search interval in half until the target element is found or determined to be absent (GeeksforGeeks, 2020b).
The example below sorts using merge sort an ArrayList of book objects by year of publication then searches the sorted list using binary:Book.java
/**
* Book object with a title and publication year. This class implements
* Comparable to allow sorting based on the publication year.
*
* @author Alexander Ricciardi
* @version 1.0
* @date 07/14/2024
*/
class Book implements Comparable {
String title;
int year;
/**
* Constructs a new Book object.
*
* @param title The title of the book.
* @param year The year the book was published.
*/
public Book(String title, int year) {
this.title = title;
this.year = year;
}
/**
* Compares this book with another book based on the publication year.
*
* @param other The book to compare with.
* @return A negative integer, zero, or a positive integer as this book is less
* than, equal to, or greater than the specified book.
*/
@Override
public int compareTo(Book other) {
return Integer.compare(this.year, other.year);
}
/**
* Returns a string representation of the book.
*
* @return A string in the format "title (year)".
*/
@Override
public String toString() {
return title + " (" + year + ")";
}
}import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/**
* Sorts and search a list of books. It implements merge sort for sorting and
* binary search for searching.
*
* @author Alexander Ricciardi
* @version 1.0
* @date 07/14/2024
*/
public class BookSortingSearching {
/**
* The main method that demonstrates sorting and searching on a list of books.
*
* @param args Command line arguments (not used).
*/
public static void main(String[] args) {
// Initialize the list of books
ArrayList books = new ArrayList<>(
Arrays.asList(new Book("To Kill a Mockingbird", 1960),
new Book("1984", 1949),
new Book("The Great Gatsby", 1925),
new Book("One Hundred Years of Solitude", 1967),
new Book("The Catcher in the Rye", 1951),
new Book("Brave New World", 1932),
new Book("The Hobbit", 1937),
new Book("The Lord of the Rings", 1954),
new Book("Pride and Prejudice", 1813),
new Book("Animal Farm", 1945)
));
// Print the original list
System.out.println("Original list:");
books.forEach(System.out::println);
// Sort the books using merge sort
mergeSort(books, 0, books.size() - 1);
// Print the sorted list
System.out.println("\nSorted list by year:");
books.forEach(System.out::println);
// Perform binary search based on user input
Scanner scn = new Scanner(System.in);
System.out.print("\nEnter a year to search for: ");
int searchYear = scn.nextInt();
int result = binarySearch(books, searchYear);
if (result != -1) {
System.out.println("Book found: " + books.get(result));
} else {
System.out.println("No book found for the year " + searchYear);
}
scn.close();
}
/**
* Sorts the given list of books using the merge sort algorithm.
*
* @param books The list of books to sort.
* @param left The starting index of the subarray to sort.
* @param right The ending index of the subarray to sort.
*/
private static void mergeSort(ArrayList books, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(books, left, mid); // Sort left half
mergeSort(books, mid + 1, right); // Sort right half
merge(books, left, mid, right); // Merge the sorted halves
}
}
/**
* Merges two sorted subarrays of the books list.
*
* @param books The list of books containing the subarrays to merge.
* @param left The starting index of the left subarray.
* @param mid The ending index of the left subarray.
* @param right The ending index of the right subarray.
*/
private static void merge(ArrayList books, int left, int mid, int right) {
// Create temporary arrays
ArrayList leftList = new ArrayList<>(books.subList(left, mid + 1));
ArrayList rightList = new ArrayList<>(books.subList(mid + 1, right + 1));
int i = 0, j = 0, k = left;
// Merge the two lists
while (i < leftList.size() && j < rightList.size()) {
if (leftList.get(i).compareTo(rightList.get(j)) <= 0) {
books.set(k++, leftList.get(i++));
} else {
books.set(k++, rightList.get(j++));
}
}
// Copy remaining elements of leftList, if any
while (i < leftList.size()) {
books.set(k++, leftList.get(i++));
}
// Copy remaining elements of rightList, if any
while (j < rightList.size()) {
books.set(k++, rightList.get(j++));
}
}
/**
* Performs a binary search on the sorted list of books to find a book by its
* publication year.
*
* @param books The sorted list of books to search.
* @param year The publication year to search for.
* @return The index of the book if found, -1 otherwise.
*/
private static int binarySearch(ArrayList books, int year) {
int left = 0, right = books.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (books.get(mid).year == year) {
return mid; // Book found
}
if (books.get(mid).year < year) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}
return -1; // Book not found
}
}Output:
To Kill a Mockingbird (1960)
1984 (1949)
The Great Gatsby (1925)
One Hundred Years of Solitude (1967)
The Catcher in the Rye (1951)
Brave New World (1932)
The Hobbit (1937)
The Lord of the Rings (1954)
Pride and Prejudice (1813)
Animal Farm (1945)
Sorted list by year:
Pride and Prejudice (1813)
The Great Gatsby (1925)
Brave New World (1932)
The Hobbit (1937)
Animal Farm (1945)
1984 (1949)
The Catcher in the Rye (1951)
The Lord of the Rings (1954)
To Kill a Mockingbird (1960)
One Hundred Years of Solitude (1967)
Enter a year to search for: 1951
Book found: The Catcher in the Rye (1951)In other words, merge sort is efficient for sorting large sets of data due to its complexity of
O(n log(n)), while binary search with its targeted approach to search is better suited for machine learning applications, such as those for training neural networks or finding the optimal hyperparameters for a model.
In summary, searching and sorting algorithms have interconnected roles in programming but serve different purposes. Sorting algorithms like Merge Sort organize the data, allowing searching methods such as Binary Search to be more efficient. Together, these algorithms are indispensable for solving real-world problems, from data analysis to application development.
References
GeeksforGeeks. (2020a, November 18). Merge sort. GeeksforGeeks https://www.geeksforgeeks.org/merge-sort/
GeeksforGeeks. (2020b, February 3). Binary search. GeeksforGeeks. https://www.geeksforgeeks.org/binary-search/
Lysecky, R., & Lizarraga, A. (2022). Programming in Java with ZyLabs[ Table]. Zyante, Inc.
Comentarios