ഷെൽ സോർട്ട്

ഡൊണാൾഡ് ഷെൽ 1959ൽ മുന്നോട്ട് വച്ച ഒരു സോർട്ടിങ്ങ് അൽഗരിതമാണിത്. ഇൻസർഷൻ സോർട്ടിങ്ങിൽ ഒരു സ്ഥാനത്തുള്ള സംഖ്യ, തൊട്ട് പുറകിലുള്ള സംഖ്യകളുമായി താരതമ്യപ്പെടുത്തി സ്വാപ്പ് ചെയ്യുകയാണു ചെയ്യുന്നതെങ്കിൽ, ഷെൽ സോർട്ടിങ്ങിൽ ‘h’ സ്ഥാനം പുറകിലുള്ള സംഖ്യകളുമായി താരതമ്യപ്പെടുത്തി സ്വാപ്പ് ചെയ്യുന്നു. h എന്നത് സോർട്ട് ചെയ്യണ്ട സംഖ്യകളുടെ എണ്ണമനുസരിച്ച് നിശ്ചയിക്കുന്നു. h എന്നത് ആദ്യം വലിയ ഒരു സംഖ്യയായിരിയ്ക്കും. അത് വഴി വലിയ ചാട്ടങ്ങൾ ചാടിയായിരിക്കും സംഖ്യകൾ താരതമ്യപ്പെടുത്തുന്നത്. ഓരോ ലിസ്റ്റ് യാത്രയ്ക്ക് ശേഷവും hന്റെ വില പുനർനിർണ്ണയിക്കും (ക്നൂത്തിന്റെ ആശയപ്രകാരമത് മൂന്നിലൊന്നായി കുറച്ച് കൊണ്ട് വരും). ഓരോ യാത്രയ്ക്ക് ശേഷവും, ലിസ്റ്റ് കൂടുതൽ കൂടുതൽ സോർട്ട് ചെയ്യപ്പെട്ടിരിയ്ക്കും.

ഷെൽ സോർട്ട്

Shellsort with gaps 23, 10, 4, 1 in action
കുടുംബം	Sorting algorithm
ദത്തസങ്കേതം	Array
കൂടിയ സമയസങ്കീർണ്ണത	O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)
കുറഞ്ഞ സമയസങ്കീർണ്ണത	O(n log n) (most gap sequences) O(n log2n) (best known worst-case gap sequence)
ശരാശരി സമയസങ്കീർണ്ണത	depends on gap sequence
കൂടിയ സ്ഥലസങ്കീർണ്ണത	О(n) total, O(1) auxiliary
Optimal	No

Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1

h ന്റെ മൂല്യം നിശ്ചയിക്കുന്നതിന് പലരും പല രീതികളും മുന്നോട്ട് വച്ചിട്ടുണ്ട്. അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത h ന്റെ മൂല്യത്തെ ആശ്രയിച്ചിരിക്കുന്നു. പ്രസിദ്ധ കമ്പ്യൂട്ടർ ശാസ്ത്രകാരനായ ഡൊണാൾഡ് കനൂത്ത് ഇതിനായി 3x+1 എന്ന ഒരു സമവാക്യമാണ് മുന്നോട്ട് വച്ചത്. ഷെൽ തന്റെ കണ്ട് പിടുത്തത്തിനു 2^x-1 എന്ന സമവാക്യമാണൂ മുന്നോട്ട് വച്ചത്. മെച്ചപ്പെട്ട h മൂല്യം എത്രയെന്ന് കണ്ട് പിടിയ്ക്കുന്നതും, സോർട്ടിങ്ങ് രീതിയിൽ മെച്ചപ്പെട്ട മാറ്റങ്ങൾ വരുത്തുന്നതും ഒരു ഗവേഷണ വിഷയമായി പലരും എടുത്തിട്ടുണ്ട്.

അൽഗരിതം

//find out h value
//knuth's method to calculate h
h=1;
while(h < N/3) h = 3*h +1; //1,4,13,40...

//sorting the values

while(h>=1)
{
	for(int i=h;i<N;i++)
	{
		for(int j=i;j>=h;j=j-h)
		{
			If(a[j] < a[j-h])swap(a[j],a[j-h]);
			else break;
		}
	}

	//knuth's proposition of recalculating h
	h = h/3;
}

സങ്കീർണ്ണത

'h' മൂല്യം കണ്ട് പിടിയ്ക്കുന്ന രീതിയ്ക്കനുസരിച്ച് ഈ അൽഗരിതത്തിന്റെ സങ്കീർണ്ണതയും മാറുന്നു. ക്നൂത്തിന്റെ രീതി ഉപയോഗിയ്ക്കുന്ന അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത് n^1.5 ആണു.

അവലംബം

• https://class.coursera.org/algs4partI-002/lecture/27 Archived 2021-01-16 at the Wayback Machine.
• http://www.cs.princeton.edu/~rs/shell/paperF.pdf