Java Algorithms
In Java, algorithms form the backbone of efficient software development. An algorithm is a step-by-step procedure or formula for solving a problem. Java, being a general-purpose programming language, offers a vast array of built-in algorithms and data structures to solve different computational problems efficiently.
Whether you're working on basic tasks like sorting and searching or complex tasks like dynamic programming or graph algorithms, Java provides the tools and libraries to implement these algorithms effectively.
Java algorithms can be broadly classified into the following categories:
Sorting is one of the most fundamental operations in computer science. It is used in almost every application, from organizing data to improving the performance of other algorithms.
Bubble Sort:
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
bubbleSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
QuickSort:
public class QuickSort {
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);
}
}
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;
}
public static void main(String[] args) {
int[] arr = {10, 80, 30, 90, 40, 50, 70};
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
3. Merge Sort:
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
System.arraycopy(arr, left, leftArray, 0, n1);
System.arraycopy(arr, mid + 1, rightArray, 0, n2);
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
Searching algorithms are used to locate an element in a data structure, such as an array or a list.
Binary Search:
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if the target is at mid
if (arr[mid] == target) {
return mid;
}
// If the target is greater, ignore the left half
if (arr[mid] < target) {
low = mid + 1;
}
// If the target is smaller, ignore the right half
else {
high = mid - 1;
}
}
return -1; // Element not found
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13};
int target = 7;
int result = binarySearch(arr, target);
System.out.println("Element found at index: " + result);
}
}
Graphs are a fundamental data structure in computer science, representing a collection of nodes (vertices) and edges connecting pairs of nodes. Java provides various algorithms to work with graphs.
import java.util.*;
public class DFS {
private Map<Integer, List<Integer>> adjList;
public DFS() {
adjList = new HashMap<>();
}
public void addEdge(int v, int w) {
adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
}
public void dfs(int start) {
Set<Integer> visited = new HashSet<>();
dfsHelper(start, visited);
}
private void dfsHelper(int v, Set<Integer> visited) {
visited.add(v);
System.out.print(v + " ");
for (int neighbor : adjList.getOrDefault(v, Collections.emptyList())) {
if (!visited.contains(neighbor)) {
dfsHelper(neighbor, visited);
}
}
}
public static void main(String[] args) {
DFS graph = new DFS();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 6);
System.out.print("DFS Traversal: ");
graph.dfs(1);
}
}
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is especially useful for optimization problems.
public class Fibonacci {
public static int fibonacci(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {
int n = 10;
System.out.println("Fibonacci of " + n + " is: " + fibonacci(n));
}
}