সর্টিং অ্যালগোরিদম - Sorting algorithm

সর্টিং: কুইক সর্ট (Quick Sort) অ্যালগরিদম

Quick sort Bangla tutorial/ Quick sort Bangla/ qsort algorithm

কুইক সর্ট (Quick sort) (aka: qsort, Quicksort) এক‌টি দ্রুতগতির স‌র্টিং অ্যালগ‌রিদম যা C.A.R Hoare আ‌বিষ্কার ক‌রেন। এ‌টি এক‌টি ভাগ কর শাসন ক‌র (Divide and Conquer) ঘরনার অ্যালগ‌রিদম যেখা‌নে প্রতিবার আমরা অ্যারেটিকে ২টি ভাগে ভাগ করে সর্ট করবো। আপনারা যদি আগে মার্জ সর্ট নিয়ে দেখে থাকেন তবে বিষয়টি হয়তো ইতোমধ্যে বুঝতে পেরেছেন। (Quick sort Bangla tutorial)

Quick sort Bangla tutorial

কুইক সর্টের (Quick sort) মাধ্য‌মে সর্ট কর‌তে প্রতিবার আমরা অ্যারের যেকোনো একটি ইলিমেন্টকে এর সর্টেড পজিশনে (Sorted position) বসাবো এবং রিকার্সিভ কলের মাধ্যমে এর দুইপাশের সাব-অ্যারের জন্যও একই কাজ করবো। আমরা যেই ইলিমেন্টকে এর সর্টেড পজিশন এ বসাবো তার বামের সকল ইলিমেন্ট তার ছোট থাকবে এবং ডানের সকল ইলিমেন্ট তার বড় বা সমান থাকবে।

এই “একটি ইলিমেন্ট” বাছাই করার বিভিন্ন পদ্ধতি রয়েছে। তবে আমরা বুঝার এবং ব্যাখার সুবিধার্থে সব সময় শেষের ইলিমেন্টকে এর সর্টেড পজিশনে নিয়ে আসবো। এই ইলিমেন্টটিকে পিভট ইলেমেন্ট (Pivot element) বলা হয়।

এবার আসি সর্টেড পজিশন (Sorted position) কি? ধরেন একটি অ্যারে দেয়া আছে আপনাকে, arr[]=\{4,8,2,5,9,7,2,6\} । আপনাকে বলা হলো 6 এর সর্টেড পজিশন কোনটা? এখন দেখা যাচ্ছে মূল অ্যারেতে 6 এর পজিশন (ইনডেক্স) হলো 7। এবার যদি অ্যারেটিকে সর্ট করা হয় তবে arr[]=\{2,2,4,5,6,7,8,9\} এরকম পাবো। দেখা যাচ্ছে এখানে 6 এর ইনডেক্স 4। তাই এই অ্যারেতে 6 এর সর্টেড পজিশন 4।

আমরা যেই পদ্ধতিতে 6 কে এর সর্টেড পজিশনে নিয়ে যাবো এবং শর্তানুসারে, 6 এর বামের সব ইলিমেন্ট 6 এর ছোট এবং 6 এর ডানের সকল ইলিমেন্ট 6 এর বড় বা সমান হবে সেই পদ্ধতিটির নাম হল পার্টিশনিং (Partitioning)।

কুইক সর্ট শেখার জন্য পার্টিশনিং সবার আগে বুঝতে হবে। এটি বুঝলেই বাকিটুকু এক তুড়িতেই বুঝা সম্ভব।

এবার চলুন আমরা পার্টিশনিং করার অ্যালগরিদমটি দেখে নেই।

Quick sort: অ্যারেকে পার্টিশন করার অ্যালগরিদম – Partitioning

