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

یکی از اولین کارها پس از ذخیره‌سازی داده‌ها چه از طریق مشاهده، چه از طریق اندازه‌گیری مرتب کردن آن‌هاست.

این کار برای بررسی خصوصیات موجود در داده‌ها و همچنین رسم نمودار آن‌ها مفید است.

با مرتب کردن داده‌ها می‌توان ارزش آن‌ها را بالا برد.

فرض کنید بخواهیم 1 عدد را در یک لیست 10 تایی نامرتب پیدا کنیم. اولین راهی که به ذهن هر کسی می‌رسه مقایسه آن عدد با تک تک عددهای موجود در لیست و پیدا کردن عدد مورد نظر است.

در بهترین حالت عدد مورد مقایسه اولین عدد است و در بدترین حالت عدد مورد نظر در لیست وجود ندارد و تعداد گشتن‌ها به اندازه تعداد موجود در لیست می‌شود. پس در یک لیست با 10 عضو حداکثر به 10 مقایسه برای جستجو نیاز داریم.

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

برای جستجو در یک لیستی با 10 عضو حداکثر به 4 مقایسه نیاز داریم.

پس می‌‌شه دید که سرعت پیدا کردن عدد در لیستی مرتب بالاتر از لیستی نامرتب است.

در یک لیست 10 تایی این موضوع اصلا اهمیتی ندارد.

اما در لیستی با 100,000 داده‌ی مختلف پیدا کردن آخرین عدد لیست در حالت نامرتب نیاز به 100,000 مقایسه دارد در حالی که در یک لیست مرتب در بدترین حالت به 17 مقایسه احتیاج دارید. و این اختلاف با بالا رفتن تعداد عضوهای لیست به مراتب بیشتر می‌شود.

2^17 = 131,072 > 100,000

پس مرتب کردن داده‌ها را می‌توان نوعی از بهینه‌سازی در انجام محاسبات نیز در نظر گرفت.

حالا که می‌دانیم چرا مرتب کردن داده‌ها مهم است می‌توانیم راجع به روش‌های مختلف مرتب کردن داده‌ها صحبت کنیم.

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

یکی از الگوریتم‌های موجود برای مرتب کردن الگوریتم مرتب‌ساز دَرجی (وارد کردنی) Insertion Sort است. چون که با وارد کردن هر عضو لیست نامرتب به لیست دیگر و مقایسه‌ی آن با عضو‌های دیگر مرتب‌سازی را انجام می‌دهیم.

مراحل این الگوریتم به صورت زیر است:

1. اولین عضو لیست نامرتب را وارد اولین خانه لیست جدید می‌کنیم. لیست جدید مرتب شده است چون که تنها دارای یک عضو است.

2. عضو بعدی لیست نامرتب را وارد خانه‌ی بعدی لیست جدید می‌‌کنیم. مقدار وارد شده‌ی جدید را با مقدار قبلی مقایسه می‌کنیم. 3 حالت ممکن است به وجود بیاید:

- مقدار دیگری وجود ندارد که بخواهیم مقدار وارد شده را با آن مقایسه کنیم. پس این به این معناست که این مقدار کوچک‌ترین مقدار است که در ابتدای لیست قرار گرفته است.

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

- کوچک‌‌تر از مقدار قبلی است پس باید جای خودش را با عضو قبلی عوض کند.

3. مرحله‌ی 2 را آن‌قدر تکرار می‌کنیم تا لیست مرتب شود.

این الگوریتم به شکل زیر عمل می‌کند:

اگر بخواهیم کدی در اکسل بنویسیم تا این الگوریتم را روی یک لیست اعمال کند می‌توانیم کد زیر را بنویسیم.

کد زیر تابعی را ایجاد می‌کند که اگر آرایه‌ای به صورت ورودی به این تابع بدهیم، آرایه‌ی مرتب شده را بر می‌گرداند.

کد تابع insertion sort

