Particionamiento de tres vías utilizando el algoritmo de clasificación nacional holandés (versión de cambio de caja) en Java

Dada una lista de arreglos arr y valores lowVal y highVal . La tarea es dividir la array alrededor del rango de modo que la lista de arrays se divida en tres partes.

1) Todos los elementos más pequeños que lowVal van primero.
2) Todos los elementos en el rango lowVal a highVVal vienen a continuación.
3) Todos los elementos mayores que highVVal aparecen al final.
Los elementos individuales de tres conjuntos pueden aparecer en cualquier orden. Debe devolver la array organizada modificada.

Nota: Esta es una versión de cambio de caso del algoritmo de la bandera nacional holandesa que se utiliza para la partición de tres vías .

Ejemplos:

Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}  
        lowVal = 14, highVal = 20
Output: arr[] = {1, 5, 4, 2, 1, 3, 14, 20, 20, 98, 87, 32, 54}

Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}  
       lowVal = 20, highVal = 20       
Output: arr[] = {1, 14, 5, 4, 2, 1, 3, 20, 20, 98, 87, 32, 54} 

Algoritmo:

1. Creamos tres variables y las nombramos como low = 0, mid = 0, high = arr.size();
2. Ahora, atraviesa el arr dado hasta que mid sea menor o igual que high, es decir; medio ≤ alto .
3. Ahora cree otra variable como valor , aquí almacenaremos nuestra condición que se usa en caso de cambio .
4. Si arr.get(mid) <lowVal entonces almacenaremos 0 en el valor.
5. Si arr.get(mid) >= lowVal && arr.get(mid) ≤ highVal) entonces almacene 1 en el valor.
6. Si arr.get(mid) > highVal entonces almacenamos 2 en el valor.
7. Ahora verifique el valor en el interruptor.
8. Si es 0 , entonces intercambiamos elementos de una posición de medio a bajo y de bajo a medio del arr , es decir; Collections.swap (arr, mid, low) luego incremente tanto mid como low, es decir; medio++; bajo++; y finalmente romper.
9. Si es 1 , entonces no cambiamos los elementos de su posición porque los elementos satisfacen la segunda condición, es decir, si el elemento está entre lowVal y highVal, se mantiene como está. Solo intercambiamos elementos que cumplan solo la primera y la tercera condición de acuerdo con la declaración. Luego incremente mid ie; medio++; y finalmente, romper.
10. Si es 2 , intercambiamos elementos de una posición de media a alta y de alta a media del arr, es decir; Collections.swap(A, mid, high) luego incrementa mid y decrement high ie, mid++; alto-; y finalmente romper.
11. Por último, devuelva el ArrayList arr.

// Dutch National Sort algorithm
// using switch in Java
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    static ArrayList<Integer>
    threeWayPartition(ArrayList<Integer> arr, int lowVal,
                      int highVal)
    {
        // dutch national sort algorithm
        // using switch
        int low = 0, mid = 0, high = arr.size() - 1;
 
        while (mid <= high) {
 
            int value;
 
            // satisfying condition 1
            if (arr.get(mid) < lowVal)
                value = 0;
 
            // satisfying condition 2
            else if (arr.get(mid) >= lowVal
                     && arr.get(mid) <= highVal)
                value = 1;
 
            // satisfying condition 3
            else
                value = 2;
 
            switch (value) {
 
            // incase of first condition, do this
            case 0:
                Collections.swap(arr, mid, low);
                mid++;
                low++;
                break;
 
            // incase of second condition, do this
            case 1:
                mid++;
                break;
 
            // incase of third condition, do this
            case 2:
                Collections.swap(arr, mid, high);
                high--;
                break;
            }
        }
 
        // return the modified arraylist
        return arr;
    }
 
    public static void main(String[] args)
    {
 
        Scanner s = new Scanner(System.in);
 
        // create an empty arraylist
        ArrayList<Integer> a = new ArrayList<>();
 
        // add elements
        a.add(1);
        a.add(14);
        a.add(5);
        a.add(20);
        a.add(4);
        a.add(2);
        a.add(54);
        a.add(20);
        a.add(87);
        a.add(98);
        a.add(3);
        a.add(1);
        a.add(32);
 
        // stores the modified arraylist
        ArrayList<Integer> res
            = threeWayPartition(a, 14, 20);
 
        // Output the arraylist
        for (int i = 0; i < 13; i++)
            System.out.print(res.get(i) + " ");
    }
}

1 5 4 2 1 3 14 20 20 98 87 32 54 

• Complejidad de tiempo: O(n)
• Espacio Auxiliar: O(1)