مرتب سازی مستقیم الگوریتم ها و ساختارهای داده تابع روش گنجاندن ساده ج

این روش به طور گسترده در هنگام بازی با ورق استفاده می شود. عناصر (کارت ها) از نظر ذهنی به دنباله "آماده" A1 ... An و دنباله اصلی Ai ... An تقسیم می شوند. در هر مرحله با شروع از i=2 و افزایش I هر بار یک، عنصر i از دنباله اصلی استخراج شده و به دنباله تمام شده منتقل می شود و در جای مناسب قرار می گیرد.

در بالا به عنوان مثال، فرآیند مرتب‌سازی با گنجاندن هشت عدد به‌طور تصادفی انتخاب شده است: الگوریتم این مرتب‌سازی به شرح زیر است:

برای i:=2 تا n انجام

گنجاندن x در جای متناظر در میان یک ... a[j];

در فرآیند واقعی جستجوی یک مکان مناسب، مقایسه‌ها و حرکات متناوب از طریق دنباله راحت است که X را به عنوان مثال غربال کنیم، یعنی X با عنصر بعدی aj مقایسه می‌شود، و سپس یکی از X در یک فضای خالی قرار می‌گیرد. فضا، یا aj به سمت راست منتقل می شود و فرآیند به سمت چپ "می رود". لطفاً توجه داشته باشید که اگر یکی از دو شرط مختلف زیر برآورده شود، فرآیند الک کردن ممکن است به پایان برسد:

1. عنصر aj با کلید کمتر از کلید X یافت می شود.

2. انتهای سمت چپ دنباله تمام شده رسیده است.

این مورد معمولی از یک فرآیند تکراری با دو شرط پایان به ما اجازه می دهد تا از تکنیک مانع شناخته شده (سنتینل) استفاده کنیم. با قرار دادن یک مانع a0 با مقدار X می توان آن را به راحتی در اینجا اعمال کرد.

تجزیه و تحلیل روش گنجاندن مستقیم. تعداد مقایسات کلیدی (Ci) در طول غربال کردن i-ام حداکثر برابر با i - 1، حداقل 1 است. اگر فرض کنیم که همه جایگشت‌های n کلید به یک اندازه محتمل هستند، میانگین تعداد مقایسه‌ها i/2 است. تعداد انتقال (تخصیص عناصر) Mi برابر است با Ci + 2 (از جمله مانع). بنابراین، تعداد کل مقایسه ها و تعداد نقل و انتقالات به شرح زیر است:

ذخیره = (n2 + n - 2)/4،

Сmax = (n2 + n - 4)/4،

M min = З*(n - 1)،

M ave = (n2 + 9n - 10)/4،

M max = (n2 + 3n - 4)/2.

حداقل برآوردها در مورد یک توالی اولیه از قبل مرتب شده از عناصر رخ می دهد، در حالی که بدترین تخمین ها زمانی رخ می دهد که آنها در ابتدا به ترتیب معکوس مرتب شوند. از برخی جهات، مرتب سازی دربرگیرنده رفتار واقعاً طبیعی از خود نشان می دهد. واضح است که الگوریتم فوق فرآیند مرتب‌سازی پایدار را توصیف می‌کند: ترتیب عناصر با کلیدهای مساوی بدون تغییر باقی می‌ماند.

اگر به این نکته توجه داشته باشید که دنباله تمام شده (a1 ... ai-1 که باید یک عنصر جدید را در آن وارد کنید، خود قبلاً سفارش داده شده است، الگوریتم با گنجاندن مستقیم را می توان به راحتی بهبود بخشید. طبیعی است که روی آن تمرکز کنید. جستجوی دودویی که در آن سعی می شود با وسط دنباله تمام شده مقایسه شود و سپس فرآیند نصف کردن تا یافتن نقطه درج ادامه می یابد. این الگوریتم مرتب سازی اصلاح شده را روش درج باینری می نامند.

این روش به طور گسترده در هنگام بازی با ورق استفاده می شود. عناصر (کارت ها) از نظر ذهنی به دنباله های "آماده" A 1 , A 2 ,…, A i -1 , و بخش "باقیمانده" ( مرتب نشده) تقسیم می شوند: A i , A i +1 ,…, A N .

ماهیت روش این است که در هر مرحله i (با شروع از i = 2)، عنصر i از قسمت مرتب نشده حذف می شود و در قسمت "آماده" قرار می گیرد و در جای مناسب قرار می گیرد.

الگوریتم متن روش:

1. شروع.

2. حلقه بزنید تا i مقادیری از 2 تا N داشته باشد،
مرحله = 1:

الف) عنصر i-امین (A(i)) را در سلول A(0) قرار دهید.

