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

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
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" എന്ന താളിൽനിന്ന് ശേഖരിച്ചത്