সিলেকশন সর্ট
12 আগস্ট 2022
Selection sort:
সিলেকশন সর্ট হলো খুব স্ট্রেইট-ফরোয়ার্ড সর্টিং অ্যালগরিদম, বিগিনারদের সাথে পরিচয় করিয়ে দেবার জন্য একটি দুর্দান্ত সর্টিং অ্যালগরিদম, এটি আন-সর্টেড লিস্ট থেকে সবচেয়ে ছোট এলিমেন্ট'কে সিলেক্ট করে এবং প্রতিটি ইটারেশনে সেই এলিমেন্ট'কে শুরুর দিকে সাজাতে থাকে ।
Working of Selection Sort:
আমরা একটি আন-সর্টেড লিস্ট থেকে ফার্স্ট এলিমেন্ট'কে মিনিমাম নাম্বার ধরে নিবো, যেই এলিমেন্ট'কে আমরা মিনিমাম নাম্বার ধরে নিবো তার সাথে অন্য সব এলিমেন্ট কম্পেয়ার করে সত্যিকার অর্থে মিনিমাম এলিমেন্ট কোনটা সেটা খুঁজে বের করবো, এখন আমাদের আপকামিং এলিমেন্ট যদি কারেন্ট মিনিমাম এলিমেন্ট থেকে ছোট হয়, তাহলে সেই এলিমেন্ট'কে আমরা কারেন্ট এলিমেন্ট হিসেবে সেট করে দিবো।
Implementation:
আমরা একটা অ্যারে নিলাম
আন-সর্টেড - [5, 2, 4, 6, 1, 3]
সর্টেড - [1, 2, 3, 4, 5, 6]
**First pass: **
- প্রথম এলিমেন্ট'কে আমরা কারেন্ট মিনিমাম [5] হিসেবে সেট করে নিলাম,
set Current Minimum = 5
2.কম্পেয়ার ফার্স্ট এলিমেন্ট উইথ সেকেন্ড এলিমেন্ট, যদি সেকেন্ড এলিমেন্ট ফার্স্ট এলিমেন্ট থেকে ছোট হয় তবে আপকামিং মিনিমাম এলিমেন্ট টা কারেন্ট মিনিমাম এলিমেন্টে সেট হয়ে যাবে।
2 < 5 ? Yes
New Current Minimum= 2
- পুনরায় আমরা থার্ড এলিমেন্ট'কে কম্পেয়ার করবো কারেন্ট মিনিমাম এলিমেন্ট এর সাথে।
4 < 2 ? No
Current Minimum = 2
এখানে কারেন্ট মিনিমাম আগের'টা বহাল থাকবে, এভাবে আমরা কারেন্ট মিনিমাম এলিমেন্ট এর সাথে বর্তমান মিনিমাম এলিমেন্ট কম্পেয়ার করে যাবো, যতক্ষণ পর্যন্ত না অ্যারেটি সর্টেড হয়।
- 6 < 2? No
Current Minimum = 2
5 .আমরা পুনরায় পাঁচ নাম্বার এলিমেন্ট কম্পেয়ার করবো,
1 < 2? Yes
Current Minimum= 1
নোটঃ এখন, আমাদের নতুন মিনিমাম এলিমেন্ট সেট হচ্ছে = [1]
- এবার আমরা সর্বশেষ এলিমেন্ট'কে কম্পেয়ার করবো, কারেন্ট মিনিমাম এলিমেন্ট এর সাথে ,
3 < 1 ? No
Current Minimum= 1
নোটঃ প্রতিটি pass এর পর কারেন্ট মিনিমাম এলিমেন্ট এর সাথে মোস্ট স্মোলেস্ট এলিমেন্ট swap হবে। ।
অবশেষে, আমরা আমাদের ফার্স্ট ইটারেশনে আন-সর্টেড অ্যারে লিস্ট থেকে, সর্টেড ফার্স্ট এলিমেন্ট খুঁজে পেয়েছি 1, আমরা এখন এলিমেন্ট 2থেকে পুনরায় কম্পেয়ার করবো, এভাবে এলিমেন্ট কম্পেয়ার করে সর্বনিম্ন এলিমেন্ট'কে দ্বিতীয় স্থানে বসাবো, এভাবে পুরো প্রসেস চলবে যতক্ষণ না আন-সর্টেড অ্যারে লিস্ট'টি সর্টেড হচ্ছে।
array - [1, 5, 2, 4, 6, 3]
**Second pass: **
current minimum = 5
-
2 < 5? Yes -> current minimum = 2
-
4 < 2? No -> current minimum = 2
-
6 < 2? No -> current minimum = 2
-
3 < 2? No -> current minimum = 2
array - [1, 2, 5, 4, 6, 3]
**Third pass: **
current minimum = 5
-
4 < 5? Yes -> current minimum = 4
-
6 < 4? No -> current minimum = 4
-
3 < 4? Yes -> current minimum = 3
array - [1, 2, 3, 5, 4, 6]
Fifth Pass:
current minimum = 5
-
4 < 5? Yes -> current minimum = 4
-
6 < 4? No -> current minimum = 4
Sorted array - [1, 2, 3, 4, 5, 6]
## selection sort code in JavaScript (smallest element will move to the left)
এখন জেনে নেয়া যাক এটি কিভাবে কাজ করে-
১.প্রথমত, আমরা আউটার লুপ তৈরি করি, এবং প্রথম উপাদানটি'কে লয়েস্ট ভ্যালু হিসেবে সেট করি।
২.এরপরে আমরা i+1 থেকে শুরু করে একটা ইনার লুপ তৈরি করি।
৩. ইনার লুপের ভিতরে আমরা কম্পেয়ার করি, কারেন্ট ভ্যালু আমাদের লয়েস্ট ভ্যালু থেকে ছোট কিনা, যদি ছোট হয় তবে আমরা কারেন্ট লয়েস্ট ভ্যালু আপডেট করি।
৪.পরবর্তীতে আমাদের লয়েস্ট ভ্যালু(i) যদি কারেন্ট লয়েস্ট ভ্যালুর সাথে না মিলে, নতুন লয়েস্ট ভ্যালু ডিফারেন্ট সেক্ষেত্রে swap(অদলবদল) হবে।
এরপর, আমরা আবার আউটার লুপে ফিরে যাবো, i++ হবে, এবং এভাবে অ্যারের প্রতিটি এলিমেন্ট চেক না হওয়া পর্যন্ত পুরো প্রসেস চলবে।
**Time complexity: **
quadratic time complexity O(n^2)
অ্যারে যদি নেয়ারলি সর্টেড ওর সর্টেড হয়, তারপরে ও সিলেকশন সর্ট প্রতিটি এলিমেন্ট চেক করে মিনিমাম এলিমেন্ট খুঁজে বের করে। এমনকি Swap হোক বা নাক হোক।
**space complexity: **
Constant space O(1)
সিলেকশন সর্ট হলো in-place অ্যালগরিদম, যার অর্থ হলো এটির কোন এক্সট্রা স্পেস এর প্রয়োজন নেই! এবং যেই মেমোরিতে ডাটা ধারণ করে, সেম মেমোরিতেই আউটপুট তৈরি করে।
When to use selection sorting algorithm:
সিলেকশন সর্ট খুব বেশি ইউজ হয়না, ছোট ডেটা সেটের জন্য সিলেকশন সর্ট ভালো কাজ করে , যেহেতু সিলেকশন সর্ট এর টাইম কমপ্লেক্সিসিটি O(n^2) যা বড় ডাটা সেটের জন্য এফিশিয়েন্ট নয়, তবে সিলেকশন সর্টের স্পেস কমপ্লেক্সিসিটি এফিশিয়েন্ট, কারণ এটি সর্টিং এর সময় সম্ভাব্য সংখ্যক মিনিমাম নাম্বার swap(অদলবদল) করে।
So far today, stay with me!!
keep reading and keep learning