ب) j = -1 را اختصاص دهید، یعنی j برابر با تعداد عنصری است که در سمت چپ موضوع (i-th) قرار دارد و بنابراین در دنباله "آماده" قرار می گیرد.

ج) اگر A(0) ≥ A(j)، سپس عنصر A(0) را در سلول A(j+1) قرار دهید، در غیر این صورت عنصر A(j) را در سلول A(j+1) قرار دهید، مقدار را کاهش دهید. از j به یک و مرحله c را دوباره انجام دهید.

در شکل شکل 1 بلوک دیاگرام مرتب سازی با استفاده از روش گنجاندن مستقیم را نشان می دهد.

روش به شرح زیر عمل می کند: در مرحله i-ام (شروع از i = 2)، عنصر i-ام در یک سلول آزاد قرار می گیرد (به عنوان مثال، A(0)). این عنصر با عنصر ایستاده در قسمت "تمام" سمت چپ آن مقایسه می شود. اگر عنصر A(0) کوچکتر باشد، آنگاه عنصر مقایسه شده (j-امین عنصر) با یک موقعیت به سمت راست منتقل می شود و پس از آن عنصر بعدی برای مقایسه گرفته می شود. اگر عنصر A(0) در هنگام مقایسه کوچکتر نباشد، بلافاصله پس از مقایسه عنصر در محل قرار می گیرد.

برنج. 1. فلوچارت مرتب سازی با استفاده از روش گنجاندن مستقیم

در شکل شکل 2 نمونه ای از انجام مرتب سازی با استفاده از روش گنجاندن مستقیم را نشان می دهد.

سکانس اصلی
	A (0)
من = 2
من = 3
من = 4
من = 5
من = 6
من = 7
من = 8
نتیجه

برنج. 2. نمونه ای از مرتب سازی شامل مستقیم

مرتب سازی مستقیم برای مواردی مناسب تر است که داده های مرتب شده به صورت متوالی (یکی پس از دیگری) وارد شوند.

مرتب سازی انتخاب مستقیم

ماهیت روش به شرح زیر است. کوچکترین عنصر در قسمت "باقی مانده" (مرتب نشده) انتخاب شده و با عنصر اول (در همان قسمت مرتب نشده) تعویض می شود. پس از این، طول قسمت مرتب نشده توسط یک عنصر کاهش می یابد (اولی)، و کل فرآیند با (n – 1) عنصر، سپس با (n – 2) عنصر و غیره ادامه می یابد تا زمانی که فقط یک عنصر وجود داشته باشد. چپ. بزرگترین عنصر.

این روش از جهاتی مخالف روش گنجاندن مستقیم است. در روش گنجاندن مستقیم، در هر مرحله، فقط یک عنصر بعدی و تمام عناصر قسمت از قبل "آماده" دنباله در نظر گرفته می شود که در میان آنها نقطه درج این عنصر بعدی یافت می شود. و در روش انتخاب مستقیم، برای یافتن یک عنصر (حداقل)، تمام عناصر قسمت مرتب نشده مورد بررسی قرار می گیرند و این عنصر حداقل به عنوان عنصر دیگری در قسمت "آماده" قرار می گیرد.

الگوریتم متن روش:

1. شروع.

2. حلقه بزنید تا i مقادیری از 1 تا N – 1 داشته باشد.
مرحله = 1:

الف) عنصر جریان (i-th) را در برخی از سلول های حافظه (X) قرار دهید و شماره سریال (i) عنصر فعلی (در متغیر K) را به خاطر بسپارید.

ب) یک حلقه را اجرا کنید در حالی که j مقادیری از i + 1 (یعنی از عنصر کنار i) تا N دارد، مرحله = +1:

بدنه حلقه: اگر X > A(j) باشد، عنصر A(j) را در سلول X قرار دهید و عدد آن را در سلول K به خاطر بسپارید.

