রুবির সাথে সিলেকশন সর্ট বোঝা

দ্রষ্টব্য:এটি রুবির সাথে বিভিন্ন সাজানোর অ্যালগরিদম দেখার একটি সিরিজের অংশ 2। পার্ট 1 অন্বেষণ করা বুদ্বুদ সাজানো৷৷

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

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

যদি এটি অনুসরণ করা কঠিন হয়, চিন্তা করবেন না! আমরা পরবর্তী একটি বাস্তব উদাহরণ মাধ্যমে হাঁটতে যাচ্ছি. :)

ধাপে ধাপে

আসুন নিম্নলিখিত উপাদানগুলির সাথে একটি অ্যারে দিয়ে শুরু করি:[10, 30, 27, 7, 33, 15, 40, 50]

পুনরাবৃত্তি এক:ক্ষুদ্রতম সংখ্যা খুঁজুন

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

পুনরাবৃত্তি দুই:পরবর্তী ক্ষুদ্রতম সংখ্যা খুঁজুন

সূচী অবস্থান 1 এ উপাদান থেকে শুরু করে (মনে রাখবেন, অ্যারেগুলি 0-সূচীযুক্ত), পরবর্তী ক্ষুদ্রতম উপাদানটি খুঁজুন

এই ক্ষেত্রে, এটি হল 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 সেট করি উপাদান সংখ্যার সমান। মনে রাখবেন, আমাদের একটি বিয়োগ করতে হবে কারণ অ্যারেগুলি 0-সূচীযুক্ত।

এর পরে, আমরা আমাদের বাইরের লুপ তৈরি করি, যা n চালাতে চলেছে বার।

min_index = i

এখানে, আমরা ন্যূনতম সূচকটি প্রথম অবস্থানে থাকা উপাদানটিতে সেট করছি।

for j in (i + 1)..n

এর পরে, আমরা আমাদের ভিতরের লুপ তৈরি করি। এই লাইনটি বলছে "নম উপাদান থেকে দ্বিতীয় অবস্থানের উপাদানটির জন্য, যা অনুসরণ করুন"। আপনি যদি .. এর সাথে পরিচিত না হন অপারেটর, এটি সূচনা বিন্দু থেকে শেষ বিন্দু পর্যন্ত একটি পরিসর তৈরি করে, অন্তর্ভুক্তভাবে। উদাহরণস্বরূপ, 1..10 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

দুর্দান্ত!

নির্বাচন সাজানো কেন অদক্ষ তা বোঝা

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

বুদ্বুদ সাজানোর মতো, নির্বাচনের সাজানোর ক্ষেত্রে নেস্টেড লুপগুলির কারণে O(n^2) এর সবচেয়ে খারাপ-কেস এবং গড় জটিলতা রয়েছে। এর অর্থ হল উপাদানের সংখ্যা বাড়ার সাথে সাথে এর কার্যকারিতা নাটকীয়ভাবে হ্রাস পায়।

র্যাপিং আপ

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