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

معرفی

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

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

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

ایده پشت انتخاب مرتب سازی کنید

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

یک پیاده سازی سطح بالا از این نوع شبیه به این است:

def selection_sort(L):
    for i in range(len(L) - 1):
        min_index = argmin(L(i:))
        L(i), L(min_index) = L(min_index), L(i)

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

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

بیایید ببینیم که چگونه در عمل با لیستی که حاوی عناصر زیر است کار می کند: (3, 5, 1, 2, 4).

ما با لیست مرتب نشده شروع می کنیم:

بخش مرتب نشده همه عناصر را دارد. ما هر مورد را بررسی می کنیم و آن را تعیین می کنیم 1 کوچکترین عنصر است. بنابراین، ما swap 1 با 3:

از عناصر دسته بندی نشده باقیمانده، (5, 3, 2, 4)، 2 کمترین عدد است. ما الان swap 2 با 5:

این process تا مرتب شدن لیست ادامه می یابد:

• 1 2 3 5 4
• 1 2 3 4 5
• 1 2 3 4 5

بیایید ببینیم چگونه می توانیم این را در پایتون پیاده سازی کنیم!

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

ترفند اجرای این الگوریتم، پیگیری حداقل مقدار و تعویض دو عنصر از لیست است:

def selection_sort(L):
    
    for i in range(len(L)-1):
        
        
        min_index = i
        
        for j in range(i+1, len(L)-1):
            
            if L(j) < L(min_index):
                min_index = j
        
        L(i), L(min_index) = L(min_index), L(i)

حالا بیایید برای آزمایش الگوریتم مقداری کد به فایل اضافه کنیم:

L = (3, 1, 41, 59, 26, 53, 59)
print(L)
selection_sort(L)


print(L)

این به ما می دهد:

(3, 1, 41, 59, 26, 53, 59)
(1, 3, 26, 41, 53, 59, 59)

لیست به درستی مرتب شده بود! ما می دانیم که چگونه کار می کند و می توانیم مرتب سازی انتخاب را در پایتون پیاده سازی کنیم. بیایید وارد یک نظریه شویم و عملکرد آن را با توجه به زمان بررسی کنیم.

محاسبه پیچیدگی زمانی

بنابراین چقدر طول می کشد تا مرتب سازی انتخاب لیست ما مرتب شود؟ ما می خواهیم رویکردی را در نظر بگیریم و با توجه به اندازه آرایه ای، الگوریتم مرتب سازی انتخاب را دقیقاً محاسبه کنیم که چقدر زمان می برد. n. خط اول کد این است:

def selection_sort(L):

این خط نباید زیاد طول بکشد زیرا فقط پشته تابع را تنظیم می کند. ما می گوییم که این یک است ثابت – اندازه ورودی ما مدت زمان اجرای این کد را تغییر نمی دهد. بیایید بگوییم طول می کشد c1 عملیات برای اجرای این خط کد. بعد، داریم:

for i in range(len(L)-1):

این یکی کمی پیچیده تر است. اول از همه، ما دو فراخوانی تابع داریم، len() و range()، که قبل از انجام می شود for حلقه شروع می شود. هزینه از len() همچنین مستقل از اندازه در CPython است که پیاده سازی پیش فرض پایتون است روی ویندوز، لینوکس و مک. این برای مقداردهی اولیه نیز صادق است range(). بیایید این دو را با هم صدا کنیم c2.

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

هزینه ثابتی برای ارزیابی وجود دارد in اپراتور، بیایید بگوییم c3. که قسمت بیرونی را می پوشاند for حلقه

تخصیص متغیر نیز در زمان ثابت انجام می شود. ما به این یکی می گوییم c4:

min_index = i

اکنون با درون مواجه می شویم for حلقه دارای دو فراخوانی تابع ثابت است. فرض کنیم می گیرند c5 عملیات

تا اینجای کار داریم c1 + c2 + (n - 1) * (c3 + c4 + c5) عملیات، و سپس حلقه داخلی ما شروع می شود و همه چیز را در … ضرب می کند؟ خوب، مشکل است، اما اگر از نزدیک نگاه کنید، طول می کشد n - 2 بار در اولین حلقه، n - 3 در مورد دوم، و 1 در آخرین بار.

ما باید همه چیز را در مجموع همه اعداد بین 1 و ضرب کنیم n - 2. ریاضیدانان به ما گفته اند که این مجموع خواهد بود (n - 2) * (n - 1) / 2.

محتویات حلقه داخلی نیز در زمان ثابت تکمیل می شود. بیایید زمان لازم برای انجام این کار را به پایتون اختصاص دهیم in، if، بیانیه انتساب و متغیر swap یک زمان ثابت دلخواه از c6.

for j in range(i+1, len(L)-1):
    if L(j) < L(min_index):
        min_index = j
L(i), L(min_index) = L(min_index), L(i)

همه با هم به دست می آوریم c1 + c2 + (n - 1) * (c3 + c4 + c5) + (n - 2) * (n - 3) * c6 / 2.

ما می توانیم این را ساده کنیم a * n * n + b * n + c، جایی که a، b، و c نشان دهنده مقادیر ثابت های ارزیابی شده است.

این به عنوان شناخته شده است بر²). معنی آن چیست؟ به طور خلاصه، عملکرد الگوریتم ما مبتنی است روی اندازه مربع لیست ورودی ما. بنابراین، اگر اندازه لیست خود را دو برابر کنیم، مدت زمان مرتب سازی آن در 4 ضرب می شود! اگر اندازه ورودی خود را بر 3 تقسیم کنیم، زمان 9 کوچک می شود!

نتیجه

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

یادگیری الگوریتم های مرتب سازی به شما کمک می کند تا درک بهتری از الگوریتم ها به طور کلی داشته باشید. بنابراین، اگر قبلاً این کار را نکرده اید، می توانید مرور کلی الگوریتم های مرتب سازی ما را بررسی کنید!