ধরা যাক আমরা কোন অ্যারের l থেকে r তম ইনডেক্স পর্যন্ত পার্টিশন করবো এবং ধরা যাক আমরা অ্যারেটির r^{th} ইলিমেন্টকে এর সর্টেড পজিশনে নিয়ে আসবো। পার্টশনিং লজিকটি আসলে খুবই সহজ। শুধু একটু খেয়াল করা লাগবে আসলে কি ঘোটছে ভেতরে।

  1. দুটি ভ্যারিয়েবল i এবং j নিতে হবে প্রথমে এবং শুরুতে i এবং j উভয়ের মান l থাকতে হবে।
  2. যতক্ষণ j<r হয়, ততক্ষন নিচের সাব স্টেপের মত করে কাজ করবো।
    1. যদি অ্যারের j ইনডেক্স এর ইলিমেন্ট অ্যারের শেষ ইলিমেন্টের চেয়ে ছোটো হয় তবে,
      1. j^{th} ইনডেক্স এর ইলিমেন্ট এর সাথে i^{th} ইনডেক্স এর ইলিমেন্ট এর swap করবো।
      2. i এর মান 1 বাড়াবো।
    2. j এর মান 1 বাড়াবো।
  3. লুপের শেষ অ্যারের i^{th} এবং r^{th} ইলিমেন্ট এর swap করবো।
  4. i এর মান পিভট ইন‌ডেক্স হি‌সে‌বে রিটার্ন করবো।

এখন আসলে কি ঘটল? এখানে প্রথম স্টেপ এ লক্ষ করলে দেখবেন আমরা দুইটি ভ্যারিয়েবল বা চলক নিয়েছি (i,j) এবং উভয়কেই শূন্যতে সেট করে রেখেছি। তারপর একটি লুপ (while) ব্যবহার করেছি যেটি j এর এর থেকে যতক্ষণ ছোট থাকবে, ততক্ষন চলবে। লুপের ভেতরে (Sub-step 2/1) আমরা একটি কন্ডিশন (if) ব্যবহার করেছি এবং এখান থেকেই প্রধান পার্টিশনিং লজিক কাজ করছে।

যদি ভাল করে লক্ষ করেন তবে দেখবেন যে i কখনও j এর থেকে বড় হতে পারবে না। কারন i এর মান বাড়বে তখনি যখন স্টেপ ২ এর সাব-স্টেপ ১ এর শর্ত পূরণ হবে। কিন্তু j এর মান সব সময় বাড়বে।

এখন নিচের ভিজুয়ালাইজেশনটি দেখি আমরা। তারপর আরও ব্যাখ্যা করবো প্রসেসটি।

Quick sort visualization with Bangla explanation

এখানে l=0 এবং r=7 বিবেচনা করা হয়েছে। (ভি‌ডিওর শেষদি‌কে রিটার্ন এর জায়গায় রিটার্ট লিখা র‌য়ে‌ছে। এর জন্য আ‌মি দুঃ‌খিত)

উপরের ভিডিওটিতে যদি লক্ষ করেন তবে দেখতে পাবেন যে, i এবং j এর মাঝে সবসময় j, i এর বড় বা সমান থাকবে। এবং i \neq j শর্ততে i সব সময় এমন জায়গায় থাকবে যেখানে i তম ইলিমেন্ট অ্যারের শেষ ইলিমেন্ট এর থেকে বড় হবে। এবং লুপের সবার শেষ ধাপে i যাকে নির্দেশ করবে সে অবশ্যই অ্যারের শেষ ইলিমেন্ট এর সমান অথবা বড় হবে কারণ j অ্যারের শেষ পর্যন্ত গিয়েছে এবং এর মধ্যে অ্যারের শেষ ইলিমেন্ট থেকে ছোট একটি ইলিমেন্ট পেলেও তা swap করে i এর মান বাড়িয়ে নিয়েছে। তাই আমরা লুপ থেকে বের হয়ে swap করার মাধ্যমে শেষ ইলিমেন্টকে (Pivot element) তার সর্টেড পজিশনে রাখি।

উপ‌রের অ্যালগ‌রিদম‌টি‌কে int partition(int l,int r,int arr[]) ফাংশনে ইমপ্লিমেন্ট করা হ‌য়ে‌ছে।

যেহেতু আগেই বলেছি, কুইক সর্ট একটি ভাগ কর শাসন কর বা ডিভাইড এন্ড কোন‌কোয়ার অ্যালগরিদম, তাই আমাদের i এর মান টি লাগবে অ্যারেটিকে ভাগ করার জন্য। কারন অ্যারের মধ্যে i ইনডেক্স এ যে ইলিমেন্ট রয়েছে (swap করার পর) তা তার সর্টেড পজিশনে রয়েছে। শুধু তার আগের এবং পরের সাব-অ্যারেকে সর্ট করা লাগবে এখন।

কুইক সর্ট অ্যালগরিদম (Quick sort algorithm in Bangla)