ج) A(K) = A(i) و A(i) = X را اختصاص دهید.

در شکل شکل 3 نمونه ای از انجام مرتب سازی با استفاده از روش انتخاب مستقیم را نشان می دهد.

سکانس اصلی	44						06
من = 1		55	12
من = 2			55			18
من = 3				42		55
من = 4					94		44
من = 5						55	94
من = 6							94	67
من = 7

برنج. 3. نمونه ای از مرتب سازی انتخاب مستقیم

مرتب سازی شامل مستقیم، مانند مرتب سازی انتخاب ساده، معمولاً برای آرایه هایی استفاده می شود که حاوی عناصر تکراری نیستند.

مرتب سازی با روش گنجاندن مستقیم، مانند همه مواردی که در بالا توضیح داده شد، در مراحل انجام می شود. در مرحله k ام، در نظر گرفته می شود که بخشی از آرایه حاوی اولین عناصر k-1 از قبل مرتب شده است، یعنی

a ≤ a ≤ ... ≤ a .

در مرحله بعد، شما باید عنصر k را بگیرید و در قسمت مرتب شده آرایه جایی برای آن انتخاب کنید تا پس از درج ترتیب آن نقض نشود، یعنی باید یک j پیدا کنید (1 ≤ j ≤ k -1) به طوری که a [j] ≤ a[ k]< a. Затем вставить элемент а [k] на найденное место.

با هر مرحله، قسمت مرتب شده آرایه افزایش می یابد. برای انجام مرتب سازی کامل، باید n-1 مرحله را انجام دهید.

بیایید با یک مثال به این روند نگاه کنیم. فرض کنید می خواهید یک آرایه از 10 عنصر را به ترتیب صعودی با استفاده از روش گنجاندن مستقیم مرتب کنید.

1 - مرحله ام

13 6 8 11 3 1 5 9 15 7 بخشی از آرایه را از یک عنصر در نظر می گیریم

ment (13). شما باید مورد دوم را در آن قرار دهید

عنصر آرایه (6) به طوری که مرتب شود

حفظ شده است از 6< 13, вставляем

6 به مقام اول. قسمت مرتب شده

آرایه شامل دو عنصر است (6 13).

3 - مرحله ام

6 8 13 11 3 1 5 9 15 7 عنصر بعدی 11 است. در قسمت مرتب آرایه در مکان سوم نوشته می شود، از 11 > 8، اما 11< 13.

5- گام

3 6 8 11 13 1 5 9 15 7 به همین دلیل 1 را به عنوان اولین می نویسیم

6 - گام

1 3 6 8 11 13 5 9 15 7 از آنجایی که 5 > 3، اما 5< 6 то место 5 в упоря-

قسمت تمام شده سوم است.

7 -گام

1 3 5 6 8 11 13 9 15 7 جای عدد 9 ششمین است.

8 -گام

1 3 5 6 8 9 11 13 15 7 تعیین مکان برای ماقبل آخر

عنصر 15. معلوم می شود که این عنصر

آرایه در حال حاضر در محل است.

9 -گام

1 3 5 6 8 9 11 13 15 7 تنها چیزی که باقی می ماند یافتن یک مکان مناسب است

عنصر آخر (7).

1 3 5 6 7 8 9 11 13 15 آرایه کاملا مرتب شده است.

اکنون می توانیم به طور خلاصه بخشی از الگوریتم مرتب سازی را با استفاده از روش گنجاندن مستقیم شرح دهیم:

برای k: = 2 تا n انجام شود

(از آنجایی که مرتب سازی را با یافتن یک مکان مناسب برای a شروع می کنیم، i از 2 تا n متغیر است)

x را در یک مکان مناسب در a، ...، a[k] وارد کنید.

باقی مانده است که به این سوال پاسخ دهیم که چگونه مکان مناسبی برای عنصر x پیدا کنیم. بیایید به صورت زیر عمل کنیم: از طریق عناصر واقع در سمت چپ x (یعنی آنهایی که قبلاً مرتب شده اند) نگاه می کنیم و به ابتدای آرایه حرکت می کنیم. شما باید از طریق عناصر a[j] نگاه کنید، j از k-1 تا 1 متغیر است. این نگاه باید زمانی پایان یابد که یکی از شرایط زیر برآورده شود:

