مرتب سازی درج در پایتون

معرفی

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

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

بیایید این اصطلاحات را توضیح دهیم:

• درجا: به یک فضای اضافی کوچک و ثابت نیاز دارد (بدون توجه به اندازه ورودی مجموعه)، اما مکان های حافظه اصلی عناصر مجموعه را بازنویسی می کند.
• پایدار: الگوریتم ترتیب نسبی اشیاء مساوی را از آرایه اولیه حفظ می کند. به عبارت دیگر، بگویید پایگاه داده کارکنان شرکت شما برمی گردد “دیو واتسون” و “دیو براون” به عنوان دو کارمند، به ترتیب خاص. اگر بخواهید آنها را با نام کوچک (مشترک) آنها مرتب کنید، الف پایدار الگوریتم تضمین می کند که این ترتیب بدون تغییر باقی می ماند.

مرتب سازی درج اغلب در عمل استفاده می شود، زیرا برای مجموعه داده های کوچک (~ 10 مورد) کارآمد است. در مورد آن بیشتر صحبت خواهیم کرد بعد.

ایده پشت درج مرتب سازی

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

فروشنده 14 کارت به شما می دهد، شما آنها را یکی یکی برمی دارید و به ترتیب درست در دستان خود قرار می دهید. در طول این کل process، دست شما “زیر مجموعه” مرتب شده از کارت های شما را نگه می دارد، در حالی که کارت های رو به پایین باقی مانده روی جدول مرتب نشده است – که از آن کارت ها را یکی یکی می گیرید و در دست می گذارید.

به این ترتیب، مرتب سازی Insertion یک آرایه را به یک زیرآرایه “مرتب شده” و یک زیرآرایه “مرتب نشده” تقسیم می کند. در ابتدا، زیرآرایه مرتب شده فقط شامل اولین عنصر آرایه اصلی ما است.

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

زیرآرایه مرتب شده را با اعداد پررنگ علامت گذاری می کنیم و از آرایه زیر برای نشان دادن الگوریتم استفاده می کنیم:

گام اول “افزودن” خواهد بود 8 به زیرآرایه مرتب شده ما

اکنون نگاهی به اولین عنصر مرتب نشده می اندازیم – 5. ما آن مقدار را برای مثال در یک متغیر جداگانه نگه می داریم current، برای حفظ ایمنی 5 کمتر است از 8. حرکت می کنیم 8 یک مکان به سمت راست، به طور موثر بازنویسی 5 که قبلاً در آنجا ذخیره شده بود (از این رو متغیر جداگانه برای نگهداری):

• 8، 8، 4، 10، 9 (current = 5)

5 از همه عناصر موجود در زیرآرایه مرتب شده ما کوچکتر است، بنابراین آن را در موقعیت اول قرار می دهیم:

بعد، به عدد نگاه می کنیم 4. ما آن مقدار را در current. 4 کمتر است از 8 بنابراین حرکت می کنیم 8 سمت راست، و همین کار را با 5.

• 5، 5، 810, 9 (current = 4)

مجدداً با عنصری کمتر از کل زیرآرایه مرتب شده خود مواجه شده ایم، بنابراین آن را در موقعیت اول قرار می دهیم:

10 بزرگتر از سمت راست ترین عنصر ما در زیرآرایه مرتب شده است و بنابراین از هر یک از عناصر سمت چپ بزرگتر است. 8. بنابراین ما به سادگی حرکت می کنیم روی به عنصر بعدی:

9 کمتر است از 10، بنابراین حرکت می کنیم 10 به سمت راست:

• 4، 5، 8، 10، 10 (current = 9)

با این حال، 9 بزرگتر است از 8، بنابراین ما به سادگی درج می کنیم 9 درست بعد از 8.

روش پیاده سازی مرتب سازی حباب در پایتون

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

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

مرتب سازی آرایه ها

def insertion_sort(array):

    
    for index in range(1, len(array)):
        currentValue = array(index)
        currentPosition = index

        
        
        
        while currentPosition > 0 and array(currentPosition - 1) > currentValue:
            array(currentPosition) = array(currentPosition -1)
            currentPosition = currentPosition - 1


        
        
        
        
        array(currentPosition) = currentValue

بیایید یک آرایه ساده را پر کنیم و مرتب کنیم:

array = (4, 22, 41, 40, 27, 30, 36, 16, 42, 37, 14, 39, 3, 6, 34, 9, 21, 2, 29, 47)
insertion_sort(array)
print("sorted array: " + str(array))

خروجی:

sorted array: (2, 3, 4, 6, 9, 14, 16, 21, 22, 27, 29, 30, 34, 36, 37, 39, 40, 41, 42, 47)