Function InsertionSort(rng As Range) As Variant1 تابعی را تعریف می‌کنیم که یک لیست نامرتب را به عنوان ورودی دریافت می‌کند و لیست مرتب را باز می‌گرداند
   Dim i As Integer 2
   Dim A() As Variant3
   nr = rng.Rows.Count4 تعداد سطرهای لیست ورودی به متغیر nr نسبت داده می‌شود
   nc = rng.Columns.Count5
   ReDim A(nr) As Variant6
   For i = LBound(A) To UBound(A)7 داده‌‌های موجود در لیست ورودی (نامرتب) را به آرایه‌ی A وارد می‌کنیم
      A(i) = rng(i)8
   Next i9
   For int1 = 1 To UBound(A)10 حلقه‌ی تکرار for اول برای چک کردن داده‌های موجود در آرایه A
      varTemp = A(int1)11 تعریف متغیر کمکی varTemp
      For int2 = int1 To 1 Step -112 حلقه‌ی تکرار for دوم برای مقایسه داده وارد شده با داده‌های قبلی
         If varTemp < A(int2) Then13
           A(int2 + 1) = A(int2)14
           A(int2) = varTemp15
         End If16
      Next int217
   Next int118
  InsertionSort = WorksheetFunction.Transpose(A)19 برگرداندن لیست مرتب شده توسط تابع
End Function20
****برای کپی کردن یک ستون کافی است کل جدول را در اکسل به صورت متن ساده کپی کنید و سپس ستون مورد نظر را کپی کنید. در Mozila با نگه داشتن دکمه کنترل می‌توان یک ستون را کپی کرد.

در هنگام استفاده از توابع آرایه‌ای لازم است که پس از نوشتن فرمول به جای کلید Enter از ترکیب Ctrl + Shift + Enter استفاده شود.

بدترین حالت عملکرد چنین الگوریتمی زمانی رخ می‌دهد که لیست ورودی به صورت معکوس مرتب شده باشد.

در چنین حالتی هر عدد باید با تمام اعداد قبل از خودش در لیست مقایسه شود و جای خودش را با آن عوض کند.

مثلا عدد سوم لیست باید با دو عدد قبلی خود مقایسه و چون از آن‌ها کوچک‌تر است باید جایش را با آن‌ها عوض کند. عدد دهم لیست باید با نه عدد قبل از خود مقایسه شود و عدد n ام لیست باید با n-1 عدد قبل از خودش مقایسه شود. عدد اول هم نیاز به مقایسه ندارد.

پس در بدترین حالت:

برای عدد اول نَه به مقایسه نیاز داریم نَه به جابجایی. 0*2

برای عدد دوم به یک مقایسه و یک جابجایی نیاز داریم. 1*2

برای عدد سوم به دو مقایسه و دو جابجایی نیاز داریم. 2*2

...

برای عدد دهم به نه مقایسه و نه جابجایی نیاز داریم. 9*2

و اگر آن‌ها را با هم جمع بزنیم:

2*0 + 2*1 + 2*2 + 2*3 + … + 2*9 = 2 * (1 + 2 + 3 + … + 9) = 90

به طور کل به 90 عمل برای مرتب‌سازی یک لیست 10 تایی در بدترین حالت نیاز داریم.

حال اگر لیستی با n عدد داشتیم تعداد عمل‌های مختلف در بدترین حالت را می‌توان به روش مشابه به صورت زیر محاسبه کرد:

2 * (1 + 2 + … + n-1)

که برابر خواهد شد با  n(n-1) یا n^2 - n. نحوه محاسبه

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

نمودار آن به صورت زیر خواهد بود.

می‌تونید ببینید که برای مرتب کردن لیستی با 45,000 عضو در حدود 2 میلیارد محاسبه مورد نیاز است و 45,000 عدد نسبتا کوچکی است. جدولی با 256 سطر و 256 ستون دارای 65536 خانه است.

چنین الگوریتمی برای استفاده در لیست‌های بزرگ نمی‌تواند کارساز باشد. برای همین انواع الگوریتم‌های دیگر برای مرتب‌سازی وجود دارند.

البته در اکسل برای استفاده از توابع مرتب‌ساز به مشکل خاصی برخورد نمی‌کنیم. چون که میایم و صورت مساله رو پاک می‌کنیم. در محیط اکسل نمی‌توان به توابع، ورودی با اندازه بزرگ‌تر از 16 بیت یا 65536 وارد کرد و در صورت وارد کردن لیستی بزرگ‌تر تابع پیام خطا را بر می‌گرداند. شاید هم بشه ولی من نمی‌دونم.

منبع:

سایت Brilliant

سایت stackoverflow