نحوه کدنویسی الگوریتم مرتب سازی انتخاب در جاوا اسکریپت و پایتون

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

این مقاله در ابتدا در jarednielsen.com منتشر شده است

نحوه کدگذاری الگوریتم مرتب سازی انتخاب

برنامه نویسی حل مسئله است. برای حل هر مشکل برنامه نویسی باید چهار مرحله را طی کنیم:

1. مشکل را درک کنید

2. ایجاد یک طرح

3. طرح را اجرا کنید

4. طرح را ارزیابی کنید

مشکل را درک کنید

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

GIVEN an unsorted array of integers
WHEN we find the lowest unsorted value
THEN we move that value to its proper ordinal position and repeat until all values are in sequence

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

بیایید برنامه ریزی کنیم!

ایجاد یک طرح

بیایید اکتشافات تفکر محاسباتی خود را مجدداً مرور کنیم زیرا آنها در ساختن یک برنامه کمک می کنند و راهنمایی می کنند. آن ها هستند:

• تجزیه

• الگو شناسی

• انتزاع – مفهوم – برداشت

• طراحی الگوریتم

ما به چیزی برای مرتب سازی نیاز داریم، بنابراین بیایید از این آرایه “غیرمترتب” استفاده کنیم:

[10, 1, 9, 2, 8, 3, 7, 4, 6, 5]

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

[10, 1]

می بینیم که ما به سادگی باید موقعیت های این دو مقدار را عوض کنیم. بیایید یک راه حل برای این مشکل بسیار کوچک رمزگذاری کنیم:

INPUT array
SET first EQUAL TO THE VALUE STORED IN array[0]
SET next EQUAL TO THE VALUE STORED IN array[1]
IF next IS LESS THAN first 
    SWAP first AND next 

تا اینجای کار خیلی خوبه! بیایید آرایه خود را گسترش دهیم و مقدار دیگری اضافه کنیم:

[10, 1, 9]

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

بیایید شبه کد خود را به روز کنیم:

INPUT array
FOR EACH index IN array:
    SET first EQUAL TO THE VALUE STORED IN array[0]
    SET next EQUAL TO THE VALUE STORED IN array[1]
    IF next IS LESS THAN first
        SWAP first AND next

بیایید از این مرحله عبور کنیم …

در اولین تکرار، اولین عنصر را انتخاب می کنیم، 10و آن را با عنصر بعدی مقایسه کنید، 1، که کمتر از 10، بنابراین ما موقعیت آنها را عوض می کنیم. آرایه ما اکنون به شکل زیر است:

[1, 10, 9]

ولی! در تکرار بعدی چه اتفاقی می افتد؟ ما دوباره اولین عنصر را انتخاب می کنیم و آن را با عنصر بعدی مقایسه می کنیم که اکنون است 9. 9 بزرگتر است از 1، بنابراین آن را در جایی که هست رها می کنیم.

راه حل چیست؟

انتزاع – مفهوم – برداشت!

ما به وسیله ای برای ردیابی و به روز رسانی شاخص “حداقل مقدار شناخته شده” نیاز داریم.

در این سناریو، 1 اولین “مقدار حداقل شناخته شده” ما است، اما ما می توانیم آن را ببینیم 9 کمتر است از 10، پس پس از حرکت 1، جاری “مقدار حداقل شناخته شده” به شاخص 0، ما نیاز به پیدا کردن بعد “حداقل مقدار شناخته شده” و مقایسه آن با next ارزش گذاری کنید و بر این اساس مبادله کنید.

بیایید به “مقدار حداقل شناخته شده” به عنوان اشاره کنیم min.

INPUT array
FOR EACH index IN array:
    SET min EQUAL TO index 
    SET next EQUAL TO index + 1
    IF THE VALUE STORED IN array[next] IS LESS THAN THE VALUE STORED IN array[min]:
        SET min EQUAL TO next
        SWAP THE VALUE STORED IN array[index] WITH THE VALUE STORED IN array[min]

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

[10, 1, 9]

در اولین تکرار، ما انتخاب کنید 10 زیرا اولین عنصر و مقدار ذخیره شده در آن استarray[min]. اگر مقدار ذخیره شده در next، در این مورد 1، کمتر از مقدار ذخیره شده در است min، که هست، دوباره اختصاص می دهیم min ارزش next. بنابراین min اکنون برابر است با 1. اکنون باید مقدار ذخیره شده در حال حاضر را عوض کنیم array[index]، 10، با مقدار ذخیره شده در array[min]، 1. پس از اولین تکرار، آرایه ما به شکل زیر است:

[1, 10, 9]

در تکرار بعدی، index برابر است با 1، بنابراین مقدار آن را مجدداً اختصاص می دهیم min با 1. سپس مقدار آن را تغییر می دهیم next با index + 1، یا 2. ما مقدار ذخیره شده را با هم مقایسه می کنیم array[next]، که است 9، با مقدار ذخیره شده در array[min]، که است 10. ارزیابی مشروط ما به عنوان true، بنابراین مقدار آن را مجدداً اختصاص می دهیم min با ارزش next و سپس مقدار ذخیره شده را عوض کنید array[index] با مقدار ذخیره شده در array[min]. آرایه ما اکنون به شکل زیر است:

