Counting Sort

Aspecte teoretice:

Sortarea prin numărare necesită spațiu suplimentar de memorie. Ea folosește următorii vectori:
– vectorul sursă (vectorul nesortat) a;
– vectorul destinație (vectorul sortat) b;
– vectorul numărător (vectorul de contoare) k.
Elementele vectorului sursă a[i] se copie în vectorul destinație prin inserarea în poziția corespunzătoare, astfel încât, în vectorul destinație să fie respectată relația de ordine. Pentru a se cunoaște poziția în care se va insera fiecare element, se parcurge vectorul sursă și se numără în vectorul k, pentru fiecare element a[i], câte elemente au valoarea mai mică decât a lui. Fiecare element al vectorului k este un contor pentru elementul a[i]. Valoarea contorului k[i] pentru elementul a[i] reprezintă câte elemente sunt mai mici decât el și arată de fapt poziția în care trebuie copiat în vectorul b.

Analiza complexității:

Cazul nefavorabil: O(k+n)
Cazul mediu: O(k+n)
Cazul favorabil: O(k+n)

Exemplu Pas cu Pas:

A

3

6

4

1

3

4

1

4

C

2

0

2

3

0

1

C

2

2

4

7

7

8

B

4

C

2

2

4

6

7

8

B

1

4

C

1

2

4

6

7

8

B

1

4

4

C

2

2

4

5

7

8

B

1

1

3

3

4

4

4

6

Implementare:

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace CountSortCS
{
	class Program
	{
		static void CountSort(int[] a, int lengt) 
		{
			int[] counts = new int[10];
			for(int i=0; i < lengt; i++) 
			{
				counts[a[i]]++;
			}
			int outputPos = 0;
			for (int i=0; i < 10; i++) 
			{
				for (int j=0; j < counts[i]; j++) 
				{
					a[outputPos] = i;
					outputPos++;
				}
			} 
		}
 
		static void Main(string[] args)
		{
			int[] v = new int[20];
			int i, len;
			Console.Write("Dati numarul de elemente n: ");
			len = Convert.ToInt32(Console.ReadLine());
			for (i = 0; i < len; i++)
			{
				Console.Write("v[" + i + "]=");
				v[i] = Convert.ToInt32(Console.ReadLine());
			}
			CountSort(v,len);
			for (i = 0; i < len; i++)
				Console.Write(v[i] + " ");
			Console.ReadKey();
		}
	}
}

Cod Sursa VB

Module Module1
 
    Private Sub CountSort(a As Integer(), lengt As Integer)
        Dim counts As Integer() = New Integer(9) {}
        For i As Integer = 0 To lengt - 1
            counts(a(i)) += 1
        Next
        Dim outputPos As Integer = 0
        For i As Integer = 0 To 9
            For j As Integer = 0 To counts(i) - 1
                a(outputPos) = i
                outputPos += 1
            Next
        Next
    End Sub
 
    Sub Main(args As String())
        Dim v As Integer() = New Integer(19) {}
        Dim i As Integer, len As Integer
        Console.Write("Dati numarul de elemente n: ")
        len = Convert.ToInt32(Console.ReadLine())
        For i = 0 To len - 1
            Console.Write("v[" & i & "]=")
            v(i) = Convert.ToInt32(Console.ReadLine())
        Next
        CountSort(v, len)
        For i = 0 To len - 1
            Console.Write(v(i) & " ")
        Next
        Console.ReadKey()
    End Sub
 
 
End Module

Cod Sursa C++

// CountSortCPP.cpp : Defines the entry point for the console application.
// Complexitate: Nefavorabil: O(k+n); Mediu: O(k+n); Favorabil: O(k+n)
 
#include "stdafx.h"
#include 
#include 
 
using namespace std;
 
int v[20];
 
void CountSort(int v[], int len)
{
	int i,j,a[20], b[20];
	for (i=0; i<len; i++)
		a[i]=0;
	for (i=0; i<len-1; i++)
		for (j=i+1; j<len; j++)
			if(v[i]<v[j])
				a[j]++;
			else
				a[i]++;
	for (i=0; i<len; i++)
		b[a[i]]=v[i];
	memcpy(v,b,len*sizeof(int));
	return;
}
 
int main(void)
{
	int i;
	int len;
	cout<<"Dati numarul de elemente din vector: ";
	cin>>len;
	for (i=0; i<len; i++)
	{
		cout<<"v["<<i<<"]=";
		cin>>v[i];
	}
	CountSort(v, len);
	for (i=0; i<len; i++)
		cout<<v[i]<<" ";
	system("pause");
}
 

Cod Sursa PHP

Cod Sursa JAVA

import java.util.Arrays; import java.util.Random;public class CountSortJAVA {     public static void sort(int[] a) {          if (a.length == 0)      return;   int max = a[0], min = a[0];    for (int i = 1; i < a.length; i++) {        if (a[i] > max)            max = a[i];        else if (a[i] < min)            min = a[i];    }    int numValues = max – min + 1;          int[] counts = new int[numValues];          for (int i = 0; i < a.length; i++) {        counts[a[i]-min]++;    }    int outputPos = 0;    for (int i = 0; i < numValues; i++) {        for (int j = 0; j < counts[i]; j++) {            a[outputPos] = i+min;            outputPos++;        }    }      }      public static void main(String[] args) {          int listSize = Integer.parseInt(args[0]);          int numValues = Integer.parseInt(args[1]);          // Generate list of random values          int[] a = new int[listSize];          Random r = new Random();          for (int i = 0; i < a.length; i++) {              a[i] = r.nextInt(numValues);          }          // Copy list to new array          int[] a2 = new int[listSize];          System.arraycopy(a, 0, a2, 0, listSize);          // Sort the two arrays          sort(a);          Arrays.sort(a2);          // Compare the two arrays          for (int i = 0; i < listSize; i++) {              if (a[i] != a2[i]) {                  System.out.println(“Error: Results do not match.”);                  return;              }          }          System.out.println(“Sort successful”);      }  }

Rezultat: