Daa10 Linearsort

Сортиране, което не е базирано на директно сравнение. Сортиране в линейно време - Counting Sort. Анализ на коректността им и на сложността им по време.

Идеята на CountingSort

Идеята е проста - ако трябва да сортираме масив с числа и знаем, че всяко едно от тях попада в даден интервал, то това сортиране може да се извърши в линейно време.

Имплементация на CountingSort на C++

Имплементацията е взета от http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Counting_sort

/* end is the last index + 1 */
void csort(int array[], const int end,
      const int max, const int min)
{
  int i;
  const int range = max-min+1;
  int count[range+1],
      scratch[end];
 
  for(i=0; i<range+1; i++)
    count[i] = 0;
 
  /* Set the value of count[i] to the number of
   * elements in array with value i+min-1. */
  for(i=0; i<end; i++) {
    int c = array[i]-1-min;
    count[c]++;
  }
 
  /* Update count[i] to be the number of
   * elements with value less than i+min. */
  for(i=1; i<range; i++)
    count[i] + = count[i-1];
 
  /* Copy the elements of array into scratch in
   * stable sorted order. */
  for(i=(end-1); i>=0; i--) {
    int c = array[i]-min;
    int s = count[c];
    scratch[s] = array[i];
    /* Increment count so that the next element
     * with the same value as the current element
     * is placed into its own position in scratch. */
    count[c]++;
  }
 
  for(i=0; i<end; i++)
    array[i] = scratch[i];
}

Имплементация на CountingSort на Java

Имплементацията е взета от http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Counting_sort

import java.util.Arrays;
 
public static void countingSort(int[] a, int low, int high)
{
    int[] counts = new int[high - low + 1]; // this will hold all possible values, from low to high
    for (int x : a)
        counts[x - low]++; // - low so the lowest possible value is always 0
 
    int current = 0;
    for (int i = 0; i < counts.length; i++)
    {
        Arrays.fill(a, current, current + counts[i], i + low); // fills counts[i] elements of value i + low in current
        current += counts[i]; // leap forward by counts[i] steps
    }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License