این بدان معنی است که اگر ما واقعاً به عنصر 0 رسیدیم، ابتدا بررسی می کنیم که آیا array(-1) > currentValue. در پایتون، این “خوب” است، اگرچه از نظر فنی نادرست است، زیرا باعث نمی شود حلقه زودتر از موعد پایان یابد یا در زمانی که نباید ادامه یابد.

این به این دلیل است که اگر به عنصر صفر رسیده بودیم، شرط دوم از currentPosition > 0 بدون توجه به شرط اول شکست می خورد و باعث می شود حلقه شکسته شود. در پایتون array(-1) > currentValue برابر است با array(len(array) - 2) > currentValue و مترجم شکایت نمی کند، اما این مقایسه ای نیست که ما واقعاً بخواهیم اتفاق بیفتد.

این ترتیب معکوس شرایط ایده بدی است. در بسیاری از موارد، می‌تواند منجر به نتایج غیرمنتظره‌ای شود که اشکال‌زدایی آن‌ها دشوار است، زیرا خطای نحوی یا معنایی وجود ندارد. بیشتر زبان های برنامه نویسی به دلیل تلاش برای دسترسی به آن “شکایت” می کنند -1عنصر st، اما پایتون شکایت نمی‌کند و از دست دادن چنین اشتباهی آسان است.

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

مرتب سازی اشیاء سفارشی

قبلاً اشاره کردیم که می‌توانیم «بزرگتر از» و «کمتر از» را هر طور که بخواهیم تعریف کنیم – که این تعریف نیازی به تکیه صرفا ندارد. روی اعداد صحیح راه های مختلفی وجود دارد که می توانیم الگوریتم خود را برای کار با اشیاء سفارشی تغییر دهیم.

ما می‌توانیم عملگرهای مقایسه واقعی را برای کلاس سفارشی خود دوباره تعریف کنیم و همان کد الگوریتم بالا را حفظ کنیم. با این حال، این بدان معناست که اگر بخواهیم اشیاء کلاس خود را به روش دیگری مرتب کنیم، باید آن عملگرها را بیش از حد بارگذاری کنیم.

مسلماً بهترین راه برای استفاده از Insertion Sort برای کلاس‌های سفارشی، ارسال آرگومان دیگری به کلاس است insertion_sort() روش – به طور خاص یک روش مقایسه. راحت ترین راه برای انجام این کار استفاده از یک تابع لامبدا سفارشی هنگام فراخوانی روش مرتب سازی است.

در این پیاده سازی، نقاطی را مرتب می کنیم که در آن نقطه “کوچکتر” نقطه ای است که دارای نقطه کمتر است x هماهنگ کردن.

ابتدا ما خودمان را تعریف می کنیم Point کلاس:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return str.format("({},{})", self.x, self.y)

سپس یک تغییر جزئی در خود ایجاد می کنیم insertion_sort روش برای تطبیق مرتب سازی سفارشی:

def insertion_sort(array, compare_function):
    for index in range(1, len(array)):
        currentValue = array(index)
        currentPosition = index

        while currentPosition > 0 and compare_function(array(currentPosition - 1), currentValue):
            array(currentPosition) = array(currentPosition - 1)
            currentPosition = currentPosition - 1

        array(currentPosition) = currentValue

در نهایت برنامه را تست می کنیم:

A = Point(1,2)
B = Point(4,4)
C = Point(3,1)
D = Point(10,0)

array = (A,B,C,D)


insertion_sort(array, lambda a, b: a.x > b.x)

for point in array:
    print(point)

خروجی را می گیریم:

(1,2)
(3,1)
(4,4)
(10,0)

این الگوریتم اکنون برای هر نوع آرایه ای کار می کند، تا زمانی که یک تابع مقایسه مناسب ارائه کنیم.

مرتب سازی درج در عمل

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

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

به عنوان مثال، جاوا از a استفاده کرد مرتب سازی سریع دو محوری به عنوان الگوریتم مرتب‌سازی اولیه، اما هر زمان که آرایه (یا زیرآرایه ایجاد شده توسط مرتب‌سازی سریع) کمتر از 7 عنصر داشت، از مرتب‌سازی درج استفاده می‌کرد.

ترکیب کارآمد دیگر صرفاً نادیده گرفتن همه زیرآرایه های کوچک ایجاد شده توسط Quick Sort و سپس عبور آرایه نهایی تقریبا مرتب شده از طریق Insertion Sort است.

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

اساساً تعداد زیادی تماس مرتب‌سازی درج را به آرایه‌های کوچک‌تر و سپس تقریباً مرتب‌سازی می‌کند و از تمام مزایایی که می‌تواند بهره می‌برد.

نتیجه

Insertion Sort یک الگوریتم بسیار ساده و عموماً ناکارآمد است که با این وجود دارای چندین مزیت خاص است که حتی پس از توسعه الگوریتم‌های بسیار کارآمد دیگر، آن را مرتبط می‌سازد.

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