· عنصر a[j] پیدا شد< x, что говорит о необходимости вставки x между a и a[j].

· انتهای سمت چپ قسمت مرتب آرایه رسیده است، بنابراین، در وهله اول باید x را وارد کنیم.

تا زمانی که یکی از این شرایط برآورده شود، عناصر در حال مشاهده را به موقعیت اول به سمت راست منتقل می کنیم، در نتیجه فضای زیر x در قسمت مرتب شده آزاد می شود.

برنامه مرتب سازی مستقیم:

برنامه n3; (به ترتیب نزولی مرتب کنید)

نوع ar=آرایه عدد صحیح;

مرتب سازی رویه3(var a:ar);

var i,j,x,k:integer;

برای k:=2 تا n انجام دهید

x:=a[k]; j:=k-1;

در حالی که (j>0)و(x>=a[j]) انجام می دهند

writeln("آرایه منبع را وارد کنید:");

برای i:=1 تا n را بخوانید(a[i]);

writeln("آرایه مرتب شده:");

برای i:=1 تا n بنویسید(a[i]," ");

هدف کاربررسی مرتب‌سازی آرایه‌ها با استفاده از روش گنجاندن مستقیم و ارزیابی اثربخشی این الگوریتم.

اطلاعات کلی

مرتب سازی شامل مستقیم، مانند مرتب سازی انتخاب ساده، معمولاً برای آرایه هایی استفاده می شود که حاوی عناصر تکراری نیستند. مرتب سازی با این روش به صورت متوالی گام به گام انجام می شود. در مرحله k-ام، در نظر گرفته می شود که بخشی از آرایه حاوی اولین عناصر k-1 از قبل مرتب شده است، یعنی. در مرحله بعد باید عنصر kth را بردارید و در قسمت مرتب شده آرایه مکانی را برای آن انتخاب کنید تا پس از درج ترتیب آن مختل نشود، یعنی باید طوری پیدا کنید که. سپس باید عنصر a[k] را در محل پیدا شده وارد کنید. با هر مرحله، قسمت مرتب شده آرایه افزایش می یابد. برای انجام مرتب سازی کامل، باید n-1 مرحله را انجام دهید. باقی مانده است که به این سؤال پاسخ دهیم که چگونه مکان مناسبی برای عنصر x جستجو کنیم. بیایید به صورت زیر عمل کنیم: از طریق عناصر واقع در سمت چپ x (یعنی آنهایی که قبلاً مرتب شده اند) نگاه می کنیم و به ابتدای آرایه حرکت می کنیم. شما باید از طریق عناصر a[j] نگاه کنید، j از k-l به 1 تغییر می کند. چنین اسکن زمانی پایان می یابد که یکی از شرایط زیر برآورده شود: عنصر a[j] پیدا شود. مثال اجازه دهید به طور خلاصه بخشی از الگوریتم مرتب سازی را شرح دهیم. با استفاده از گنجاندن مستقیم: برای k:= 2 تا n x:= a[k]; j:= k-1; (x را در یک مکان مناسب در a، ...، a[k] وارد کنید) (برای این کار یک حلقه را سازماندهی می کنیم که در حالی که اجرا می شود) (j > 0 و x

تکلیف تست

برنامه ای بنویسید تا آخرین عنصر یک آرایه را بعد از اولین عنصر منفی همان آرایه وارد کند.

گزینه های وظیفه

توجه!!! مگر اینکه صریحاً خلاف آن ذکر شده باشد، داده های ورودی (آرایه اصلی) و داده های خروجی (آرایه مرتب شده) باید به صورت یک فایل متنی حاوی اعداد صحیح تولید شوند! برای همه کارها، ابتدا رویه ای برای مرتب سازی یک آرایه با استفاده از روش گنجاندن مستقیم بنویسید. 1. یک سری حاوی n عنصر داده می شود. آنها را به ترتیب صعودی مرتب کنید و همه عناصر تکراری را کنار بگذارید. 2. حالت یک سری داده شده را تعیین کنید - مقداری که اغلب در بین عناصر آن رخ می دهد. 3. مجموعه داده های اصلی مجموعه ای از سوابق متشکل از نام خانوادگی، سن و مدت خدمت است. چاپ این لیست: 1) به ترتیب حروف الفبا. 2) به ترتیب افزایش سن؛ 3) به منظور افزایش طول خدمت. 4. رویه ای برای مرتب سازی به ترتیب نزولی بنویسید. 5. با توجه به یک سری اعداد صحیح. تمام اعداد مختلف موجود در این سری را به ترتیب صعودی دریافت کنید. 6. یک سری از n عدد صحیح مختلف داده می شود. اعداد صحیح مختلف را بدست آورید به طوری که 7. اعداد صحیح داده شده پس از حذف تمام عبارت های دارای مقدار از آن، بزرگترین مقدار را در این دنباله بیابید 8. طبیعی داده شده است اعداد نتایج n ورزشکار در مسابقه 100 متر است که در صدم ثانیه اندازه گیری می شود. تیمی از چهار بهترین دونده برای شرکت در مسابقه امدادی 4×100 تشکیل دهید، یعنی یکی از چهار عدد طبیعی i، j، k را مشخص کنید. به طوری که مجموع کمترین اهمیت را دارد. 9. با توجه به n نقطه تصادفی مستقل، با مختصات (xi; yi)، که به طور یکنواخت در دایره ای به شعاع 1 با مرکز در مبدا توزیع شده اند. برنامه ای بنویسید که نقاط را به ترتیب افزایش فاصله از مرکز مرتب کند. 10. با توجه به n عدد صحیح دو رقمی مثبت. در نظر گرفتن هر عدد به عنوان یک جفت رقم از بازه 0-9، آنها را (اعداد) به ترتیب صعودی مرتب کنید. 11. با توجه به n نقطه در هواپیما. یک (n-1)-link چندخط بسته غیر خود متقاطع را پیدا کنید که از همه این نقاط عبور می کند. (قطعات مجاور چندخط مجاز هستند روی همان خط مستقیم قرار گیرند.) اشاره. بیایید سمت چپ ترین نقطه (یعنی نقطه ای با کوچکترین مختصات x) را بگیریم و پرتوهایی را از آن به تمام نقاط دیگر رسم کنیم. حالا بیایید این پرتوها را از پایین به بالا مرتب کنیم و نقاط یک پرتو را با فاصله از ابتدای پرتو مرتب کنیم (این کار برای همه پرتوها به جز پایین و بالا انجام می شود). چند خط از نقطه انتخاب شده (سمت چپ) در امتداد پرتو پایین، سپس در امتداد تمام پرتوهای دیگر (به ترتیب توضیح داده شده) خارج می شود و در امتداد پرتو بالایی باز می گردد. 12. با توجه به n نقطه در هواپیما. بدنه محدب آنها را بسازید - شکل محدب حداقل حاوی آنها. (حلقه لاستیکی که روی میخ‌هایی که در یک تخته قرار گرفته‌اند - پوسته محدب آنها کشیده شده است.) دستورالعمل. بیایید نکات را مرتب کنیم. سپس با در نظر گرفتن یک به یک نقاط، بدنه محدب نقاطی که قبلا در نظر گرفته شده را می سازیم.

