mElstEd fyrir 21 árum, 3 mánuðum Fjöldi lestra: 982

Counting Sort

Counting Sort er aðferð til að raða heiltölum á einfaldan og mjög hraðvirkan hátt. Inntakið fyrir aðferðina er fylki A af heiltölum á bilinu 0 til k-1 af stærð n og B er fylki af stærð n.

C er hjálparfylki af stærð k sem í byrjun telur hversu oft hver tala kemur fyrir. T.d. telur C[5] hversu oft talan 5 kemur fyrir í fylkinu A.

Síðan er C breytt þannig að það C telur hversu oft tölurnar 0 og upp í i koma fyrir í A. Þá telur C[5] hversu oft tölurnar 0,1,2,3,4,5 koma fyrir í A.

Síðasta skrefið er aðal barbabrellan og ekki auðvelt að átta sig á af hverju fylkið B verður raðað. Nei, ég ætla ekki að útskýra það :)

Þessi aðferð hefur keyrslutímann O(n+k) svo að þetta hentar mjög vel fyrir lítil k t.d. 256 en ekki til að raða int breytum sem á góðum degi eru ca. 4 milljarðar. Þá þyrfti fylkið C að vera 4 GB af stærð! C++ kóði fylgir með, það ætti að vera auðvelt mál að breyta þessu í Java kóða eða bara hvað sem er.

function count_sort(int* A, int* B, int n, int k) { 
  int i; 
  int *C = new int[n]; 
  for (i = 0; i < k; i++) { 
    C = 0; 
  } 
 
  for (i = 0; i < n; i++) { 
    C[A]++; 
 &n bsp;} 
 
  for (i = 1; i < k; i++) { 
    C += C[i-1]; 
  } 
 
  for (j = 0; j < n; j++) { 
    B[C[A[j]]] = A[j]; 
    C[A[j]]–; 
&nbs p; } 
}

abh fyrir 21 árum, 3 mánuðum

Svari eytt af stjórnanda

Fyrra álit

abh fyrir 21 árum, 3 mánuðum

Gleymdi reyndar að bæta, en frábært að fá greinar frá öðrum en mér! Ég var orðinn hálfleiður á sjálfum mér ;)

Komdu með fleiri

Fyrra álit

abh fyrir 21 árum, 3 mánuðum

Jæja, ég verð að éta ofan í mig stóru orðin, þetta er þótt ótrúlegt sé, langtum hraðvirkara en Quick Sort.

Prófaði að gera lítinn samanburð á Quick Sort og Counting Sort. Sorteraði 1.000.000 færslur af random integer tölum. Útkoman kom mjög á óvart, en að meðaltali þá skilaði Quick Sort rútínan mín þessu á 2293 ms en Counting Sort rútínan á 170 MS!!!

Ég reyndar breytti þessu þannig að ég þyrfti einungis 2 array-a.

Þetta er ótrúlegur munur sko, en samt sem áður, þá virkar þetta bara á heiltölur :(

// Hér er svo Counting Sort rútínan sem ég notaði
// Quick Sort er í grein frá mér.

void CountingSort(int *iarrTolur, int iNum)
{
int iHi = 0;
for (int i = 0; i < iNum; i++)
if (iarrTolur > iHi) iHi = iarrTolur;
int *iarrCount = new int[iHi + 1];

for (int i = 0; i <= iHi; i++) iarrCount = 0;

for (int i = 0; i < iNum; i++) iarrCount[iarrTolur]++;

for (int i = 0, d = 0; i <= iHi; i++)
{
for (int j = 0, int cc = iarrCount; j < cc; j++, d++)
iarrTolur[d] = i;
}
delete[] iarrCount;
}

Fyrra álit

Avatar fyrir 21 árum, 3 mánuðum

Þessi röðunaraðferð hentar einkar vel til að raða Byte og Char arrayum. Þau get jú mest verið með 256 gildi ;)

Fyrra álit

[Notanda eytt] fyrir 21 árum, 3 mánuðum

Flott hjá þér. Hvenær kemur grein um MergeSort? Það er mjög stöðugt reiknirit sama hvað þú hendir í það nema auðvitað þetta með minnisnotkunina.

Fyrra álit

an13810 fyrir 21 árum, 3 mánuðum

Í staðinn fyrir að vera með for loopu þarna til að setja C array-ið sem 0 væri hraðara að nota memset eða calloc.

–> an13810

Fyrra álit

ojb fyrir 21 árum, 3 mánuðum

eða nota bara pointerafylki ( null sjálfkrafa )

Fyrra álit

DjonnsonRivers fyrir 21 árum, 2 mánuðum

vóts mand hvar læriði þessi orð mand mig lángar að læra að tala svona

buurrrrrrrn

Fyrra álit

Forritun

Forritun

Ofurhugar

Stjórnendur

Hverjir eru inni

Greinar

Counting Sort

Dýr

Dægurmál

Fræði

Leikir

Lífið

Lífsstíll

Margmiðlun

Menning

Skjár

Sport

Tónlist

Tækni

Vélar

Hugi