java:algorithms:divide-and-conquer
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| java:algorithms:divide-and-conquer [2024/04/26 10:00] – removed - external edit (Unknown date) 127.0.0.1 | java:algorithms:divide-and-conquer [2024/04/26 10:00] (current) – ↷ Page name changed from java:algorithms:divide-et-impera to java:algorithms:divide-and-conquer odefta | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | ====== Divide and Conquer in Java ====== | ||
| + | Divide and Conquer is a fundamental algorithm design paradigm in computer science, used to solve various types of problems by dividing them into smaller subproblems, | ||
| + | |||
| + | ==== Core Concept ==== | ||
| + | The divide and conquer strategy works by: | ||
| + | - **Dividing** the problem into a number of subproblems that are smaller instances of the same problem. | ||
| + | - **Conquering** the subproblems by solving them recursively. If the subproblem sizes are small enough, solve them in a straightforward manner. | ||
| + | - **Combining** the solutions to the subproblems into the solution for the original problem. | ||
| + | |||
| + | ==== Common Applications ==== | ||
| + | - **Sorting algorithms** such as Quick Sort and Merge Sort. | ||
| + | - **Searching algorithms** like Binary Search. | ||
| + | - Complex number multiplication and other number-theoretic problems. | ||
| + | - Constructing data structures such as Binary Trees and Segment Trees. | ||
| + | |||
| + | ==== Example: Merge Sort in Java ==== | ||
| + | Merge Sort is a classic example of divide and conquer. | ||
| + | |||
| + | <code java MergeSort.java> | ||
| + | public class MergeSort { | ||
| + | // Merges two subarrays of arr[] | ||
| + | void merge(int arr[], int l, int m, int r) { | ||
| + | // Find sizes of two subarrays 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 subarrays | ||
| + | int i = 0, j = 0; | ||
| + | |||
| + | // Initial index of merged subarray array | ||
| + | int k = l; | ||
| + | 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++; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | // Main function that sorts arr[l..r] using merge() | ||
| + | void sort(int arr[], int l, int r) { | ||
| + | if (l < r) { | ||
| + | // Find the middle point | ||
| + | int m = (l + r) / 2; | ||
| + | |||
| + | // Sort first and second halves | ||
| + | sort(arr, l, m); | ||
| + | sort(arr, m + 1, r); | ||
| + | |||
| + | // Merge the sorted halves | ||
| + | merge(arr, l, m, r); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | </ | ||