Counting sort

From Algorithm wiki

Jump to: navigation, search
Related content:


Contents

[edit] Pseudocode 

This section needs your Code!

COUNTING-SORT(A, B, k)
1    for i ← 0 to k
2      do C[i] ← 0
3    for j ← 1 to length[A]
4      do C[A[j]] ← C[A[j]] + 1
5 ▹ C[i] now contains the number of elements equal to i.
6    for i ← 1 to k
7      do C[i] ← C[i] + C[i - 1]
8 ▹ C[i] now contains the number of elements less than or equal to i.
9    for j ← length[A] downto 1
10     do B[C[A[j]]] ← A[j]
11        C[A[j]] ← C[A[j]] - 1

[edit] C Code 

void counting_sort(int *array, int size)
{
  int i, min, max;
 
  min = max = array[0];
  for(i = 1; i < size; i++) {
    if (array[i] < min)
      min = array[i];
    else if (array[i] > max)
      max = array[i];
  }
 
  int range = max - min + 1;
  int *count = (int *) malloc(range * sizeof(int));
 
  for(i = 0; i < range; i++)
    count[i] = 0;
 
  for(i = 0; i < size; i++)
    count[ array[i] - min ]++;
 
  int j, z = 0;
  for(i = min; i <= max; i++)
    for(j = 0; j < count[ i - min ]; j++)
      array[z++] = i;
 
  free(count);
}

[edit] C++ Code 

This section needs your Code!

[edit] PHP Code 

This section needs your Code!

[edit] C# Code 

static void CountingSort(ref int[] arr)
        {
            int max = arr.Max();
            int min = arr.Min();
            int range = max - min + 1; 
            var count=new int[range]; //Count Array Hold The Number Of Each Number          
            for (int i = 0; i < arr.Length; i++)
                count[arr[i] - min]++;
            
            int index = 0;
            for (int i = min; i <= max; i++)//Fill Array in sorted Order
                for (int j = 0; j < count[i - min]; j++)
                    arr[index++] = i;
        }

[edit] Java Code 

/*
 * @(#)CombSort11Algorithm.java	1.0 96/11/20 Jason Harrison
 *
 * Copyright (c) 1995 University of British Columbia
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL purposes and without
 * fee is hereby granted provided that this copyright notice
 * appears in all copies. Please refer to the file "copyright.html"
 * for further important copyright and licensing information.
 *
 * UBC MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. UBC SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 */
 
/**
 * A comb sort 11 sort demonstration algorithm
 * Idea from Byte April 1991 by Richard Box and Stephen Lacey
 * Michele Estebon (mestebon@vt.edu) brought this to my attention.
 * 
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
 *
 * @author Jason Harrison@cs.ubc.ca
 * @version 	1.0, 20 Nov 1996
 *
 */
class CombSort11Algorithm extends SortAlgorithm {
    final float SHRINKFACTOR = (float)1.3;
 
    void sort(int a[]) throws Exception {
        boolean flipped = false;
        int gap, top;
        int i, j;
 
        gap = a.length;
        do {
            gap = (int) ((float) gap / SHRINKFACTOR);
            switch (gap) {
            case 0: /* the smallest gap is 1 - bubble sort */
                gap = 1;
                break;
            case 9: /* this is what makes this Combsort11 */
            case 10: 
                gap = 11;
                break;
            default: break;
            }
            flipped = false;
            top = a.length - gap;
            for (i = 0; i < top; i++) {
                if (stopRequested) {
                    return;
                }
 
                j = i + gap;
                if (a[i] > a[j]) {
                    int T = a[i];
                    a[i] = a[j];
                    a[j] = T;
                    flipped = true;
                }
                pause(i,j);
            }
        } while (flipped || (gap > 1));
        /* like the bubble and shell sorts we check for a clean pass */
    }
}

[edit] VB Code 

Module Module1

    Sub Main()
        Dim A() As Integer = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
        Dim B(A.Length - 1) As Integer

        countingSort(A, B, 10)

        For i As Integer = 0 To UBound(B) Step 1
            System.Console.Write(B(i).ToString)
        Next
        System.Console.Read()

    End Sub

    Sub countingSort(ByRef A, ByRef B, ByVal k)
        Dim C(k + 1) As Integer

        For i As Integer = 0 To UBound(A) Step 1
            C(A(i)) = C(A(i)) + 1
        Next

        For i As Integer = 1 To k + 1 Step 1
            C(i) = C(i) + C(i - 1)
        Next

        For i As Integer = UBound(B) - 1 To 0 Step -1
            B(C(A(i)) - 1) = A(i)
            C(A(i)) = C(A(i)) - 1
        Next
    End Sub

End Module

[edit] Perl Code 

This section needs your Code!

[edit] Prolog Code 

This section needs your Code!

[edit] Python Code 

#Author: Jonathan Cantrell

from pylab import *

def CountingSort(A,B,k):
    C = array([0] * (k))
    for i in A:
        C[i] = C[i] + 1
    for i in range(1,k):
        C[i] = C[i] + C[i-1]
    for j in reversed(A):
        B[C[j]-1] = j
        C[j] = C[j] - 1

[edit] Ruby Code 

This section needs your Code!
Retrieved from "http://www.algorithm-code.com/wiki/Counting_sort"
Personal tools