چندین الگوریتم اساسی برای حل مشکل مرتب‌سازی یک آرایه وجود دارد. یکی از معروف ترین آنها درج مرتب سازی است. این روش به دلیل وضوح و سادگی، اما کارایی کم، عمدتاً در آموزش برنامه نویسی مورد استفاده قرار می گیرد. این به شما امکان می دهد مکانیسم های مرتب سازی اولیه را درک کنید.
شرح الگوریتم
ماهیت الگوریتم مرتب سازی درج این است که یک بخش به درستی مرتب شده در داخل آرایه اولیه تشکیل می شود. هر عنصر یک به یک با قسمت بررسی شده مقایسه می شود و در جای مناسب قرار می گیرد. بنابراین، پس از تکرار در میان همه عناصر، آنها به ترتیب درست ردیف می شوند.
ترتیب انتخاب عناصر می تواند هر کدام باشد، آنها را می توان خودسرانه یا طبق برخی از الگوریتم ها انتخاب کرد. اغلب، شمارش متوالی از ابتدای آرایه، جایی که یک قطعه مرتب شده تشکیل می شود، استفاده می شود.
شروع مرتب‌سازی ممکن است به این شکل باشد:
- اولین عنصر آرایه را بگیرید.
- از آنجایی که چیزی برای مقایسه با آن وجود ندارد، خود عنصر را مطابق سفارش بگیریددنباله.
- به دومین مورد بروید.
- بر اساس قانون مرتب سازی آن را با اولین مورد مقایسه کنید.
- در صورت لزوم، عناصر را در مکان‌ها عوض کنید.
- دو عنصر اول را به عنوان یک دنباله مرتب در نظر بگیرید.
- به سومین مورد بروید.
- آن را با دومی مقایسه کنید، در صورت لزوم تعویض کنید.
- اگر جایگزینی ساخته شده است، آن را با اولی مقایسه کنید.
- سه عنصر را به عنوان یک دنباله مرتب در نظر بگیرید.
و به همین ترتیب تا پایان آرایه اصلی ادامه دهید.
مرتب سازی درج واقعی
برای وضوح، شایسته است مثالی از نحوه استفاده از این مکانیسم مرتب‌سازی در زندگی روزمره ارائه دهیم.
برای مثال یک کیف پول بگیرید. اسکناس های صد، پانصد و هزار دلاری در محفظه اسکناس بی نظم است. این یک آشفتگی است، در چنین توده ای دشوار است که بلافاصله تکه کاغذ مناسب را پیدا کنید. آرایه اسکناس ها باید مرتب شوند.
اولین اسکناس 1000 روبلی است و بلافاصله بعد از آن - 100. صد را می گیریم و جلویش می گذاریم. سومین مورد متوالی 500 روبل است، مکان مناسب برای آن بین صد تا هزار است.
به همین ترتیب هنگام بازی "احمق" کارت های دریافتی را مرتب می کنیم تا حرکت در آنها آسان تر شود.
اپراتورها و توابع کمکی
روش مرتب‌سازی درج، یک آرایه اولیه برای مرتب‌سازی، یک تابع مقایسه، و در صورت لزوم، تابعی را به عنوان ورودی می‌گیرد که قانون شمارش عناصر را تعیین می‌کند. اغلب به جای آن استفاده می شودبیانیه حلقه معمولی.
عنصر اول خود یک مجموعه مرتب شده است، بنابراین مقایسه از دومی شروع می شود.
الگوریتم اغلب از یک تابع کمکی برای مبادله دو مقدار (swap) استفاده می کند. از یک متغیر موقت اضافی استفاده می کند که حافظه را مصرف می کند و سرعت کد را کمی کند می کند.
یک جایگزین این است که گروهی از عناصر را جابجا کنید و سپس عنصر فعلی را در فضای آزاد قرار دهید. در این حالت، انتقال به عنصر بعدی زمانی اتفاق می‌افتد که مقایسه نتیجه مثبتی را به همراه داشته باشد که نشان‌دهنده ترتیب صحیح است.
نمونه های پیاده سازی
پیاده سازی خاص تا حد زیادی به زبان برنامه نویسی مورد استفاده، نحو و ساختار آن بستگی دارد.
پیاده سازی کلاسیک C با استفاده از یک متغیر موقت برای تبادل مقادیر:
int i, j, temp; برای (i=1; i =0; j--) { if (array[j] < temp) break; آرایه[j + 1]=آرایه[j]; آرایه[j]=دما; } }
پیاده سازی PHP:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
در اینجا، ابتدا همه عناصری که با شرط مرتب سازی مطابقت ندارند به سمت راست منتقل می شوند و سپس عنصر فعلی در فضای آزاد درج می شود.
کد جاوا با استفاده از حلقه while:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
معنای کلی کد بدون تغییر باقی می ماند: هر عنصر آرایه به ترتیب با عناصر قبلی مقایسه می شود و در صورت لزوم با آنها تعویض می شود.
زمان اجرای تخمینی
بدیهی است که در بهترین حالت، ورودی الگوریتم آرایه ای خواهد بود که از قبل به روش صحیح مرتب شده است. در این شرایط، الگوریتم به سادگی باید هر عنصر را بررسی کند تا مطمئن شود که در جای مناسبی بدون انجام مبادله قرار دارد. بنابراین، زمان اجرا مستقیماً به طول آرایه اصلی O(n) بستگی دارد.
بدترین حالت ورودی آرایه ای است که به ترتیب معکوس مرتب شده اند. این به تعداد زیادی جایگشت نیاز دارد، تابع زمان اجرا به تعداد عناصر مربع بستگی دارد.
تعداد دقیق جایگشت برای یک آرایه کاملاً نامرتب را می توان با استفاده از فرمول محاسبه کرد:
n(n-1)/2
، که در آن n طول آرایه اصلی است. بنابراین، برای مرتب کردن 100 عنصر به ترتیب صحیح، 4950 جایگشت نیاز است.
روش درج برای مرتب سازی آرایه های کوچک یا جزئی مرتب شده بسیار کارآمد است. با این حال، به دلیل پیچیدگی زیاد محاسبات، استفاده از آن در همه جا توصیه نمی شود.
این الگوریتم به عنوان یک ابزار کمکی در بسیاری از روش‌های مرتب‌سازی پیچیده‌تر استفاده می‌شود.
مقادیر مساوی را مرتب کنید
الگوریتم درج متعلق به دسته های به اصطلاح پایدار است. به این معنی،که عناصر یکسان را عوض نمی کند، اما نظم اصلی آنها را حفظ می کند. شاخص پایداری در بسیاری از موارد برای ترتیب صحیح مهم است.
موضوع بالا یک مثال تصویری عالی از مرتب سازی در یک رقص است.
