تفاوت کلیدی – مرتب‌سازی درج در مقابل مرتب‌سازی انتخابی
مرتب‌سازی درج و مرتب‌سازی انتخاب دو الگوریتم مرتب‌سازی هستند که برای مرتب‌سازی مجموعه‌ای از داده‌ها استفاده می‌شوند. گاهی اوقات لازم است که داده ها را به ترتیب خاصی مرتب کنیم. الگوریتم های مرتب سازی مکانیسم هایی برای مرتب سازی مجموعه ای از داده ها هستند. در مرتب سازی، داده ها بر اساس یک ترتیب عددی یا واژگانی مرتب می شوند. اگر داده ها به درستی مرتب شوند، جستجوی داده ها سریعتر آسان خواهد بود. اگر شماره‌های تلفن در فهرست تلفن مرتب نشده باشند، پیدا کردن یک شماره تلفن خاص دشوار خواهد بود. به همین ترتیب، اگر کلمات در فرهنگ لغت به ترتیب حروف الفبا چیده نشده باشند، یافتن کلمات بسیار سخت خواهد بود.بنابراین مرتب سازی در زندگی روزمره مفید است. در علوم کامپیوتر، الگوریتم های مرتب سازی برای مرتب سازی مجموعه ای از داده ها وجود دارد. دو الگوریتم از این دست عبارتند از مرتب سازی درج و مرتب سازی انتخاب. مرتب سازی درج الگوریتم مرتب سازی است که آرایه را با جابجایی عناصر یک به یک مرتب می کند. مرتب سازی انتخاب، الگوریتم مرتب سازی است که کوچکترین عنصر آرایه را پیدا می کند و عنصر را با موقعیت اول مبادله می کند، سپس دومین عنصر کوچک را پیدا کرده و با عنصر در موقعیت دوم مبادله می کند و روند را تا مرتب شدن کل آرایه ادامه می دهد.. تفاوت اصلی بین مرتب‌سازی درج و مرتب‌سازی انتخابی این است که مرتب‌سازی درج دو عنصر را در یک زمان مقایسه می‌کند در حالی که مرتب‌سازی انتخابی حداقل عنصر را از کل آرایه انتخاب می‌کند و آن را مرتب می‌کند.
Insertion Sort چیست؟
مرتب‌سازی درج یک الگوریتم مرتب‌سازی مبتنی بر مقایسه در محل است. در این روش آرایه گام به گام جستجو می شود. موارد مرتب نشده منتقل می شوند و در فهرست فرعی مرتب شده آرایه قرار می گیرند. الگوریتم مرتب سازی درج را می توان با استفاده از مثال زیر توضیح داد.
برای مثال، آرایه اولیه را ۷۷، ۳۳، ۴۴، ۱۱، ۸۸ در نظر بگیرید. در این الگوریتم مرتب‌سازی، اولین مرحله انتخاب عنصر فعلی است.
عنصر فعلی 77 است. عنصر فعلی با همه عناصر در سمت چپ مقایسه می شود. 77 اولین عنصر است و هیچ عنصری در سمت چپ وجود ندارد. شاخص موقعیت فعلی 0. است
سپس شاخص موقعیت فعلی 1 افزایش می یابد. اکنون شاخص 1 است و عنصر فعلی 33 است. هنگام مقایسه آن با عنصر سمت چپ، کوچکتر از 77 است. سپس هر دو مقدار تعویض می شوند. اکنون 33 در شاخص 0 و 77 در شاخص 1 است.
اکنون آرایه 33، 77، 44، 11، 88 است.
دوباره، شاخص افزایش یافته است. شاخص 2 و عنصر فعلی 44 است. با عناصر سمت چپ مقایسه می شود. 44 کمتر از 77 است. بنابراین این دو مقدار با هم عوض می شوند. اکنون آرایه 33، 44، 77، 11، 88 است. لازم است همه عناصر سمت چپ را با هم مقایسه کنید.بنابراین، 44 با 33 مقایسه می شود. 33 کوچکتر از 44 است. بنابراین این عناصر نیازی به مبادله ندارند.
اکنون آرایه 33، 44، 77، 11، 88 است.
دوباره، شاخص افزایش یافته است. شاخص 3 و عنصر فعلی 11 است. با تمام عناصر سمت چپ مقایسه می شود. 11 کمتر از 77 است، بنابراین این دو با هم عوض می شوند. اکنون آرایه 33، 44، 11، 77، 88 است. وقتی 11 و 44 را با هم مقایسه می کنیم، 11 کمتر از 44 است. بنابراین این دو با هم مبادله می شوند. اکنون آرایه ها 33، 11، 44، 77، 88 هستند. دوباره 11 با 33 مقایسه می شود. 11 کمتر از 33 است، بنابراین این دو مقدار با هم عوض می شوند.
اکنون آرایه 11، 33، 44، 77، 88 است.
افزایش شاخص، ایندکس را به 4 تبدیل می کند. مقدار آن 88 است. از 77 بالاتر است. بنابراین، نیازی به تعویض نیست. در نهایت، آرایه مرتب شده 11، 33، 44، 77، 88 است.
شکل 01: نمونه مرتب‌سازی درج
پیاده سازی مرتب سازی درج مانند بالا است. آرایه اولیه 77، 33، 44، 11، 88 بود. پس از مرتب سازی، خروجی 11، 33، 44، 77، 88 را می دهد.
مرتب‌سازی انتخاب چیست؟
Selection مرتب‌سازی یک الگوریتم مرتب‌سازی مبتنی بر مقایسه در محل است. آرایه ها به بخش هایی تقسیم می شوند. قسمت مرتب شده در انتهای سمت چپ قرار دارد. قسمت مرتب نشده در انتهای سمت راست قرار دارد. ابتدا باید کوچکترین مقدار را پیدا کرد. سپس با عنصر سمت چپ تعویض می شود. اکنون آن عنصر در آرایه مرتب شده است. این فرآیند به حرکت مرز آرایه مرتب نشده از یک عنصر به سمت راست ادامه می دهد. الگوریتم مرتب سازی انتخاب را می توان با استفاده از مثال زیر توضیح داد.
برای مثال، آرایه اولیه را ۷۷، ۳۳، ۴۴، ۱۱، ۸۸، ۲۲ در نظر بگیرید. در این الگوریتم مرتب‌سازی، کوچکترین آرایه در آرایه پیدا می‌شود. کوچکترین عنصر 11 است. با عنصر موجود در شاخص 0 آرایه مبادله می شود.
اکنون آرایه 11، 33، 44، 77، 88، 22 است.
کوچکترین عنصر در شاخص 0 است، بنابراین 11 اکنون مرتب شده است. از بقیه عناصر، کوچکترین آن 22 است. با عنصر شاخص 1st تعویض می شود.
اکنون آرایه 11، 22، 44، 77، 88، 33 است.
عناصر 11 و 22 قبلا مرتب شده اند. از بقیه، کوچکترین مقدار 33 است. با عنصر شاخص 2nd تعویض می شود.
اکنون آرایه 11، 22، 33، 77، 88، 44 است.
عناصر 11، 22 و 33 قبلا مرتب شده اند. از بقیه، کوچکترین مقدار 44 است. با عنصر شاخص 3rd جایگزین می شود.
اکنون آرایه 11، 22، 33، 44، 88، 66 است.
عناصر 11، 22، 33، 44 قبلا مرتب شده اند. عناصر باقیمانده 88 و 66 هستند. عنصر 66 با عنصر شاخص 4ام تعویض می شود.
اکنون آرایه 11، 22، 33، 44، 66، 88 است.
این آرایه مرتب شده با استفاده از الگوریتم مرتب سازی انتخاب است.
شکل 02: مثال مرتب‌سازی انتخابی
پیاده سازی مرتب سازی درج مانند بالا است. آرایه اولیه 77، 33، 44، 11، 88 بود. پس از مرتب سازی، خروجی 11، 33، 44، 77، 88 را می دهد.
شباهت بین مرتب‌سازی درج و مرتب‌سازی انتخابی چیست؟
هر دو مرتب‌سازی درج و مرتب‌سازی انتخاب الگوریتم‌های مرتب‌سازی هستند
تفاوت بین مرتب‌سازی درج و مرتب‌سازی انتخابی چیست؟
مرتب‌سازی درج در مقابل مرتب‌سازی انتخابی |
|
| مرتب‌سازی درج الگوریتم مرتب‌سازی است که آرایه را با جابجایی عناصر یک به یک مرتب می‌کند. | مرتب انتخاب، الگوریتم مرتب‌سازی است که کوچکترین عنصر آرایه را پیدا می‌کند و عنصر را با موقعیت اول مبادله می‌کند، سپس دومین عنصر کوچکترین را پیدا می‌کند و آن را با عنصر در موقعیت دوم مبادله می‌کند و روند را تا زمانی ادامه می‌دهد. کل آرایه مرتب شده است. |
| فرآیند | |
| مرتب‌سازی درج برای مرتب‌سازی فهرست فرعی با مقایسه دو عنصر تا مرتب‌سازی کل آرایه است. | مرتب انتخاب حداقل عنصر را انتخاب می کند و آن را با موقعیت اول تعویض می کند، دوباره حداقل را برای بقیه انتخاب می کند و آن را با موقعیت دوم تعویض می کند و این روند را تا پایان ادامه می دهد. |
| پایداری | |
| Insertion Sort یک الگوریتم مرتب‌سازی پایدار است. | مرتب‌سازی انتخابی یک الگوریتم مرتب‌سازی پایدار نیست. |
خلاصه - مرتب‌سازی درج در مقابل مرتب‌سازی انتخابی
گاهی اوقات لازم است داده ها مرتب شوند. در علوم کامپیوتر، الگوریتم هایی برای مرتب سازی داده ها وجود دارد. این مقاله دو الگوریتم مرتب‌سازی را مورد بحث قرار می‌دهد که عبارتند از مرتب‌سازی درج و مرتب‌سازی انتخاب.مرتب سازی درج الگوریتم مرتب سازی است که آرایه را با جابجایی عناصر یک به یک مرتب می کند. مرتب سازی انتخاب، الگوریتم مرتب سازی است که کوچکترین عنصر آرایه را پیدا می کند و عنصر را با موقعیت اول مبادله می کند، سپس دومین عنصر کوچک را پیدا کرده و با عنصر در موقعیت دوم مبادله می کند و روند را تا مرتب شدن کل آرایه ادامه می دهد.. تفاوت بین مرتب‌سازی درج و مرتب‌سازی انتخابی در این است که مرتب‌سازی درج دو عنصر را در یک زمان مقایسه می‌کند در حالی که مرتب‌سازی انتخابی حداقل عنصر را از کل آرایه انتخاب می‌کند و آن را مرتب می‌کند.
دانلود پی دی اف Insertion Sort در مقابل Selection Sort
می توانید نسخه PDF این مقاله را دانلود کنید و طبق یادداشت استنادی از آن برای اهداف آفلاین استفاده کنید. لطفاً نسخه PDF را از اینجا دانلود کنید: تفاوت بین مرتب‌سازی درج و مرتب‌سازی انتخابی
