GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Counting Sort Program for positive Integers · TORRYNN/Java_Learning@4362355

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • 18_Basic_Sorting_Algorithm
    • CountingSort.class
    • CountingSort.java
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎18_Basic_Sorting_Algorithm/CountingSort.class‎

Copy file name to clipboard
1.39 KB
Binary file not shown.
Collapse file

‎18_Basic_Sorting_Algorithm/CountingSort.java‎

Copy file name to clipboard
+51Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
2+
public class CountingSort {
3+
// This only works for postive values;
4+
public static void Csort(int arr[]) {
5+
int n = arr.length;
6+
int largest = Integer.MIN_VALUE;
7+
for (int i = 0; i < n; i++) {
8+
largest = Math.max(largest, arr[i]);
9+
}
10+
11+
int count[] = new int[largest + 1];
12+
for (int i = 0; i < n; i++) {
13+
count[arr[i]]++;
14+
}
15+
16+
17+
18+
// Sorting
19+
int j = 0;
20+
for (int i = 0; i <=largest; i++) {
21+
while (count[i] > 0) {
22+
arr[j] = i;
23+
j++;
24+
count[i]--;
25+
}
26+
}
27+
28+
}
29+
// Time Complexity:
30+
// Finding the largest element: O(n)
31+
// Populating the count array: O(n)
32+
// Reconstructing the sorted array: O(n+k), where k is the largest element.
33+
// Overall: O(n+k)
34+
35+
// Space Complexity:
36+
// The count array: O(k)
37+
// Overall: O(k)
38+
39+
public static void main(String[] args) {
40+
int ar[] = { 5, 4, 1, 3, 2 };
41+
for (int num : ar) {
42+
System.out.print(num + " ");
43+
}
44+
System.out.println();
45+
Csort(ar);
46+
for (int num : ar) {
47+
System.out.print(num + " ");
48+
}
49+
}
50+
51+
}

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.