এতক্ষন আমরা পার্টিশন বুঝেছি। এখন আমরা পুরোপুরি প্রস্তুত কুইক সর্ট বুঝার জন্য। আমরা একটি ফাংশন নিলাম void qsort(int l,int r,int arr[]) নামে। এখানে l এবং r যথাক্রমে অ্যারে/সাব-অ্যারের বাম এবং ডান ইনডেক্স নির্দেশ করে। এখন নিচ থেকে আমরা কুইক সর্টের কোডটি দেখে নিই।

Quick sort C++ implementation

উপরের কোডের দিকে তাকান। খুবই সহজ কোড। প্রথমেই আমরা বেস কেস বিষয়ে ভেবেছি। যদি l > r হয়, এটা সম্ভব না। তাই আমরা রিকার্শন থামাবো।

নয়তো আমরা partition() ফাংশন কল করার মাধ্যমে অ্যারের l-r পর্যন্ত পার্টিশন করবো যেখানে r^{th} ইলিমেন্টকে আমরা পিভট ইলিমেন্ট হিসেবে বিবেচনা করছি। পার্টিশন হয়ে যাবার পর আমরা জানি p হলো পিভট ইলিমেন্ট এর সর্টেড পজিশন, তাই আমরা রিকার্সিভ ভাবে বাম ( l=l, r=p-1 এবং ডান সাব-অ্যারেতে l=p+1,r=r একই প্রসেস করে সাব-অ্যারের পিভট ইলিমেন্ট বছাই করবো এবং তাকে তার সর্টেড পজিশনে নিয়ে যাবো। এতে করে একসময় অ্যারেটি সর্ট হয়ে যাবে।

কুইক সর্ট , quick sort bangla tutorial

সুতরাং কুইক সর্ট অ্যালগোরিদমটি হলো,

  1. যদি l>r হয়ে যায় তবে থামতে হবে। কারণ l , r থেকে বড় হতে পারে না।
  2. অ্যারের r^{th} ইলিমেন্টকে (Pivot element) পার্টিশনিং এর মাধ্যমে সর্টেড পজিশনে নিয়ে আসি।
  3. রিকার্সিভ ভাবে পিভট পজিশন বা p এর বাম সাব-অ্যারেকে সর্ট করি।
  4. রিকার্সিভ ভাবে পিভট পজিশন বা p এর ডান সাব-অ্যারেকে সর্ট করি।
Quicksort

আরও পরুন এখানে

কুইক সর্ট অ্যালগরিদম কমপ্লেক্সিটি

কুইক সর্টের বেস্ট কেস এবং এভারেজ কেস টাইম কমপ্লেক্সিটি হলো O(n log(n)) , কিন্তু বাজে কেস বা Worst case টাইম কমপ্লেক্সইটি O(n^2) । আমরা O(n^2) থেকে O(n log(n)) এ নামতে পারি। এই উত্তরটি পরুন।

কুইক সর্টের worst case স্পেস কমপ্লেক্সিটি O(n)

কুইক সর্ট নাকি মার্জ সর্ট (Quick sort vs Merge sort)?

মার্জ সর্টের টাইম কমপ্লেক্সিটি সব সময় O(n lon(n)) কিন্তু কুইক সর্টের (Quick sort) টাইম কমপ্লেক্সিটি O(n log(n)) থেকে O(n^2) এর মধ্যে থাকে।

কখন কুইক সর্ট ব্যবহার করবোঃ ক্ষেত্র বিশেষে কুইক সর্ট মার্জ সর্ট থেকে ভালো পারফর্ম করে। যেমন যখন ডাটাসেট রেন্ডম থাকে ,আগে থেকেই সর্টেড (ASC বা DESC) না থাকে, এবং ইলিমেন্টের পুনরাবৃত্তি কম থাকে।

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

কুইক সর্ট: Full Quick sort code all together – with Bangla explanation

তো আজকে এই পর্যন্তই। বুঝতে সমস্যা হলে কমেন্ট বক্স আছেই। তা নহলে যেকোনো ভাবে যোগাযোগ কইরেন। #happy_coding.

লেখাটি কেমন লেগেছে আপনার?

রেটিং দিতে হার্টের উপর ক্লিক করুন।

গড় রেটিং / 5. মোট ভোট:

আপনি প্রথম ভোটদাতা.

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

4 টি মন্তব্য

      1. ভাইয়া আপনার সাথে কিভাবে যোগাযোগ করবো, যদি বলতেন

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button