数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


Counting Sort Algorithm



Counting sort is an external sorting algorithm that assumes all the input values are integers that lie between the range 0 and k. Then mathematical computations on these input values to place them at the correct position in the output array.

This algorithm makes use of a counter to count the frequency of occurrence of the numbers and arrange them accordingly. Suppose, if a number ‘m’ occurs 5 times in the input sequence, the counter value of the number will become 5 and it is repeated 5 times in the output array.

Counting Sort Algorithm

The counting sort algorithm assumes that the input is relatively smaller so the algorithm is as follows −

Step 1 − Maintain two arrays, one with the size of input elements without repetition to store the count values and other with the size of the input array to store the output.

Step 2 − Initialize the count array with all zeroes and keep the output array empty.

Step 3 − Every time an element occurs in the input list, increment the corresponding counter value by 1, until it reaches the end of the input list.

Step 4 − Now, in the output array, every time a counter is greater than 0, add the element at its respective index, i.e. if the counter of ‘0’ is 2, ‘0’ added at the 2nd position (i.e. 1st index) of the output array. Then decrement the counter value by 1.

Step 5 − Repeat Step 4 until all the counter values become 0. The list obtained is the output list.

COUNTING-SORT(A, B, k)
let C[0 … k] be a new array
for i = 0 to k
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1

// C[i] now contains the number of elements equal to i.
for i = 1 to k
C[i] = C[i] + C[i – 1]
// C[i] now contains the number of elements less than or equal to i.
for j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j – 1]

Analysis

The average case time complexity for the counting sort algorithm is same as bucket sort. It runs in Θ(n) time.

Example

Consider an input list to be sorted, 0, 2, 1, 4, 6, 2, 1, 1, 0, 3, 7, 7, 9.

For easier computations, let us start with single digit numbers.

Step 1

Create two arrays: to store counters and the output. Initialize the counter array with zeroes.

create_two_arrays

Step 2

After incrementing all the counter values until it reaches the end of the input list, we achieve −

incrementing_all_counter

Step 3

Now, push the elements at the corresponding index in the output list.

push_elements

Step 4

Decrement the counter by 1 after adding the elements in the output array. Now, 1 is added at the 4th index.

Decrement_counter

Step 5

Add the remaining values preceding the index in previous step.

Add_remaining_values

Step 6

After adding the last values, we get −

adding_last_values

The final sorted output is achieved as 0, 0, 1, 1, 1, 2, 2, 3, 4, 6, 7, 7, 9

Implementation

The counting sort implementation works closely with the algorithm where we construct an array to store the frequency of each element of the input array. Based on these frequencies, the elements are placed in the output array. Repetitive elements are also sorted in the counting sort algorithm.

Example

In this chapter, we look into the counting sort program implemented in four different programming languages.

#include<stdio.h>
int countingsort(int a[], int n){
   int i, j;
   int output[15], c[100];
   for (i = 0; i < 100; i++)
      c[i] = 0;
   for (j = 0; j < n; j++)
      ++c[a[j]];
   for (i = 1; i <= 99; i++)
      c[i] += c[i-1];
   for (j = n-1; j >= 0; j--) {
      output[c[a[j]] - 1] = a[j];
      --c[a[j]];
   }
   printf("
After sorting array elements are: ");
   for (i = 0; i<n; i++)
      printf("%d ", output[i]);
}
void main(){
   int n , i;
   int a[] = {12, 32, 44, 8, 16};
   n = sizeof(a) / sizeof(a[0]);
   printf("Before sorting array elements are: ");
   for(int i = 0; i<n; i++){
       printf("%d " , a[i]);
   }
   countingsort(a, n);
}

Output

Before sorting array elements are: 12 32 44 8 16 
After sorting array elements are: 8 12 16 32 44
#include<iostream>
using namespace std;
void countingsort(int a[], int n){
   int i, j;
   int output[15], c[100];
   for (i = 0; i < 100; i++)
      c[i] = 0;
   for (j = 0; j < n; j++)
      ++c[a[j]];
   for (i = 1; i <= 99; i++)
      c[i] += c[i-1];
   for (j = n-1; j >= 0; j--) {
      output[c[a[j]] - 1] = a[j];
      --c[a[j]];
   }
   cout << "
After sorting array elements are: ";
   for (i = 0; i <n; i++)
      cout << output[i] << " ";
}
int main(){
   int n , i;
   int a[] = {12, 32, 44, 8, 16};
   n = sizeof(a) / sizeof(a[0]);
   cout<<"Before sorting array elements are: ";
   for(int i = 0; i<n; i++){
       cout<<a[i]<<" ";
   }
   countingsort(a, n);
   cout << "
";
   return 0;
}

Output

Before sorting array elements are: 12 32 44 8 16 
After sorting array elements are: 8 12 16 32 44 
import java.io.*;
public class counting_sort {
   static void sort(int a[], int n) {
      int i, j;
      int output[] = new int[15];
      int c[] = new int[100];
      for (i = 0; i < 100; i++)
      c[i] = 0;
      for (j = 0; j < n; j++)
      ++c[a[j]];
      for (i = 1; i <= 99; i++)
      c[i] += c[i-1];
      for (j = n-1; j >= 0; j--) {
         output[c[a[j]] - 1] = a[j];
         --c[a[j]];
      }
      System.out.println("
After sorting array elements are: ");
      for (i = 0; i < n; ++i)
      System.out.print(output[i] + " ");
   }
   public static void main(String args[]){
      int a[] = {12, 32, 44, 8, 16};
      int n = a.length;
      System.out.println("Before sorting array elements are: ");
      for(int i = 0; i<n; i++){
          System.out.print(a[i] + " ");
      }
      // Function call
      sort(a, n);
   }
}

Output

Before sorting array elements are: 
12 32 44 8 16 
After sorting array elements are: 
8 12 16 32 44 
output = []
def counting_sort(a, n):
    output = [0] * n
    c = [0] * 100
    for i in range(100):
        c[i] = 0
    for j in range(n):
        c[a[j]] += 1
    for i in range(1, 99):
        c[i] += c[i-1]
    for j in range(n-1, -1, -1):
        output[c[a[j]] - 1] = a[j]
        c[a[j]] -= 1
    print("After sorting array elements are: ")
    print(output)
a = [12, 32, 44, 8, 16]
n = len(a)
print("Before sorting array elements are: ")
print (a)
counting_sort(a, n)

Output

Before sorting array elements are: 
[12, 32, 44, 8, 16]
After sorting array elements are: 
[8, 12, 16, 32, 44]