[1, 9, 10]

تا اینجای کار خیلی خوبه. بیایید مقدار دیگری به آرایه خود اضافه کنیم:

[10, 1, 9, 2]

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

[1, 9, 10, 2]

اینجا قرار است چه اتفاقی بیفتد؟ ما فقط می خواهیم مکان های آن را عوض کنیم 2 و 10. آرایه ما به شکل زیر خواهد بود:

[1, 9, 2, 10]

چه اشکالی در طراحی ما وجود دارد؟

ما فقط تکرار کننده را مقایسه می کنیم، index، به بعد ارزش.

راه حل چیست؟

تکرار تو در تو. ما باید هر شاخص را با تمام مقادیر زیر در آرایه مقایسه کنیم. بیایید شبه کد خود را به روز کنیم:

INPUT array
FOR EACH index IN array
    SET min EQUAL TO index
    SET next TO index + 1
    FOR EACH next IN array
        IF THE VALUE STORED IN array[next] IS LESS THAN THE VALUE STORED IN array[min]
        SET min EQUAL TO next
    SWAP THE VALUES STORED IN array[index] WITH THE VALUE STORED IN array[min]

بیایید با استفاده از این آرایه از شبه کد خود عبور کنیم:

[10, 1, 9, 2]

در اولین تکرار حلقه بیرونی خود، تنظیم کردیم min به index، یا 0. سپس حلقه تودرتوی خود را وارد می کنیم تا روی باقیمانده یا تکرار شود بعد عناصر. عنصر بعدی برابر است با index + 1. که در این تکرار است 1. مشروط ما بررسی می کند که آیا مقدار ذخیره شده در آرایه ما در شاخص است یا خیر 1 کمتر از مقدار ذخیره شده در آرایه ما در شاخص است 0. اگر این به عنوان ارزیابی شود true، مقدار را تعیین می کنیم min مساوی با next. در این تکرار، array[next] برابر است با 1 و array[index] برابر است با 10، بنابراین ما تنظیم کردیم min برابر با مقدار ذخیره شده در next، که است 1. ما هنوز در حلقه تودرتو خود هستیم، بنابراین به مقایسه مقادیر باقی مانده با آن ادامه می دهیم min و کشف کنید که 1 کمترین مقدار در آرایه ما است. از حلقه تو در تو خارج می شویم و مبادله ارزش در 0 شاخص، که است 10، با دره در min شاخص، که است 1. آرایه ما اکنون به شکل زیر است:

[1, 10, 9, 2]

اکنون دوباره در سطح حلقه بیرونی خود تکرار می کنیم و مقدار را در قسمت انتخاب می کنیم 1 شاخص، که اکنون است 10. به آن اختصاص می دهیم min و حلقه تو در تو را وارد کنید. مقدار بعدی است 9، که کمتر از 10، بنابراین ما شاخص را اختصاص می دهیم next، که است 2 به min. ما به تکرار روی مقادیر باقی مانده در آرایه خود ادامه می دهیم و متوجه می شویم که مقدار بعدی، 2، کمتر است از 9، بنابراین ما شاخص را اختصاص می دهیم next، که است 3، به min. از حلقه تو در تو خارج می شویم و مقدار ذخیره شده در آن را عوض می کنیم array[index] با مقدار ذخیره شده در array[next]. آرایه ما اکنون به شکل زیر است:

[1, 2, 9, 10]

به نظر طرح محکمی است!

طرح را اجرا کنید

اکنون فقط موضوع ترجمه شبه کد ما به نحو زبان برنامه نویسی ما است. بیایید با جاوا اسکریپت شروع کنیم…

نحوه کدنویسی الگوریتم مرتب سازی انتخاب در جاوا اسکریپت

بیایید شبه کد خود را به جاوا اسکریپت ترجمه کنیم:

const selectionSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        let min = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }

        let tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
    return arr;
};

نحوه کدنویسی الگوریتم مرتب سازی انتخاب در پایتون

حالا بیایید آن را در پایتون ببینیم …

unsorted = [10, 1, 9, 2, 8, 3, 7, 4, 6, 5]

def selection_sort(arr):
    for i in range(len(arr)):
        min = i

        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min]:
                min = j

        tmp = arr[i]
        arr[i] = arr[min]
        arr[min] = tmp

    return arr

طرح را ارزیابی کنید

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

اینجا در جاوا اسکریپت است…

const selectionSort = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {
        let min = i;

        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }

        let tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
    return arr;
};

توجه داشته باشید که خط دوم را با موارد زیر به روز می کنیم:

    for (let i = 0; i < arr.length - 1; i++) {

اینجا در پایتون است…

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min = i

        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min]:
                min = j

        tmp = arr[i]
        arr[i] = arr[min]
        arr[min] = tmp

    return arr

همانطور که در بالا ذکر شد، توجه داشته باشید که ما به سادگی خط دوم را با موارد زیر به روز می کنیم:

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

توجه داشته باشید که ما نداریم - 1 در شرایط حلقه تو در تو. اگر این کار را می کردیم، هرگز نمی کردیم انتخاب کنید ارزش نهایی

A برای الگوریتم ها است

به خود یک A بدهید. کپی خود را از A برای الگوریتم ها بگیرید