കശക്കൽ അൽഗൊരിതം

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
(Shuffling algorithm എന്ന താളിൽ നിന്നും തിരിച്ചുവിട്ടതു പ്രകാരം)
Jump to navigation Jump to search

സമാന സാധ്യതയാൽ ഒരു കൂട്ടം വസ്തുക്കളെ കൂട്ടി കലർത്തുന്ന അൽഗൊരിതങ്ങളെ കശക്കൽ അൽഗൊരിതങ്ങൾ അഥവാ ഷഫ്ലിങ്ങ് അൽഗൊരിതങ്ങൾ എന്നു വിളിക്കാം.

ക്നൂത്തിന്റെ കശക്കൽ അൽഗൊരിതം[തിരുത്തുക]

ഈ അൽഗരിത പ്രകാരം, N വസ്തുക്കളെ N തവണ കശക്കുന്നു. ഇതിനായി, ഒരു ലൂപ്പിലൂടെ ഐറ്റെറേറ്റ് ചെയ്യുകയും, ഇറ്ററേറ്റ് ചെയ്യുംബോൾ ഒരു പ്രത്യേക ഇൻഡെക്സിലുള്ള വസ്തുവിനെ, ആ വസ്തുവിനു മുൻബിലുള്ള മറ്റു വസ്തുക്കളിലേതെങ്കിലുമൊന്നിന്റെ ഇൻഡെക്സുമായി സ്ഥാനം വച്ച് മാറുകയും ചെയ്യുന്നു. (ഇപ്രകാരം സ്ഥാനം നിർണ്ണയിക്കുന്നത് യൂണിഫോം റാൻഡം സംഖ്യ നിർമ്മാണ അൽഗൊരിതവും ഉപയോഗിയ്ക്കുന്നു.)

അൽഗൊരിതം[തിരുത്തുക]

//a[]  conatins objects to be shuffled
for(int i=N-1; i>=0;i--)
{ 
	//creating random number b/w 0 and i position. object will be swapped with this random position
	int r = rand()%(i+1);
	//object  a[i] is being swapped with the object at random position r
	swap(a[i],a[r]);
}

സങ്കീർണ്ണത[തിരുത്തുക]

ഈ അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത ~ (N + N * (റാൻഡം സംഖ്യ സൃഷ്ടിയ്ക്കുവാനാവശ്യമായ സങ്കീർണ്ണത)

അവലംബം[തിരുത്തുക]

https://class.coursera.org/algs4partI-002/lecture/28

"https://ml.wikipedia.org/w/index.php?title=കശക്കൽ_അൽഗൊരിതം&oldid=1658041" എന്ന താളിൽനിന്ന് ശേഖരിച്ചത്