basic-programs/Sorting/CountingSort.java at master · yodifm/basic-programs · GitHub

History

50 lines (39 loc) · 1.09 KB

Raw

// Program for implementation of counting sort in java

import java.util.Arrays;

class CountingSort {

void countSort(int array[], int size) {

int[] output = new int[size + 1];

int max = array[0];

for (int i = 1; i < size; i++) {

if (array[i] > max)

max = array[i];

}

int[] count = new int[max + 1];

// Initialize count array with all zeros.

for (int i = 0; i < max; ++i) {

count[i] = 0;

}

// Store the count of each element

for (int i = 0; i < size; i++) {

count[array[i]]++;

}

// Store the cummulative count of each array

for (int i = 1; i <= max; i++) {

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

}

for (int i = size - 1; i >= 0; i--) {

output[count[array[i]] - 1] = array[i];

count[array[i]]--;

}

for (int i = 0; i < size; i++) {

array[i] = output[i];

}

public static void main(String args[]) {

int[] data = { 4, 2, 2, 8, 3, 3, 1 };

int size = data.length;

CountingSort cs = new CountingSort();

cs.countSort(data, size);

System.out.println(Arrays.toString(data));

}

basic-programs/Sorting/CountingSort.java at master · yodifm/basic-programs · GitHub

Expand file tree

Breadcrumbs

CountingSort.java

Latest commit

History

Breadcrumbs

CountingSort.java

File metadata and controls