CountingSortPractice

Ahora toca practicar!!

Primero crear nuestra función que ordenará el arreglo dado como entrada

   public static void sort(int[] arr) {

Luego necesitamos encontrar el valor máximo posible de nuestro arreglo

    int maxVal = getMaxValue(arr);

Para ello crearemos una función que nos ayude a hacerlo

    private static int getMaxValue(int[] arr) {
        int maxVal = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }
        return maxVal;
    }

Ahora crearemos dos arreglos de números, uno sera el que cuenta y otro será el que se ordene. Como pueden ver el arreglo que cuenta, su tamaño será uno más que el valoe máximo que se encuentra en el arreglo dado a ordenar.

    int[] counts = new int[maxVal + 1];
    int[] sortedArr = new int[arr.length];

Ahora crearemos un ciclo for donde llenamos nuestro arreglo que cuenta

        for (int i = 0; i < arr.length; i++) {
            counts[arr[i]]++;
        }

Luego creamos otro ciclo for que modifica el arreglo de conteo haciendo que cada elemento de cada índice almacene la suma de los recuentos anteriores. El array de conteo modificaado indica la posición de cada objeto en la secuencia de salida.

        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

Después creamos otro ciclo for con el cual vamos a hacer el ordenamiento.

        for (int i = 0; i <= arr.length- 1; i++) {
            sortedArr[counts[arr[i]]-1] = arr[i];
            counts[arr[i]]--;
        }

Acto seguidi copiamos el arreglo ordenado con el arreglo dado como entrada.

    System.arraycopy(sortedArr, 0, arr, 0, arr.length);

Finalmente creamos el main donde se pondrá el arreglo de entrada, se llame a la función de arreglo y se imprima

    public static void main(String[] args) {
        int[] arr = {1,4,1,2,7,5,2};
        CountingSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

Este debería ser le resultado:

import java.util.Arrays;

public class CountingSort {
    
    public static void sort(int[] arr) {
        //
        int maxVal = getMaxValue(arr);
        int[] counts = new int[maxVal + 1];
        int[] sortedArr = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            counts[arr[i]]++;
        }

        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        for (int i = 0; i <= arr.length- 1; i++) {
            sortedArr[counts[arr[i]]-1] = arr[i];
            counts[arr[i]]--;
        }

        System.arraycopy(sortedArr, 0, arr, 0, arr.length);
    }

    private static int getMaxValue(int[] arr) {
        int maxVal = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }
        return maxVal;
    }
    public static void main(String[] args) {
        int[] arr = {1,4,1,2,7,5,2};
        CountingSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Si quieres que el código en vez de ordenar números ordene caracteres se usa el siguiente código:

// Java implementation of Counting Sort

import java.io.*;

class CountingSort {
	void sort(char arr[])
	{
		int n = arr.length;

		// The output character array that will have sorted
		// arr
		char output[] = new char[n];

		// Create a count array to store count of individual
		// characters and initialize count array as 0
		int count[] = new int[256];
		for (int i = 0; i < 256; ++i)
			count[i] = 0;

		// store count of each character
		for (int i = 0; i < n; ++i)
			++count[arr[i]];

		// Change count[i] so that count[i] now contains
		// actual position of this character in output array
		for (int i = 1; i <= 255; ++i)
			count[i] += count[i - 1];

		// Build the output character array
		// To make it stable we are operating in reverse
		// order.
		for (int i = n - 1; i >= 0; i--) {
			output[count[arr[i]] - 1] = arr[i];
			--count[arr[i]];
		}

		// Copy the output array to arr, so that arr now
		// contains sorted characters
		for (int i = 0; i < n; ++i)
			arr[i] = output[i];
	}

	// Driver code
	public static void main(String args[])
	{
		CountingSort ob = new CountingSort();
		char arr[] = { 'g', 'e', 'e', 'k', 's', 'f', 'o',
					'r', 'g', 'e', 'e', 'k', 's' };

		// Function call
		ob.sort(arr);

		System.out.print("Sorted character array is ");
		for (int i = 0; i < arr.length; ++i)
			System.out.print(arr[i]);
	}
}
/*This code is contributed by Rajat Mishra */

Si quieres saber más sobre todo esto te dejo está página web

 https://www.geeksforgeeks.org/counting-sort/

y este video

 https://www.youtube.com/watch?v=7zuGmKfUt7s&ab_channel=GeeksforGeeks

fernandovs11 / countingsortpractice Goto Github PK

countingsortpractice's Introduction

CountingSortPractice

Ahora toca practicar!!

Primero crear nuestra función que ordenará el arreglo dado como entrada

Luego necesitamos encontrar el valor máximo posible de nuestro arreglo

Para ello crearemos una función que nos ayude a hacerlo

Ahora crearemos dos arreglos de números, uno sera el que cuenta y otro será el que se ordene. Como pueden ver el arreglo que cuenta, su tamaño será uno más que el valoe máximo que se encuentra en el arreglo dado a ordenar.

Ahora crearemos un ciclo for donde llenamos nuestro arreglo que cuenta

Luego creamos otro ciclo for que modifica el arreglo de conteo haciendo que cada elemento de cada índice almacene la suma de los recuentos anteriores. El array de conteo modificaado indica la posición de cada objeto en la secuencia de salida.

Después creamos otro ciclo for con el cual vamos a hacer el ordenamiento.

Acto seguidi copiamos el arreglo ordenado con el arreglo dado como entrada.

Finalmente creamos el main donde se pondrá el arreglo de entrada, se llame a la función de arreglo y se imprima

Este debería ser le resultado:

Si quieres que el código en vez de ordenar números ordene caracteres se usa el siguiente código:

Si quieres saber más sobre todo esto te dejo está página web

y este video

countingsortpractice's People

Contributors

Watchers

Recommend Projects

Recommend Topics

Recommend Org