روش‌های زیادی برای مرتب‌سازی (ترتیب) مقادیر به ترتیب صعودی یا نزولی در یک آرایه [Wirth، Knuth] ایجاد شده‌اند. t 3. بیایید سه مورد از آنها را در نظر بگیریم، برای قطعیت بودن، با توجه به اینکه اولین n، n=6، عناصر آرایه X

در هر مرحله i-ام بعدی، i=2, 3,…,n-1، مقدار سلول (i+1) آرایه با مبادله موقعیت با عدد قبلی به سمت کاهش شاخص سلول حرکت می کند. سلول تا زمانی که معلوم نمی شود که سلول قبلی دارای تعداد کمتری است.

از موارد فوق چنین استنباط می شود که هنگام اجرای روش گنجاندن مستقیم، حلقه بیرونی باید n-1 بار اجرا شود و حداکثر تعداد ممکن اجرای حلقه داخلی که در بدنه آن باید مقایسه و بازآرایی اعداد انجام شود. از 1 به n-1 افزایش خواهد یافت. با این حال، حلقه داخلی باید به گونه‌ای سازماندهی شود که در صورت وقوع این شرط تمام شود یا اصلاً اجرا نشود: مقدار در سلول آرایه قبلی کمتر از مقدار فعلی است.

در مثال ما:

