Zdrojové kódy pro vývojáře.
Přeskočit odkazy pro navigaci Top 10 přispěvatelů
UživatelČlánky
codeshare45
sochor1
stoupa1
tomas.oplt15
Článek: Algorithm - Count sort
Špatný Super
Autor:
Vytvořeno:
Popularita:

Counting Sort is a special case of indexed sort.

This algorithm can be applied only under very particular conditions but that, when such conditions are met, turns to be the fastest sort algorithm.
Range of different values should not be too large and values should be an numeric types.

1 ) Algorithm parses the original array determining its minimum and maximum value,
2 ) builds a temporary array of Long with one element for each possible value of the key.
3 ) Parses the original array again, this time counting the occurrences of each distinct value.
4 ) Evaluate where each value has to go in the sorted array.
#include  
#include
#include
#include
#include
using std::cout;
using std::cin;

int arr[] = {1,6,2,2,4};

void counting_sort(int *nums, int size)
{
// search for the minimum and maximum values in the array
int i, min = nums[0], max = min;

for(i = 1; i < size; ++i)
{
if (nums[i] < min)
min = nums[i];
else if (nums[i] > max)
max = nums[i];
}

// create a counting array, counts, with a member for
// each possible discrete value in the input.
// initialize all counts to 0.
int distinct_element_count = max - min + 1;
int * counts = new int[distinct_element_count];

for(i=0; i{
counts[i] = 0;
}

// accumulate the counts - the result is that counts will hold
// the offset into the sorted array for the value associated with that index
for(i=0; i{
++counts[ nums[i] - min ];
}

// store the elements in the array
int j=0;
for(i=min; i<=max; i++)
{
for(int z=0; z{
nums[j++] = i;
}
}

delete[] counts;
}

int main()
{
counting_sort(arr, 5);
}l

 

  Na stránku 
screen  Nový příspěvek
Název  Uživatel  Datum 
Poslední návštěva: 20:54:00, 22. září 2017 První  Předchozí  0 Záznamů  Další  Poslední  

Autor článku
Jméno
Pracovní pozice
Informace
Foto

   

Počet návštěvníků:72
 
  Kontakt