Clasificación rápida Radix de 3 vías en Java

Básicamente, como su nombre indica , 3-Way Radix Quicksort es una combinación de radix y 3-way quicksort. Es una ordenación híbrida que se encuentra entre Radix y Quicksort de 3 vías. Este algoritmo se utiliza principalmente para ordenar strings.

La idea principal detrás de la clasificación radix es usar los dígitos (comenzando desde LSD hasta MSD) de todos los números enteros para realizar un hash y dividirlos en una lista separada y unirlos. De la misma manera, usaremos el carácter MSD de las strings y luego usaremos estos caracteres para realizar lo que se conoce como clasificación rápida de 3 vías.

La ordenación rápida de 3 vías es básicamente un caso de ordenación rápida general solamente. La idea es que si usamos ordenación rápida, entonces puede haber una situación en la que obtendríamos los mismos caracteres en la array de caracteres (aquí estamos ordenando strings usando la idea de ordenación radix, para tomar todos los caracteres uno por uno para ordenar). 

Entonces, para manejar tal situación, dividimos la array en tres partes:

1. La partición contiene caracteres menores que el carácter pivote.
2. La partición para caracteres que son iguales a la del carácter pivote.
3. La última partición contiene caracteres que son mayores que el carácter pivote.

Así que básicamente lo que va a pasar es:

1. Consideraríamos el carácter MSD de cada string (la idea de ordenación radix).
2. Luego, realizaremos una clasificación rápida en esta array de caracteres, lo que dará como resultado la partición de la array en 3 partes (como se explicó anteriormente).

Esta división se muestra en la siguiente figura.

Explicación de la imagen: 

• Básicamente, como se muestra, hay 11 strings en la array y tenemos que ordenarlas. Entonces, considerando el primer carácter de todas las strings, se obtiene una array de {s,a,h,s,s,z,b,t,c,u,s}. Esta es la idea obtenida de radix sort. Ahora vamos a clasificar esta array de caracteres sobre la base de la idea de clasificación rápida.
• Así que aquí el elemento pivote que estamos considerando es el primer elemento de la array, es decir, ‘s’. Ahora estamos usando Quicksort para hacer particiones. Las particiones se realizan sobre la base de que:
• Primero estamos considerando el primer carácter como el pivote y también tenemos los punteros ‘i’ y ‘j’. El puntero ‘i’ se mueve de principio a fin y ‘j’ se mueve de principio a fin. Inicialmente i=1 yj =n-1; esto nos ayudaría a obtener el índice de dos límites de la segunda partición.
• Rangos de partición que serían primero uno forma 0 – i, segundo forma i+1 – j-1 y tercero forma j a n-1;

1. if arr[i]<pivot: el pivote se intercambia con arr[i] (tenga en cuenta que aquí se intercambian strings y no los caracteres de la string)
2. si arr[i]==pivot se queda allí solamente, y el puntero se incrementa al siguiente.
3. si arr[i]>pivot, la string en j se intercambia con la string arr[i] y j se reduce.

Entonces, después de realizar estas operaciones, obtendremos la array de tres particiones como se muestra.

Después de obtener las particiones, podemos ver que en la segunda no podemos realizar una ordenación rápida recursiva en el primer carácter de la string, ya que en esa partición todas las strings tienen el mismo primer carácter (aquí, en este ejemplo, es ‘s’) . Así que vamos a hacer una partición sobre la base del siguiente carácter. Y para los otros dos, volveremos a recordar el mismo tipo a partir del primer carácter. Esta es toda la idea sobre la ordenación rápida de 3 vías.

Lo principal aquí es notar que todas las strings no tienen la misma longitud, por lo que en algún paso podemos tener una condición de que no habrá más caracteres de la string pivote y otras strings tienen caracteres y, por lo tanto, se intercambian y comparan los caracteres. no son posibles en ese caso.

Entonces, para manejar ese caso, primero encontraríamos la longitud máxima de las strings en la array y luego agregaríamos a cada string un carácter que tenga un valor ASCII más pequeño que el alfabeto.

¿Por qué más pequeño? 

considere un ejemplo:

Array es un = {héroe, héroes, ella}

Aquí, si le damos a cada string con menos caracteres que la cantidad máxima necesaria (es decir, 6) un carácter que es mayor que los alfabetos (por ejemplo, ‘~’), entonces a se convertirá en ={héroe~~, héroes, ella~~~} .

ordenar esta array daría como resultado {héroes, héroe~~, ella~~~} pero la respuesta real debería ser {her, héroe, héroes}.

Realizar el algoritmo anterior de forma recursiva generará una array ordenada y, por lo tanto, podremos ordenar la array de strings.

Implementación recursiva:

// Java program for 3-Way Radix Quicksort
 
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Enumeration;
import java.util.Scanner;
import java.util.zip.ZipEntry;
import java.util.zip.ZipFile;
import java.util.zip.ZipInputStream;
 
public class GFG {
 
    // swapping method.
    public static void swp(String[] s, int x, int y)
    {
        String tmp = s[x];
        s[x] = s[y];
        s[y] = tmp;
    }
 
    // sort method.
    public static void srt(String[] s, int start, int last,
                           int character_index)
    {
        // base condition if no further index possible.
        if (start >= last)
            return;
 
        // first making a start pointer for dividing the
        // list from start to start_pointer.
        int start_pointer = start;
 
        // last_pointer and last are the boundaries for the
        // third list.
        int last_pointer = last;
 
        // taking the ascii value of the pivot at the index
        // given.
        int char_ascii_value_pivot
            = s[start].charAt(character_index);
 
        int pointer = start + 1;
 
        // starting a pointer to scan the whole array to
        // sort.
        while (pointer <= last) {
 
            // ASCII value of char at the position of all
            // the strings to compare with that of the pivot
            // char.
            int char_ascii_value_element
                = s[pointer].charAt(character_index);
 
            // if the element has char less than pivot than
            // swapping it with the top element and
            // incrementing the top boundary of the first
            // list.
            if (char_ascii_value_pivot
                > char_ascii_value_element) {
                swp(s, start_pointer, pointer);
                start_pointer++;
 
                // incrementing the pointer to check for
                // next string.
                pointer++;
            }
            else
 
                // if found larger character than it is
                // replaced by the element at last_pointer
                // and lower boundary is raised by
                // decrementing it.
                if (char_ascii_value_pivot
                    < char_ascii_value_element) {
                swp(s, last_pointer, pointer);
                last_pointer--;
                pointer++;
            }
 
            // if character is the same as that of the pivot
            // then no need to swap and move the pointer on
            else {
                pointer++;
            }
        }
 
        // now performing same sort on the first list
        // bounded by start and start_pointer with same
        // character_index
        srt(s, start, start_pointer - 1, character_index);
 
        // if we have more character left in the pivot
        // element than recall quicksort on the second list
        // bounded by  start_pointer and last_pointer and
        // next character_index.
        if (char_ascii_value_pivot >= 0)
 
            srt(s, start_pointer, last_pointer,
                character_index + 1);
 
        // lastly the third list with boundaries as
        // last_pointer and last.
        srt(s, last_pointer + 1, last, character_index);
    }
 
    public static void main(String[] args) throws Exception
    {
        // predefined array of five element all of same
        // length.
        String s[]
            = { "some", "same", "hero", "make", "zero" };
 
        // calling sort function to sort the array using
        // 3-way-radix-quicksort.
        srt(s, 0, 4, 0);
 
        // printing the sorted array;
        // here we are calling function by passing parameters
        // using references .
        for (int i = 0; i < 5; ++i)
            System.out.println(s[i]);
    }
}

hero
make
same
some
zero

Ejemplo 2: Ordenar strings con diferentes longitudes.

// Java program for 3-Way radix QuickSort
 
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Enumeration;
import java.util.Scanner;
import java.util.zip.ZipEntry;
import java.util.zip.ZipFile;
import java.util.zip.ZipInputStream;
 
public class GFG {
   
    // swapping method.
    public static void swp(String[] s, int x, int y)
    {
        String tmp = s[x];
        s[x] = s[y];
        s[y] = tmp;
    }
   
    // sort method.
    public static void srt(String[] s, int start, int last,
                           int character_index)
    {
        // base condition if no further index possible.
        if (start >= last)
            return;
       
        // first making a start pointer for dividing the
        // list from start to start_pointer.
        int start_pointer = start;
       
        // last_pointer and last are the boundaries for the
        // third list.
        int last_pointer = last;
       
        // taking the ASCII value of the pivot at the index
        // given.
        int char_ascii_value_pivot = s[start].charAt(character_index);
        int pointer = start + 1;
       
        // starting a pointer to scan the whole array to
        // sort.
        while (pointer <= last)
        {
            // ASCII value of char at the position of all
            // the strings to compare with that of the pivot
            // char.
            int char_ascii_value_element = s[pointer].charAt(character_index);
           
            // if the element has char less than pivot than
            // swapping it with the top element and
            // incrementing the top boundary of the first
            // list.
            if (char_ascii_value_pivot> char_ascii_value_element)
            {
                swp(s, start_pointer, pointer);
                start_pointer++;
               
                // incrementing the pointer to check for
                // next string.
                pointer++;
            }
            else
               
                // if found larger character than it is
                // replaced by the element at last_pointer
                // and lower boundary is raised by
                // decrementing it.
                if (char_ascii_value_pivot< char_ascii_value_element)
                {
                swp(s, last_pointer, pointer);
                last_pointer--;
                pointer++;
            }
           
            // if character is same as that of the pivot then
            // no need to swap and move the pointer on
            else
            {
                pointer++;
            }
        }
       
        // now performing same sort on the first list
        // bounded by start and start_pointer with same
        // character_index
        srt(s, start, start_pointer - 1, character_index);
       
        // if we have more character left in the pivot
        // element than recall quicksort on the second list
        // bounded by  start_pointer and last_pointer and
        // next character_index.
        if (char_ascii_value_pivot >= 0)
            srt(s, start_pointer, last_pointer,character_index + 1);
       
        // lastly the third list with boundaries as
        // last_pointer and last.
        srt(s, last_pointer + 1, last, character_index);
    }
 
    public static void main(String[] args) throws Exception
    {
        // predefined array of five element all of different
        // length.
        String s[] = { "sam", "same", "her", "make", "zebra" };
        int max_character_index = 0;
       
        // finding max_character_index
        for (int i = 0; i < 5; ++i)
            if (s[i].length() > max_character_index)
                max_character_index = s[i].length();
       
        // adding each string with a character having less
        // ascii value than alphabets.
        for (int i = 0; i < 5; ++i)
            if (s[i].length() < max_character_index)
                while (s[i].length() < max_character_index)
                    s[i] += '?';
 
        // calling sort function to sort the array using
        // 3-way-radix-quicksort.
        srt(s, 0, 4, 0);
 
        // printing the sorted array;
        // here we are calling function by passing
        // parameters using references . printing without the
        // appended character.
        for (int i = 0; i < 5; ++i)
        {
            String ans = "";
            for (int j = 0; j < s[i].length(); ++j)
                if (s[i].charAt(j) != '?')
                    ans += s[i].charAt(j);
                else
                    break;
 
            System.out.println(ans);
        }
    }
}

her
make
sam
same
zebra