Algorithms/shell sort

خوارزمية شِل للترتيب Shell sort هي شكل آخر لخوارزمية الترتيب بالإدراج Insertion Sort. نحرّك العناصر موقعًا واحدًا إلى الأمام فقط في خوارزمية الترتيب بالإدراج، وإن لَزِم تحريك العنصر أبعد من ذلك يجب تحريك العنصر لخطوات متعددة. تهدف خوارزمية ترتيب شِل إلى السماح بإجراء عملية تبادل مع العناصر البعيدة.

ترتب خوارزمية شِل المصفوفة بالنسبة لقيمة كبيرة من h ، ثم تستمر في تقليص قيمة h إلى حين الوصول إلى 1. تسمى المصفوفة h-sorted إذا كانت جميع المصفوفات الفرعية لكل h عنصر مرتّبة.

أمثلة

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <iostream> 
using namespace std; 

int shellSort(int arr[], int n) 
{ 
	// البدء بفجوة كبيرة ثم تقليص هذه الفجوة
	for (int gap = n/2; gap > 0; gap /= 2) 
	{ 
		// إجراء عملية الترتيب بالإدراج باستخدام مقدار الفجوة المعطى.
		// أولى العناصر في الفجوة 
		// a[0..gap-1]
		// مرتّبة أصلًا
		// نستمر في إضافة عنصر إضافي إلى أن تصبح المصفوفة كلها مرتّبة
		for (int i = gap; i < n; i += 1) 
		{ 
			// نضيف هذا العنصر إلى العناصر التي جرى ترتيبها
			// نحفظ هذا العنصر في متغير مؤقت ثم نحدث ثغرة في موقعه
			int temp = arr[i]; 

			// نزيح جميع العناصر المرتّبة مسبقًا إلى حين العثور
			// a[i] على الموقع الصحيح للعنصر 
			int j;			 
			for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
				arr[j] = arr[j - gap]; 
			
			// نضع العنصر المخزن في المتغير المؤقت في مكانه الصحيح
			arr[j] = temp; 
		} 
	} 
	return 0; 
} 

void printArray(int arr[], int n) 
{ 
	for (int i=0; i<n; i++) 
		cout << arr[i] << " "; 
} 

int main() 
{ 
	int arr[] = {12, 34, 54, 2, 3}, i; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	cout << "Array before sorting: \n"; 
	printArray(arr, n); 

	shellSort(arr, n); 

	cout << "\nArray after sorting: \n"; 
	printArray(arr, n); 

	return 0; 
}

• بايثون:

def shellSort(arr): 

	# البدء بفجوة كبيرة ثم تقليص هذه الفجوة
	n = len(arr) 
	gap = n//2



	# إجراء عملية الترتيب بالإدراج باستخدام مقدار الفجوة المعطى.
	# أولى العناصر في الفجوة 
	# a[0..gap-1]
	# مرتّبة أصلًا
	# نستمر في إضافة عنصر إضافي إلى أن تصبح المصفوفة كلها مرتّبة 
	while gap > 0: 

		for i in range(gap,n): 
			# نضيف هذا العنصر إلى العناصر التي جرى ترتيبها
			# نحفظ هذا العنصر في متغير مؤقت ثم نحدث ثغرة في موقعه
			temp = arr[i] 
			# نزيح جميع العناصر المرتّبة مسبقًا إلى حين العثور
			# a[i] على الموقع الصحيح للعنصر 
			j = i 
			while j >= gap and arr[j-gap] >temp: 
				arr[j] = arr[j-gap] 
				j -= gap 


			# نضع العنصر المخزن في المتغير المؤقت في مكانه الصحيح
			arr[j] = temp 
		gap //= 2


# اختبار الدوال السابقة
arr = [ 12, 34, 54, 2, 3] 

n = len(arr) 
print ("Array before sorting:") 
for i in range(n): 
	print(arr[i]), 

shellSort(arr) 

print ("\nArray after sorting:") 
for i in range(n): 
	print(arr[i]),

• جافا:

class ShellSort 
{ 
	/* دالة مساعدة لطباعة محتويات المصفوفة */
	static void printArray(int arr[]) 
	{ 
		int n = arr.length; 
		for (int i=0; i<n; ++i) 
			System.out.print(arr[i] + " "); 
		System.out.println(); 
	} 

	int sort(int arr[]) 
	{ 
		int n = arr.length; 

		// البدء بفجوة كبيرة ثم تقليص هذه الفجوة 
		for (int gap = n/2; gap > 0; gap /= 2) 
		{ 
		// إجراء عملية الترتيب بالإدراج باستخدام مقدار الفجوة المعطى.
		// أولى العناصر في الفجوة 
		// a[0..gap-1]
		// مرتّبة أصلًا
		// نستمر في إضافة عنصر إضافي إلى أن تصبح المصفوفة كلها مرتّبة 
			for (int i = gap; i < n; i += 1) 
			{ 
			// نضيف هذا العنصر إلى العناصر التي جرى ترتيبها
			// نحفظ هذا العنصر في متغير مؤقت ثم نحدث ثغرة في موقعه
				int temp = arr[i]; 

			// نزيح جميع العناصر المرتّبة مسبقًا إلى حين العثور
			// a[i] على الموقع الصحيح للعنصر 
				int j; 
				for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
					arr[j] = arr[j - gap]; 

			//  نضع العنصر المخزن في المتغير المؤقت في مكانه الصحيح
				arr[j] = temp; 
			} 
		} 
		return 0; 
	} 

	// اختبار الدوال السابقة
	public static void main(String args[]) 
	{ 
		int arr[] = {12, 34, 54, 2, 3}; 
		System.out.println("Array before sorting"); 
		printArray(arr); 

		ShellSort ob = new ShellSort(); 
		ob.sort(arr); 

		System.out.println("Array after sorting"); 
		printArray(arr); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لطريقة التنفيذ الموضحة في الأمثلة أعلاه المقدار O(n2)‎. تُقلّص الفجوة في الأمثلة إلى النصف في كل دورة من دورات الحلقة التكرارية، وهناك طرق أخرى لتقليص مقدار الفجوة تؤدي إلى الحصول على تعقيد زمني أفضل.

مصادر

• صفحة ShellSort في توثيق الخوارزميات في موقع GeeksforGeeks.