Write a program in Java that performs the Counting Sort algorithm. a) Create the

Question

Write a program in Java that performs the Counting Sort algorithm. a) Create the countingSort method. Use the pseudocode shown in the lecture. b) Test your codes by writing a program that uses the following input array: int[] array_A = {6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2}; c) Your output should display the following versions of the arrays: I. The original input array A II. The counting array C after the counting (lines 4-5 in pseudocode) has completed III. The counting array C after the summing (lines 7-8 in pseudocode) has completed IV. The final sorted array B after performing the Counting Sort algorithm

Explanation / Answer

import java.util.Scanner;

public class Count_Sort

{

    private static final int MAX_RANGE = 1000000;
    public static void sort( int[] arr )

    {

        int N = arr.length;

        if (N == 0)

            return;

        /** find max and min values **/

        int max = arr[0], min = arr[0];

        for (int i = 1; i < N; i++)

        {

            if (arr[i] > max)

                max = arr[i];

            if (arr[i] < min)

                min = arr[i];

        }

        int range = max - min + 1;

        if (range > MAX_RANGE)

        {

            System.out.println(" Error : Range too large for sort");

            return;

        }
       int[] count = new int[range];

        for (int i = 0; i < N; i++)

            count[arr[i] - min]++;

        for (int i = 1; i < range; i++)

            count[i] += count[i - 1];

        int j = 0;

        for (int i = 0; i < range; i++)

            while (j < count[i])

                arr[j++] = i + min;

    }  

    public static void main(String[] args)

    {

        Scanner scan = new Scanner( System.in );      

        System.out.println("Counting Sort Test ");

        int n, i;

        /** Accept number of elements **/

        System.out.println("Enter number of integer elements");

        n = scan.nextInt();

        /** Create integer array on n elements **/

        int arr[] = new int[ n ];

        /** Accept elements **/

        System.out.println(" Enter "+ n +" integer elements");

        for (i = 0; i < n; i++)

            arr[i] = scan.nextInt();

        sort(arr);

        /** Print sorted Array **/

        System.out.println(" Elements after sorting ");      

        for (i = 0; i < n; i++)

            System.out.print(arr[i]+" ");          

        System.out.println();                   

    }  

}

A)

funcition count_sort()

int[] array_A = {6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2}
for i in 0 to (K - 1)
    counts[i] = 0

for each input student s
    counts[array_A] = counts[array_A] + 1

// up to this line, it is identical to the rapid sort.

sum = 0
for i in 0 to (K - 1)
    sum = sum + counts[i] // accumulate sum
    counts[i] = sum // convert counts[] array to a "cumulative sum"

// second pass through the original data
for each input student s starting from the last student
    index = counts[array_A]
    assert( 0 < counts[array_A] )
    counts[array_A] = counts[array_A] - 1
    assert( 0 <= counts[array_A] )
    sorted_students[index] = s
  
    end

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.