وقتی i=2 باشد، عدد 15 از سلول X 3 به صورت متوالی با عدد 34 از سلول X 2 و سپس با عدد 21 از سلول X 1 مبادله می کند.

هنگامی که i=4 است، عدد 25 از سلول X 5 با عدد 34 از سلول X 3 مبادله می کند.

در زیر بخشی از یک برنامه برای مرتب سازی به ترتیب صعودی n عنصر اول آرایه X با استفاده از روش گنجاندن مستقیم (شامل با حفظ ترتیب) آمده است.

برای i:=1 تا n-1 انجام دهید

2. در حالی که (X 0) انجام دهید

3. R:=X[j];

   X[j]:=X;

   X:=R;

برای ترتیب دادن اعداد در یک آرایه به ترتیب نزولی، در هر مرحله کافی است شرط جایگشت اعداد در سلول های همسایه آرایه را به عکس تغییر دهید، یعنی تبادل مقادیر سلول های همسایه در خانه انجام شود. در صورتی که قبلی کمتر از فعلی باشد.

روش تبادل مستقیم (روش حبابی).

این روش، مانند روش قبلی، مبتنی بر تبادل مقادیر سلول های همسایه آرایه است، اما از همان مرحله اول در تجزیه و تحلیل متوالی، هنگام حرکت از یک سر آرایه به انتهای دیگر، همه جفت های سلول های مجاور آرایه درگیر هستند.

در مرحله اول، به صورت متوالی، برای j = n، n-1، ...، 2، مقادیر سلول های همسایه آرایه مقایسه می شوند و اگر شرط X j<Х j-1 выполняется их перестановка, в результате чего наименьшее число оказывается в ячейке Х 1 .

در مثال ما، پس از اتمام مرحله اول، داده های آرایه به صورت زیر قرار می گیرند:

در هر مرحله بعدی، تعداد جفت های سلولی که باید بررسی شوند 1 کاهش می یابد. به طور کلی، در هر مرحله i، i=1، 2، 3، ...، n-1، فرآیند برای j از n تا i+1، به ویژه برای i= n-1 – فقط یک بار برای سلول های n و (n-1)-امین.

از مطالب فوق چنین بر می آید که هنگام اجرای روش تبادل مستقیم، حلقه بیرونی باید n-1 بار اجرا شود و تعداد اجرای حلقه داخلی که در بدنه آن باید مقایسه و بازآرایی اعداد انجام شود کاهش می یابد. از n-1 تا 1.

منشأ اصطلاح "روش حباب" به شرح زیر توضیح داده می شود: اگر آرایش عمودی سلول های آرایه را با افزایش شاخص از بالا به پایین تصور کنید، آنگاه کوچکترین تعداد مورد نظر مانند حباب در آب بالا می رود.

در مثال ما

وقتی i=3 جایگشت به حالت زیر از آرایه منجر می شود

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

روش تبادل مستقیم اصلاح شده (روش حباب اصلاح شده).

همانطور که از مثال عددی بالا مشاهده می شود، مشخص شد که آرایه بعد از مرحله چهارم مرتب شده است، یعنی می توان حلقه بیرونی را نه n-1 بار، بلکه کمتر، زمانی که مشخص شد که آرایه است، اجرا کرد. قبلا سفارش داده شده این بررسی بر اساس موارد زیر است: اگر هیچ جایگشتی در طول اجرای حلقه داخلی وجود نداشت، آرایه از قبل مرتب شده است و می توانید از حلقه بیرونی خارج شوید. یک متغیر نوع Boolean به عنوان نشانه ای برای اینکه آیا جایگشت انجام شده است استفاده می شود: قبل از ورود به حلقه داخلی، یک مقدار به عنوان مثال False داده می شود و زمانی که جایگشت انجام می شود، مقدار دیگری به عنوان مثال، درست است، واقعی.

بدیهی است تأثیر استفاده از روش حباب اصلاح شده نسبت به روش اصلاح نشده در سرعت بخشیدن به مرحله مرتب سازی در صورتی مشاهده خواهد شد که توالی اصلی اعداد نزدیک به مرتب شدن در جهت مورد نظر باشد. در حالت شدید، زمانی که آرایه از قبل به روش دلخواه مرتب شده باشد، بدنه حلقه بیرونی فقط یک بار اجرا می شود.