রুবিতে সিলেকশন সর্ট মাস্টার করুন: স্টেপ-বাই-স্টেপ ইমপ্লিমেন্টেশন

নোট: এটি রুবি দিয়ে বিভিন্ন সর্টিং অ্যালগরিদম দেখার সিরিজের পার্ট ২। পার্ট ১-এ বাবল সর্ট আলোচনা করা হয়েছিল।

এই পোস্টে, আমি রুবি দিয়ে সিলেকশন সর্ট অ্যালগরিদম ইমপ্লিমেন্ট করার প্রক্রিয়া ওয়াক থ্রু করব। সিলেকশন সর্ট একটি ইন-প্লেস কমপैरিজন সর্টিং অ্যালগরিদম। এর মানে সর্টেড আইটেমগুলো অরিজিনালদের সাথে একই স্টোরেজ দখল করে। আরও যাওয়ার আগে, নোট করা গুরুত্বপূর্ণ যে সিলেকশন সর্টিং অ্যালগরিদম প্র্যাকটিসে কমনলি ব্যবহার হয় না যদি ডেটাসেট ছোট না হয় (অর্থাৎ, ১০-২০ এলিমেন্ট)। কিন্তু, এটি একটি চমৎকার স্ট্রার্টার অ্যালগরিদম শিখতে এবং বুঝতে, সাদৃশ্য ট্রাইসাইকেল চালা শিখে বাইসাইকেল চলে, যদি আপনি চান। ইমপ্লিমেন্টেশনটি একটি কোডিং চ্যালেঞ্জে জব ইন্টারভিউতে দেখতে পাওয়া যেতে পারে, অথবা আপনাকে বলতে বলতে পারা যেতে পারে কেন সিলেকশন সর্টের মতো একটি অ্যালগরিদম বড় ডেটাসেটে খুব প্র্যাকটিক্যাল নয়। সিলেকশন সর্ট সাধারণত বাবল সর্টের চেয়ে ভালো পারফর্ম করে, যা এই সিরিজের প্রথম অ্যালগরিদম ছিল।

উচ্চ স্তরে, সিলেকশন সর্ট অ্যারেকে দুটি পার্টে ভাগ করে: একটা হälfte সর্টেড এবং অন্যটা নন। শুরুতে, সর্টেড সেকশন খালি, এবং আনসর্টেড পোর্শন সব এলিমেন্ট ধারণ করে। সিলেকশন সর্ট দুটি লুপ ব্যবহার করে; আউটার লুপ n বার ইটারেট করে, যেখানে n হলো অ্যারেতে এলিমেন্টের সংখ্যা। আমরা অবিলম্বে "মিন ইনডেক্স" সেট করি প্রথম এলিমেন্টে, এবং তারপর আরেকটি লুপ ব্যবহার করে এলিমেন্টগুলো কমপেয়ার করি, মিন ইনডেক্স সওয়্যাপ করি যদি আডজেসেন্ট এলিমেন্ট কারেন্ট মিনিমাম থেকে কম হয়।

এটি যদি ফলো করা কঠিন লাগে, চিন্তা করবেন না! আমরা একটু পরে একটি একচুচু উদাহরণের মাধ্যমে যাব। :)

স্টেপ বাই স্টেপ

চলুন শুরু করি একটি অ্যারে দিয়ে যেটিতে নিচের এলিমেন্টগুলো রয়েছে: [10, 30, 27, 7, 33, 15, 40, 50]

ইটারেশন এক: সবচেয়ে ছোট নম্বর খুঁজুন

এই কেসে, সবচেয়ে ছোট নম্বর হলো 7, তাই আমরা এটাকে শুরুতে রাখি এবং 10-কে সেখানে সরিয়ে দেই যেখানে 7 ছিল। আমাদের অ্যারে এখন এভাবে দেখে: [7, 30, 27, 10, 33, 15, 40, 50]

ইটারেশন দুই: পরবর্তী সবচেয়ে ছোট নম্বর খুঁজুন

ইনডেক্স পজিশন ১-এ থাকা এলিমেন্ট থেকে শুরু করে (মনে রাখবেন, অ্যারে ০-ইন্ডেক্সড), পরবর্তী সবচেয়ে ছোট এলিমেন্ট খুঁজুন

এই কেসে, সেটি হলো 10. 10-কে অ্যারেতে দ্বিতীয় পজিশনে সরান এবং 30-কে সেখানে সরান যেখানে 10 ছিল। ফলাফল অ্যারেটি হলো: [7, 10, 27, 30, 33, 15, 40, 50]

এখান থেকে, আমরা এই সেম প্রসেস চালিয়ে যাব যতক্ষণ না আমাদের অ্যারে ফুলি সর্টেড হয়। নিচে, আপনি পরবর্তী ইটারেশনগুলোতে ফলাফল অ্যারেগুলো দেখতে পারেন।

ইটারেশন তিন:

[7, 10, 15, 30, 33, 27, 40, 50]

ইটারেশন চার:

[7, 10, 15, 27, 33, 30, 40, 50]

ইটারেশন পাঁচ:

[7, 10, 15, 27, 30, 33, 40, 50]

বিঙ্গো! আমরা সর্টেড হয়ে গেলাম!

আপনি যদি ভিজ্যুয়াল লার্নার হন, তবে এখানে একটি উদাহরণ দেওয়া হলো কীভাবে একটি সিলেকশন সর্ট কাজ করবে একটি [] অ্যারে দিয়ে

