In this exercise, you will create a Java program that implements advanced searching and sorting algorithms. The program should be able to search for an element in a list using **binary search** and sort a list of numbers using algorithms such as **quicksort** and **mergesort**. You will begin by implementing each of these algorithms, then test their efficiency by comparing runtime and accuracy on different data sets. This exercise will help you understand how to apply and optimize searching and sorting algorithms in Java to improve the performance of your programs.
This exercise will give you a solid understanding of how to implement and optimize advanced searching and sorting algorithms in Java, improving the performance of your programs through efficient data manipulation techniques.
import java.util.Arrays;
public class SearchSortAlgorithms {
// Binary Search Implementation
public static int binarySearch(int[] arr, int x) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1; // Element not found
}
// Quicksort Implementation
public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quicksort(arr, low, pivot - 1);
quicksort(arr, pivot + 1, high);
}
}
// Partition helper function for quicksort
private 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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// Mergesort Implementation
public static void mergesort(int[] arr) {
if (arr.length < 2) return;
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
mergesort(left);
mergesort(right);
merge(arr, left, right);
}
// Merge helper function for mergesort
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}
public static void main(String[] args) {
// List of numbers
int[] arr = {12, 4, 7, 9, 2, 5, 1, 8, 3, 6};
// Binary Search (only after sorting)
quicksort(arr, 0, arr.length - 1);
System.out.println("Sorted list: " + Arrays.toString(arr));
int x = 5;
int result = binarySearch(arr, x);
if (result == -1) {
System.out.println("Number " + x + " was not found in the list.");
} else {
System.out.println("Number " + x + " is found at index " + result);
}
// Mergesort
int[] arr2 = {12, 4, 7, 9, 2, 5, 1, 8, 3, 6};
mergesort(arr2);
System.out.println("Sorted list with Mergesort: " + Arrays.toString(arr2));
}
}
Output:
Sorted list: [1, 2, 3, 4, 5, 6, 7, 8, 9, 12]
Number 5 is found at index 4
Sorted list with Mergesort: [1, 2, 3, 4, 5, 6, 7, 8, 9, 12]
This program implements three key algorithms: **binary search**, **quicksort**, and **mergesort**. **Quicksort** and **mergesort** are advanced sorting algorithms, while **binary search** allows you to efficiently find an element in a sorted list. The output shows the sorted list and the location of a searched element within it.