Sorting
ডাটা স্ট্রাকচার অ্যালগরিদমে প্রাইমারি একটা টপিক হচ্ছে সর্টিং! যে কোন প্রোগ্রামিং ল্যাংগুয়েজের জন্য সর্টিং খুবই গুরুত্বপূর্ণ, আজ আমরা জানবো সর্টিং নিয়ে, চলুন শুরু করা যাক !!
Sorting Algorithm কি?
এক কথায় যাকে বলে Organizing data in order
সর্টিং অ্যালগরিদম ব্যবহার করা হয়, অ্যারে/ ডাটা এলিমেন্ট'স গুলো নির্দিষ্ট অর্ডারে সাজানোর জন্য। সেটা হতে পারে অ্যাসেন্ডিং অথবা ডিসেন্ডিং অর্ডারে!
-Ascending (Smaller to Larger)
-Descending (Larger to Smaller)
Example:
- Random - [3, 1, 4, 6, 8, 10]
- ascending - [1, 3, 4, 6, 8, 10]
- descending - [10, 8, 6, 4, 3, 1]
ডাটা স্ট্রাকচার অ্যালগরিদমে অনেক গুলো সর্টিং অ্যালগরিদম আছে৷ আমরা আমাদের প্রয়োজন উপর ভিত্তি করে যেকোনো সর্টিং অ্যালগরিদম ব্যবহার করতে পারি।
- Bubble Sort
- Selection Sort
- Merge Sort
- Quick Sort
- Insertion Sort
- Counting Sort
- Radix Sort
- Bucket Sort
- Heap Sort
- Shell Sort
Complexity of Sorting Algorithm:
যে কোনো অ্যালগরিদমের দক্ষতা বা কার্যকরিতা অথবা সহজ কথায় বলতে পারি কোন অ্যালগরিদম কতটুকু এফিসিয়েন্ট সেটা টাইম কমপ্লেক্সিসিটি এবং স্পেস কমপ্লেক্সিসিটি দ্বারা নির্ধারিত হয়।
Time complexity:
একটি অ্যালগরিদম রান করার জন্য কত সময় নেয় টাইম কমপ্লেক্সিসিটি সেটা ডিফাইন করে,টাইম কমপ্লেক্সিসিটি তিন ভাবে রিপ্রেজেন্ট করা যায়ঃ
- Big-O notation: অ্যালগরিদমের worst - case complexity দেয়।
- Omega notation: অ্যালগরিদমের best - case complexity দেয়।
- Theta notation: অ্যালগরিদমের average - case দেয়।
Space complexity:
যখন একটি অ্যালগরিদম একটি কম্পিউটারে চালানো হয়, তখন এটি একটি নির্দিষ্ট পরিমাণ মেমোরি বা জায়গা প্রয়োজন হয়। একটি প্রোগ্রাম এক্সিকিউট করার জন্য যে পরিমাণ মেমোরি ব্যবহার করা হয় এটাই স্পেস কমপ্লেক্সিসিটি। কারণ একটি প্রোগ্রাম চালানোর সময় ইনপুট ডেটা এবং টেম্পোরাল ভ্যালু বা অস্থায়ী ভ্যালু সংরক্ষণ বা স্টোর করার জন্য মেমোরির প্রয়োজন হয়।
স্পেস কমপ্লেক্সিসিটি হলো auxiliary এবং input space। এখন হয়তো আপনার মনে প্রশ্ন আসবে auxiliary space কি? auxiliary space হলো একটি অ্যালগরিদম দ্বারা ব্যবহৃত এক্সট্রা স্পেস বা টেম্পোরারি স্পেস। একটি অ্যালগরিদমের স্পেস কমপ্লেক্সিসিটি হলো ইনপুট সাইজের সাপেক্ষে নেয়া টোটাল স্পেস। স্পেস কমপ্লেক্সিসিটি এর মধ্যে অক্সিলিয়ারি স্পেস এবং ইনপুট দ্বারা ব্যবহৃত স্পেস উভয়ই অন্তর্ভুক্ত।
1.Bubble sort:
বাবল সর্ট হলো একটি সহজ সর্ট অ্যালগরিদম, এটি পাশাপাশি দুটি এলিমেন্ট তুলনা করে যতক্ষণ পর্যন্ত না এলিমেন্ট গুলো সর্টেড হয়।
### Working of bubble sort:
ফার্স্ট ইনডেক্স থেকে শুরু করে, প্রথম এবং দ্বিতীয় এলিমেন্টগুলির মধ্যে কম্পেয়ার করে। যদি প্রথম এলিমেন্ট দ্বিতীয় এলিমেন্ট এর চেয়ে বড় হয় তবে সেগুলি swap(অদলবদল) হবে, সহজ ভাষায় বলতে গেলে প্রথম এলিমেন্ট জায়গা পরিবর্তন করে। এখন দ্বিতীয় এলিমেন্ট এর সাথে তৃতীয় এলিমিনেটর কম্পেয়ার হবে, এভাবে কম্পেয়ার চলবে ততক্ষণ পর্যন্ত যতক্ষণ না সবচেয়ে বড় এলিমেন্ট'টি রাইট সাইডে চলে যাবে।
### Implementation:
আমরা একটা সিম্পল অ্যারে নিবো, সেটা কে আমরা অ্যাসেন্ডিং অর্ডারে সর্ট করবো,সেক্ষেত্রে আমরা বাবল সর্ট ব্যবহার করতে পারি।
- array: [1, 10, 2, 3, 5, 30, 40, 28]
- output: [1, 2, 3, 5, 10, 28, 30, 40]
এখানে, আমরা বাবল সর্ট ব্যবহার করে স্টেপ বাই স্টেপ অ্যারে সর্ট করবো।
First iteration:
- [1, 10, 2, 3, 5, 30, 40, 28] -> [1, 10] – no swapping
- [1, 10, 2, 3, 5, 30, 40, 28] -> [10, 2] – swap
- [1, 2, 10, 3, 5, 30, 40, 28] -> [10, 3] – swap
- [1, 2, 3, 10, 5, 30, 40, 28] -> [10, 5] –swap
- [1, 2, 3, 5, 10, 30, 40, 28] -> [10, 30] – no swapping
- [1, 2, 3, 5, 10, 30, 40, 28] -> [30, 40] – no swapping
- [1, 2, 3, 5, 10, 30, 40, 28] -> [40, 28] – swap
Second iteration:
- [1, 2, 3, 5, 10, 30, 28, 40] -> [1, 2] – no swapping
- [1, 2, 3, 5, 10, 30, 28, 40] -> [2, 3] – no swapping
- [1, 2, 3, 5, 10, 28, 30, 40] -> [3, 5] – no swapping
- [1, 2, 3, 5, 10, 30, 28, 40] -> [5, 10] – no swapping
- [1, 2, 3, 5, 10, 30, 28, 40] -> [10, 30] – no swapping
- [1, 2, 3, 5, 10, 30, 28, 40] -> [30, 28] – swap
Third iteration:
- [1, 2, 3, 5, 10, 28, 30, 40] -> [1, 2] – no swapping [array sorted]
- [1, 2, 3, 5, 10, 28, 30, 40] -> [2, 3] – no swapping
- [1, 2, 3, 5, 10, 28, 30, 40] -> [3, 5] – no swapping
- [1, 2, 3, 5, 10, 28, 30, 40] -> [5, 10] – no swapping
- [1, 2, 3, 5, 10, 28, 30, 40] -> [10, 28] – no swapping
Fourth iteration:
- [1, 2, 3, 5, 10, 28, 30, 40] -> [1, 2] – no swapping
- [1, 2, 3, 5, 10, 28, 30, 40] -> [2, 3] – no swapping
- [1, 2, 3, 5, 10, 28, 30, 40] -> [3, 5] – no swapping
- [1, 2, 3, 5, 10, 28, 30, 40] -> [5, 10] – no swapping
Bubble Sort Code in JavaScript (move the largest element to the end)
Optimized Bubble Sort Algorithm:
উপরের অ্যালগরিদমে, থার্ড ইটারেশনে অ্যারে সর্টেড হওয়ার পরও লুপের কারণে পুনরায় কম্পেয়ার হচ্ছে, এটা কোড এক্সিকিউশনের টাইম বাড়িয়ে দেয়। এটা সমাধানের জন্য, আমরা swap নামে একটা ভ্যারিয়েবল নিতে পারি, যদি এখানে এলিমেন্ট অদলবদল(swap) হয় তবে swap = true হবে, আদারওয়াইজ swap = false।
যদি কোন swapping না হয়, দ্যাট মিন্স অ্যারে অলরেডি সর্টেড, পুনরায় কম্পেয়ার করার প্রয়োজন নেই।
Optimized Bubble Sort Code in JavaScript
Bubble Sort complexity
টাইম কমপ্লেক্সিসিটি -
Worst and Average Case: O (n^2)
যখন অ্যারে রেন্ডম অর্ডারে থাকে
Best Case: O (n)
যদি অ্যারে অলরেডি সর্টেড হয়।
স্পেস কমপ্লেক্সিসিটি- O (1) constant space
When is the Bubble sort algorithm used?
বিয়েল ওয়ার্ল্ডে কম্পিউটার সায়েন্সে বাবল সর্ট খুব বেশি ব্যবহার হয়না, কম্পিউটার প্রোগ্রামার্স'রা বাবল সর্ট ব্যবহার করে কারেক্ট অর্ডারে সিকোয়েন্স অনুযায়ী নাম্বার সাজানোর জন্য। কারণ বাবল সর্ট অ্যালগরিদম'টি বুঝা এবং প্রয়োগ করাটা সহজ। পাশাপাশি দুটো এলিমেন্ট তুলনা করে সর্ট করে, বাবল সর্ট বড় ডেটা সেটের জন্য অপটিমাল(সর্বোত্তম) নয়, কিন্তু এটি অল্প সংখ্যক নাম্বার সর্টিং এর জন্য ভালো কাজ করে।
So far today, stay with me!!
keep reading and keep learning