ফটো ক্রেডিট

একটি রুবি ইমপ্লিমেন্টেশন

এখানে রুবিতে লেখা একটি সিলেকশন সর্ট ফাংশন দেওয়া হলো:

def selection_sort(array) n = array.length - 1 n.times do |i| min_index = i for j in (i + 1)..n min_index = j if array[j] < array[min_index] end array[i], array[min_index] = array[min_index], array[i] if min_index != i end puts array end 

চলুন দেখি এটি কীভাবে কাজ করে।

প্রথমে, আমরা n সেট করি এলিমেন্টের সংখ্যায়। মনে রাখবেন, আমাদের এক বিয়োগ করতে হয় কারণ অ্যারে ০-ইন্ডেক্সড।

পরবর্তী, আমরা আউটার লুপ তৈরি করি, যা n বার চলবে।

min_index = i 

এখানে, আমরা মিনিমাম ইনডেক্স সেট করি প্রথম পজিশনের এলিমেন্টে।

for j in (i + 1)..n 

পরবর্তী, আমরা ইনার লুপ তৈরি করি। এই লাইনটি বলছে "দ্বিতীয় পজিশনের এলিমেন্ট থেকে nth এলিমেন্ট পর্যন্ত, নিচের কী করবে"। আপনি যদি .. অপারেটরের সাথে পরিচিত ন হন, তবে এটি একটি রেঞ্জ তৈরি করে স্টার্ট পয়েন্ট থেকে এন্ড পয়েন্ট পর্যন্ত, ইনক্লুসিভলি। উদাহরণস্বরূপ, 1..10 ১ থেকে ১০ পর্যন্ত একটি রেঞ্জ তৈরি করে, ইনক্লুসিভ।

min_index = j if array[j] < array[min_index] 

এই লুপের ভেতরে, আমরা min_index-কে একটি নতুন এলিমেন্টে সেট করি যদি সেটি কারেন্ট min_index-এর চেয়ে কম হয়।

array[i], array[min_index] = array[min_index], array[i] if min_index != i 

আমাদের ইনার লুপের বাইরে, আমরা চেক করি কারেন্ট min_index i-এর সমান কিনা। যদি এটি সত্য হয়, তবে আমাদের এলিমেন্টগুলো শাফল করতে হবে। আমরা array[i]-কে array[min_index] এবং array[min_index]-কে array[i] সেট করি। এখানে, আমরা সেম "সওয়্যাপ" পারফর্ম করছি যেন আমরা আমাদের উদাহরণে করেছিলাম।

শেষে, একবার ফিনিশ হলে, আমরা আমাদের অ্যারে আউটপুট করি, যা এখন সর্টেড!

সবকিছু একসাথে করা

এখানে আমার ফুল প্রোগ্রাম:

def selection_sort(array) n = array.length - 1 n.times do |i| min_index = i for j in (i + 1)..n min_index = j if array[j] < array[min_index] end array[i], array[min_index] = array[min_index], array[i] if min_index != i end puts array end array = [10, 30, 27, 7, 33, 15, 40, 50] selection_sort(array) 

ruby ruby-selection-sort.rb টার্মিনাল থেকে রান করলে নিচের আউটপুট আসবে:

7 10 15 27 30 33 40 50 

কুল!

সিলেকশন সর্ট অদক্ষ কেন বুঝা

এক অ্যালগরিদমের এফিশিয়েন্সি মাপার একটি পথ হলো "Big-O নোটেশন" দেখা; এটি ওৰ্স্ট-কেস পারফর্মেন্স রিপ্রেজেন্ট করে যাতে অ্যালগরিদমগুলো কমপেয়ার করা যায়। উদাহরণস্বরূপ, O(1) Big-O মানে ওৰ্স্ট-কেস রান টাইম কনস্ট্যান্ট থাকে এলিমেন্টের সংখ্যা "n" বড়লেও, আর O(n) Big-O মানে ওৰ্স্ট-কেস রান টাইম লিনিয়ারলি বড়ে n বড়লে। এর মানে আপনার যদি ১০০ এলিমেন্টের অ্যারে থাকে এবং আপনাকে O(n) এবং O(1) সর্টিং অ্যালগরিদমের মধ্যে বেছে নিতে হয়, তবে আপনি O(1) বেছে নেবেন কারণ O(1) অবশ্যই O(100)-কে হারাবে।

বাবল সর্টের মতো, সিলেকশন সর্টের ওৰ্স্ট-কেস এবং এভারেজ কমপ্লেক্সিটি O(n²) নেস্টেড লুপের কারণে। এর মানে এলিমেন্ট সংখ্যা বড়লেই এর এফিশিয়েন্সি নাটকিয়ভাবে কমে যায়।

র‍্যাপ আপ

সবকিছু কনসিডার করলে, সিলেকশন সর্ট এখনও একটি ইন্ড্রেস্টিং অ্যালগরিদম যা কোডিং চ্যালেঞ্জে পপ-আপ হতে পারে। অথবা, আপনাকে একটি সিলেকশন সর্ট ফাংশন দিয়ে বলতে পারা যেতে পারে Big-O নোটেশন কী এবং কেন। আশা করি এই আর্টিকেলের উদাহরণগুলো আপনাকে উভয় সিনেরিওর জন্য রেডি করবে।