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 13:00] – removed - external edit (Unknown date) 127.0.0.1 | java:algorithms:divide-and-conquer [2024/04/26 13: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); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ |