QuickSort es una técnica de clasificación popular basada en el algoritmo divide y vencerás. En esta técnica, se elige un elemento como pivote y la array se divide a su alrededor. El objetivo de la partición es, dada una array y un elemento x de la array como pivote, colocar x en su posición correcta en una array ordenada y colocar todos los elementos más pequeños (menores que x) antes de x, y colocar todos los elementos mayores (mayores). que x) después de x.
Los subprocesos múltiples permiten la ejecución simultánea de dos o más partes de un programa para una utilización máxima de la CPU. Cada parte de dicho programa se llama hilo . Entonces, los hilos son procesos livianos dentro de un proceso.
Ejemplos:
Entrada: arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Salida: 1 2 3 4 5 6 7 8 9 10
Entrada: arr[] = {54, 64, 95, 82, 12, 32, 63}
Salida: 12 32 54 63 64 82 95
Enfoque: La idea principal del enfoque es:
- El hilo principal llama al método quicksort.
- El método divide la array y verifica la cantidad de subprocesos actuales.
- Se llama a nuevos subprocesos para el siguiente paso utilizando el mismo método paralelo.
- Utilice el método de clasificación rápida normal simple.
A continuación se muestra el programa que utiliza el grupo de subprocesos ForkJoinPool para mantener el mismo número de subprocesos que el número de CPU y reutilizar los subprocesos:
Java
// Java program for the above approach
import java.io.*;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
public class QuickSortMutliThreading
extends RecursiveTask<Integer> {
int start, end;
int[] arr;
/**
* Finding random pivoted and partition
* array on a pivot.
* There are many different
* partitioning algorithms.
* @param start
* @param end
* @param arr
* @return
*/
private int partition(int start, int end,
int[] arr)
{
int i = start, j = end;
// Decide random pivot
int pivoted = new Random()
.nextInt(j - i)
+ i;
// Swap the pivoted with end
// element of array;
int t = arr[j];
arr[j] = arr[pivote];
arr[pivote] = t;
j--;
// Start partitioning
while (i <= j) {
if (arr[i] <= arr[end]) {
i++;
continue;
}
if (arr[j] >= arr[end]) {
j--;
continue;
}
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
j--;
i++;
}
// Swap pivoted to its
// correct position
t = arr[j + 1];
arr[j + 1] = arr[end];
arr[end] = t;
return j + 1;
}
// Function to implement
// QuickSort method
public QuickSortMutliThreading(int start,
int end,
int[] arr)
{
this.arr = arr;
this.start = start;
this.end = end;
}
@Override
protected Integer compute()
{
// Base case
if (start >= end)
return null;
// Find partition
int p = partition(start, end, arr);
// Divide array
QuickSortMutliThreading left
= new QuickSortMutliThreading(start,
p - 1,
arr);
QuickSortMutliThreading right
= new QuickSortMutliThreading(p + 1,
end,
arr);
// Left subproblem as separate thread
left.fork();
right.compute();
// Wait untill left thread complete
left.join();
// We don't want anything as return
return null;
}
// Driver Code
public static void main(String args[])
{
int n = 7;
int[] arr = { 54, 64, 95, 82, 12, 32, 63 };
// Forkjoin ThreadPool to keep
// thread creation as per resources
ForkJoinPool pool
= ForkJoinPool.commonPool();
// Start the first thread in fork
// join pool for range 0, n-1
pool.invoke(
new QuickSortMutliThreading(
0, n - 1, arr));
// Print shorted elements
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
12 32 54 63 64 82 95
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vickyrathod y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA