مرتب‌سازی گسترش‌یافته

مرتب‌سازی گسترش یافته یک الگوریتم مرتب‌سازی است که در سال ۲۰۰۲ توسط Steven J. Ross ابداع شد. این الگوریتم، مفاهیمی از مرتب‌سازی‌های توزیع شده مانند مرتب‌سازی مبنایی و سطلی را با مفاهیم مرتب‌سازی‌های سریع و ترکیبی تلفیق می‌کند. در نتایج تجربی، این الگوریتم در اجرا، بسیار کارامد تر از الگوریتم‌های سنتی مانند مرتب‌سازی سریع به ویژه در ارائه ساختارهای توزیع شده نشان داده شده‌است.
مرتب‌سازی سریع یک عنصر محوری را درلیست شناسایی می‌کند و لیست را به دو زیر لیست تقسیم می‌کند:عناصر بزرگتر از عنصر محوری وعناصر کوچکتر ازعنصر محوری.
مرتب‌سازی گسترش یافته این ایده را به صورت تقسیم بندی لیست به n/cپارتیشن در هر گام تعمیم می‌دهد، که nتعداد عناصر لیست وc ثابت کوچک است (در عمل در مقایسه‌های کند، معمولاً بین ۴ تا ۸ است؛ ولی در مقایسه‌های سریع c مقدار بزرگتری است).
این الگوریتم برای اجرا از تکنیک‌های توزیع شده استفاده می‌کند. ابتدا بزرگترین و کوچکترین مقادیر را وارد لیست می‌کند سپس ناحیه بین این دو را به n/c ظرف بااندازه مساوی تقسیم می‌کند. در مواقعی که ذخیره‌سازی یک مسئله مهم است، این الگوریتم می‌تواند در هر مرحله از تقسیم بازگشتی به داشتن بزرگترین ظرف کمک کند و باعث می‌شود این روند تقسیم چندین مرحله داشته باشد، اگرچه این کار باعث تکراربیشتر می‌شود ولی خطاهای ذخیره‌سازی را کاهش می‌دهد و باعث می‌شود که الگوریتم سریع تر اجرا شود.
درمواردی که تعداد ظرف‌ها حداقل برابر تعداد عناصر است، مرتب‌سازی گسترش یافته به مرتب‌سازی سطلی تخریب می‌شود و مرتب‌سازی به اتمام می‌رسد. در غیر این صورت هرظرف به صورت بازگشتی مرتب می‌شود.

الگوریتم از آزمون‌های اکتشافی برای تعیین اینکه ایا هر ظرف می‌تواند توسط این الگوریتم یا الگوریتم‌های دیگر، به‌طور کارامدتری مرتب شود، استفاده می‌کند. سپس به صورت بازگشتی ظرف‌ها را مرتب می‌کند.

این الگوریتم نیز مانند الگوریتم‌های توزیع شده دیگر نقطه ضعفی دارد و آن این است که برنامه‌نویس به ابزاری برای تبدیل هرعنصربه یک کلید عددی نیاز دارد و هدف آن شناسایی این است که هرکدام ازعناصر در کدام ظرف می‌افتند.
اگرچه برای عناصر با طول متغیر مانند رشته‌ها (با توجه به اینکه هر عدد باتعداد بی‌نهایتی از مقادیر مینیمم دنبال می‌شود و برای هرنوع داده‌ای دارای یک ارایش کلی می‌باشد) این عملیات برای پیاده‌سازی صحیح بسیار سخت تر از یک تابع مقایسه‌ای ساده به ویژه در ساختارهای پیچیده‌است. پیاده‌سازی ضعیف این تابع مقداری می‌تواند منجر به کلاستربندی شود که به کارایی الگوریتم آسیب می‌رساند.

کارایی

بدترین حالت الگوریتم مرتب‌سازی گسترش یافته بستگی به این دارد که این الگوریتم در نهایت کدام مرتب‌سازی را تبدیل به ظرف‌های کوچک می‌کند. برای الگوریتم‌هایی که بدترین حالت شان((O(nlogn) است مانند مرتب‌سازی ادغامی و مرتب‌سازی هرمی و برای الگوریتم‌هایی که بدترین حالت شان O(n^۲)می‌باشد مانند مرتب‌سازی سریع، مقدار ((O(nlogn) می‌باشد.
در توزیع‌ها هر جا اندازه کلید ۲k بار کوچکتر از مربع n(اندازه لیست) باشد ((۲k<log(n^۲) الگوریتم در بدترین حالت با دستیابی به بدترین زمان O(n(k - log(n)).۵)در نسخه‌های اصلی منتشرشده و O(n((k/s) + s)) برای نسخه‌های حافظه دار، بهتر عمل می‌کند.
آزمایش‌هایی که برای مقایسه نسخه بهینه مرتب‌سازی گسترش یافته با مرتب‌سازی بهینه C++انجام شدند، با مرتب‌سازی درونگرا پیاده‌سازی شدند.
مرتب‌سازی گسترش یافته در سیستم عامل‌های مختلف برای داده‌های تصادفی از نوع integer و float حدودا ۲-۷X برابر بهبود زمان اجرا را نشان می‌دهد. ازنظرحافظه موردنیاز، مرتب‌سازی گسترش یافته بدتر از اکثر الگوریتم‌های درجا است. این الگوریتم در ساده‌ترین شکلش یک الگوریتم درجا نیست که ازفضای اضافی O(n) استفاده کند. در آزمایش‌هایی ۲۰ ٪ بیشتر از مرتب‌سازی سریع ازحافظه استفاده می‌کند.
درفرم حافظه دار، از حافظه کمتری استفاده می‌شود و در استفاده از حافظه با حداکثرشمارش ظرف‌ها به تعداد حداکثر بازگشت‌ها یک کران بالا وجود دارد که تا تبدیل اندازه کلیدها از بایت به کیلوبایت تمام می‌شود.
اگرچه در این فرم نسبت به مرتب‌سازی سریع و مرتب‌سازی هرمی از فضای بیشتری استفاده می‌شود، ولی نسبت به فرم‌های اولیه مرتب‌سازی ادغامی که از فضای کمکی برابر با فضای اشغال شده توسط لیست‌ها استفاده می‌کند، به‌طور قابل ملاحظه‌ای از حافظه کمتری استفاده می‌نماید.
مرتب‌سازی گسترش یافته در مورد مسائل بسیار بزرگ که در حافظه جای نمی‌گیرند ونیازمند دسترسی به دیسک هستند، بسیار کارامد عمل می‌کند.

پیاده‌سازی

unsigned
RoughLog۲(DATATYPE input)
{
	unsigned char cResult = 0;
	// The && is necessary on some compilers to avoid infinite loops; it doesn't
	// significantly impair performance
	if(input >= ۰)
		while((input >> cResult) && (cResult < DATA_SIZE)) cResult++;
	else
		while(((input >> cResult) < -۱) && (cResult < DATA_SIZE)) cResult++;
	return cResult;
}
SIZETYPE
GetMaxCount(unsigned logRange, unsigned uCount)
{
	unsigned logSize = RoughLog2Size(uCount);
	unsigned uRelativeWidth = (LOG_CONST * logRange)/((logSize > MAX_SPLITS) ? MAX_SPLITS: logSize);
	// Don't try to bitshift more than the size of an element
	if(DATA_SIZE <= uRelativeWidth)
		uRelativeWidth = DATA_SIZE - ۱;
	return ۱ << ((uRelativeWidth < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ?
		(LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT): uRelativeWidth);
}

void
FindExtremes(DATATYPE *Array, SIZETYPE uCount, DATATYPE & piMax, DATATYPE & piMin)
{
	SIZETYPE u;
	piMin = piMax = Array[۰];
	for(u = 1; u < uCount; ++u){
		if(Array[u] > piMax)
			piMax=Array[u];
		else if(Array[u] < piMin)
			piMin= Array[u];
	}
}	

//---------------------SpreadSort Source-----------------

Bin *
SpreadSortCore(DATATYPE *Array, SIZETYPE uCount, SIZETYPE & uBinCount, DATATYPE &iMax, DATATYPE &iMin)
{
	// This step is roughly ۱۰٪ of runtime but it helps avoid worst-case
	// behavior and improves behavior with real data. If you know the
	// maximum and minimum ahead of time, you can pass those values in
	// and skip this step for the first iteration
	FindExtremes((DATATYPE *) Array, uCount, iMax, iMin);
	if(iMax == iMin)
		return NULL;
	DATATYPE divMin,divMax;
	SIZETYPE u;
	int LogDivisor;
	Bin * BinArray;
	Bin* CurrentBin;
	unsigned logRange;
	logRange = RoughLog2Size((SIZETYPE)iMax-iMin);
	if((LogDivisor = logRange - RoughLog2Size(uCount) + LOG_MEAN_BIN_SIZE) < ۰)
		LogDivisor = 0;
	// The below if statement is only necessary on systems with high memory
	// latency relative to processor speed (most modern processors)
	if((logRange - LogDivisor) > MAX_SPLITS)
		LogDivisor = logRange - MAX_SPLITS;
	divMin = iMin >> LogDivisor;
	divMax = iMax >> LogDivisor;
	uBinCount = divMax - divMin + ۱;

	// Allocate the bins and determine their sizes
	BinArray = calloc(uBinCount, sizeof(Bin));
	// Memory allocation failure check and clean return with sorted results
    if(!BinArray) {
		printf("Using std::sort because of memory allocation failure\n");
		std::sort(Array, Array + uCount);
		return NULL;
	}

	// Calculating the size of each bin; this takes roughly ۱۰٪ of runtime
	for(u = 0; u < uCount; ++u)
		BinArray[(Array[u] >> LogDivisor) - divMin].uCount++;
	// Assign the bin positions
	BinArray[۰].CurrentPosition = (DATATYPE *)Array;
	for(u = 0; u < uBinCount - ۱; u++) {
		BinArray[u + ۱].CurrentPosition = BinArray[u].CurrentPosition + BinArray[u].uCount;
		BinArray[u].uCount = BinArray[u].CurrentPosition - Array;
	}
	BinArray[u].uCount = BinArray[u].CurrentPosition - Array;

	// Swap into place. This dominates runtime, especially in the swap;
	// std::sort calls are the other main time-user.
	for(u = 0; u < uCount; ++u) {
		for(CurrentBin = BinArray + ((Array[u] >> LogDivisor) - divMin); (CurrentBin->uCount > u);
			CurrentBin = BinArray + ((Array[u] >> LogDivisor) - divMin))
				SWAP(Array + u, CurrentBin->CurrentPosition++);
		// Now that we've found the item belonging in this position,
		// increment the bucket count
		if(CurrentBin->CurrentPosition == Array + u)
			++(CurrentBin->CurrentPosition);
	}

	// If we've bucketsorted, the array is sorted and we should skip recursion
	if(!LogDivisor) {
		free(BinArray);
		return NULL;
	}
	return BinArray;
}

void
SpreadSortBins(DATATYPE *Array, SIZETYPE uCount, SIZETYPE uBinCount, const DATATYPE &iMax
				, const DATATYPE &iMin, Bin * BinArray, SIZETYPE uMaxCount)
{
	SIZETYPE u;
	for(u = 0; u < uBinCount; u++){
		SIZETYPE count = (BinArray[u].CurrentPosition - Array) - BinArray[u].uCount;
		// Don't sort unless there are at least two items to compare
		if(count < ۲)
			continue;
		if(count < uMaxCount)
			std::sort(Array + BinArray[u].uCount, BinArray[u].CurrentPosition);
		else
			SpreadSortRec(Array + BinArray[u].uCount, count);
	}
	free(BinArray);
}

void
SpreadSortRec(DATATYPE *Array, SIZETYPE uCount)
{
	if(uCount < ۲)
		return;		
	DATATYPE iMax, iMin;
	SIZETYPE uBinCount;
	Bin * BinArray = SpreadSortCore(Array, uCount, uBinCount, iMax, iMin);
	if(!BinArray)
		return;
	SpreadSortBins(Array, uCount, uBinCount, iMax, iMin, BinArray,
	 GetMaxCount(RoughLog2Size((SIZETYPE)iMax-iMin), uCount));
}

دو سطح که از بقیه بهترند

یک نتیجه جالب برای الگوریتم‌های این نوع کلی (تقسیم بندی بر اساس مبنا و مرتب‌سازی براساس مقایسه) این است که درجه آن‌ها برای هر عملکرد پیوسته (O(n) است. این نتیجه می‌تواند بدین صورت فراهم شود که اگر اندازه ظرف‌ها بعد از اولین تکرار بیشتر از برخی مقادیر ثابت بود، الگوریتم مرتب‌سازی گسترش یافته حداقل ۲ بار تکرارشود.
اگر داده‌ها درهمه اوقات بر روی برخی توابع پیوسته انتگرال پذیر شناخته شوند این اصلاح مرتب‌سازی گسترش یافته می‌تواند به برخی بهبودهای کارایی بر روی الگوریتم اصلی نائل شود ومی تواند بدترین حالت بهتری داشته باشد. اگر این محدودیت نتواند وابستگی داشته باشد، این تغییر یک سربار اضافی کوچک را به الگوریتم اضافه می‌کند وکوچک تر می‌شود. الگوریتم‌های مشابه دیگر Flashsort (که ساده‌تراست) وAdaptive Left Radix می‌باشند.
Adaptive Left Radix در ظاهرکاملا مشابه می‌باشد، تفاوت اصلی آن در وجود رفتار بازگشتی می‌باشد. درمرتب‌سازی گسترش یافته چک کردن وضعیت‌های بدترین حالت و استفاده از مرتب‌سازی std::sort برای جلوگیری از به وجود آمدن مشکلات کارایی (هرجا که نیاز است) و بازگشت‌های مداوم در Adaptive Left Radix تا وقتی که به اتمام برسد یا داده برای استفاده در مرتب‌سازی درجی به قدرکافی کوچک باشد، انجام می‌شود.

الگوریتم‌های مرتب‌سازی

اصول	پیچیدگی محاسباتی، نمادگذاری o بزرگ،order کلی، لیست‌ها، پایایی، مرتب‌سازی مقایسه‌ای، مرتب‌سازی تطبیقی، شبکه مرتب کردن داده‌ها، مرتب‌سازی عددی
مرتب‌سازی‌های معاوضه‌ای	Bubble sort • Cocktail sort • Odd-even sort • Comb sort • Gnome sort • Quicksort
مرتب‌سازی‌های انتخابی	Selection sort • Heapsort • Smoothsort • Cartesian tree sort • Tournament sort • Cycle sort
مرتب‌سازی‌های درجی	Insertion sort • Shell sort • Tree sort • Library sort • Patience sorting
مرتب‌سازی‌های ادغامی	Merge sort • Polyphase merge sort • Strand sort
مرتب‌سازی‌های توزیعی	American flag sort • Bead sort • Bucket sort • Burstsort • Counting sort • Pigeonhole sort • Proxmap sort • Radix sort • Flashsort
مرتب‌سازی‌های هم‌زمان	Bitonic sorter • Batcher odd-even mergesort • Pairwise sorting network
مرتب‌سازی‌های ترکیبی	Timsort • Introsort • Spreadsort • UnShuffle sort • JSort
مرتب‌سازی‌های مقداری	Spaghetti sort
دیگر	Topological sorting • Pancake sorting
مرتب‌سازی‌های بی‌فایده /مضحک	Bogosort • Stooge sort • Luckysort • Sleep sort

منابع

• Markku Tamminen: Two Levels are as Good as Any. J. Algorithms ۶(۱): ۱۳۸-۱۴۴ (۱۹۸۵)

• Steven J. Ross. The Spreadsort High-performance General-case Sorting Algorithm. Parallel and Distributed Processing Techniques and Applications، Volume ۳، pp.۱۱۰۰–۱۱۰۶. Las Vegas Nevada. ۲۰۰۲.

• http://en.wikipedia.org/wiki/Spreadsort