കൗണ്ടിങ്ങ് സോർട്ട്

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Counting_sort

കൗണ്ടിങ്ങ് സോർട്ട്

കുടുംബം	സോർട്ടിങ്ങ് അൽഗൊരിതം
ദത്തസങ്കേതം	അറേ
കൂടിയ സമയസങ്കീർണ്ണത	${\displaystyle O(n+k)}$
കുറഞ്ഞ സമയസങ്കീർണ്ണത	${\displaystyle O(n+k)}$
ശരാശരി സമയസങ്കീർണ്ണത	${\displaystyle O(n+k)}$
ക സ തി

ഒരു ലിസ്റ്റിലെ സംഖ്യകളുടെ റെയ്ഞ്ച് ചെറുതാണെങ്കിൽ ഈ വിവരമുപയോഗിച്ച് അവയെ വളരെ വേഗത്തിൽ ക്രമീകരിക്കുന്ന സോർട്ടിങ്ങ് അൽഗൊരിതമാണ്‌ കൗണ്ടിങ്ങ് സോർട്ട്. അൾട്ര സോർട്ട്, മാത്ത് സോർട്ട് എന്നും ഇതിന്‌ പേരുകളുണ്ട്^[1]. റെയ്ഞ്ചിലെ സംഖ്യകൾക്കായി ക്രമത്തിൽ ഒരു അറേ നിർമ്മിക്കുകയും ക്രമീകരിക്കേണ്ട ലിസ്റ്റിൽ ഓരോ സംഖ്യയും എത്ര തവണ ആവർത്തിക്കുന്നുണ്ട് എന്ന് എണ്ണുകയും ചെയ്തുകൊണ്ടാണ്‌ ഈ അൽഗൊരിതം ക്രമീകരണം സാധിക്കുന്നത്. 1954-ൽ ഹരോൾഡ് എച്ച്.. സീവാർഡാണ്‌ ഇത് കണ്ടെത്തിയത്.

ലിസ്റ്റിലെ സംഖ്യകളെ തമ്മിൽ താരതമ്യം ചെയ്യുന്നില്ല എന്നതിനാൽ ഇത് താരതമ്യ സോർട്ട് അല്ല. ഈ അൽഗൊരിതം സ്റ്റേബിൾ ആണ്‌. ലിസ്റ്റിലെ സംഖ്യകളുടെ എണ്ണം n, ലിസ്റ്റിന്റെ റെയ്ഞ്ചിലെ സംഖ്യകളുടെ എണ്ണം k എന്നിവയാണെങ്കിൽ ഈ അൽഗൊരിതത്തിന്റെ മികച്ച, ശരാശരി, മോശം സമയസങ്കീർണ്ണതകളെല്ലാം O(n + k) ആണ്‌. അതിനാൽ k, n എന്നിവ ഏതാണ്ട് തുല്യമാണെങ്കിൽ വളരെ വേഗം സംഖ്യകളെ ക്രമീകരിക്കാൻ ഈ അൽഗൊരിതത്തിന്‌ സാധിക്കുന്നു. ഇതിന്‌ സമാനമായ മറ്റൊരു സോർട്ടിങ്ങ് അൽഗൊരിതമാണ്‌ പീജിയൺഹോൾ സോർട്ട്.

ഒരു ലിസ്റ്റ് ക്രമീകരിക്കാനുള്ള അൽഗൊരിതത്തിലെ പടികൾ:

1. ലിസ്റ്റിലെ ഏറ്റവും ചെറുതും വലുതുമായ സംഖ്യകൾ കണ്ടുപിടിക്കുക
2. ഇതിനിടയിലെ ഓരോ സംഖ്യയും ലിസ്റ്റിൽ എത്ര തവണ ആവർത്തിക്കുന്നുവെന്ന് (count) കണ്ടെത്തുക
3. ഈ വിവരമുപയോഗിച്ച് ഏത് സ്ഥാനങ്ങളിലാണ്‌ ഓരോ സംഖ്യയും ലിസ്റ്റിൽ വരാവുന്നത് എന്ന് കണ്ടുപിടിക്കുക. ഇതിനായി ഏറ്റവും ചെറിയ സംഖ്യ മുതൽ ആ സംഖ്യ വരെയുള്ളവയുടെ ആവർത്തനങ്ങളുടെ തുക (sumcount = sum (count)) കണ്ടെത്തിയാൽ മതി
4. ല്ലിസ്റ്റിന്റെ പിൻഭാഗത്തുനിന്ന് സംഖ്യകളെ വായിച്ച് sumcount സ്ഥാനത്ത് വയ്ക്കുകയും sumcount ന്റെ വില കുറയ്ക്കുകയും ചെയ്യുക. ലിസ്റ്റിലെ എല്ലാ സംഖ്യകളെയും ക്രമത്തിലാക്കും വരെ ഇത് തുടരുക

ഇങ്ങനെ ചെയ്യുകയാണെങ്കിൽ അൽഗൊരിതം സ്റ്റേബിൾ ആവുകയും ലിസ്റ്റിൽ സംഖ്യകൾ മാത്രമല്ലാതിരിക്കുമ്പോഴും (അതായത്, കീ വില ഉള്ള സ്ട്രച്ചറുകൾക്കും ഇത് ഉപയോഗിക്കാം) സോർട്ടിങ്ങ് സാധിക്കുകയും ചെയ്യുന്നു. എന്നാൽ സംഖ്യകൾ മാത്രമാണെങ്കിൽ 3,4 പടികൾ കൂട്ടിച്ചേർക്കാം

സംഖ്യകൾ മാത്രമുള്ള അറേ ക്രമീകരിക്കാനുള്ള അൽഗൊരിതത്തിന്റെ C കോഡ്:

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);
}

വിവരസാങ്കേതികവിദ്യ കവാടം