Quick Sort Algorithm

Divide and Conquer :

Quick Sort এলগোরিদম মুলত Divide and Conquer এলগোরিদম অনুসরণ করে। "Divide and Conquer" এর পদ্ধতি টা হলো-

একটা সমস্যা(problem) কে অনেকগুলো সমস্যাগুচ্ছে(sub problem)

বিভক্ত(divide) করা এবং তারপর মুল সমস্যার(problem) সমাধান করার জন্য sub problem গুলোকে recursively সমাধান করা এবং sub problem এর সমাধান গুলোকে একত্রিত করা।

সুতরাং, "Divide and Conquer" ৩ টি ধাপ অনুসরণ করেঃ-

একটি problem কে কতগুলো sub problem এ বিভক্ত করা;
sub problem গুলো recursively সমাধান করে conquer করা;
"original problem" সমাধান এর জন্য sub problem এর সমাধান গুলো combine করা।

Quick Sort:

quick Sort এর এর heart হল partition , অর্থাৎ পার্টিশন বুঝতে পারলে কুইক শর্ট বুঝা কোনো

ব্যাপার ই না।

partition:

একটি Array

"partition" এর পরে

pivot(4) এর চেয়ে ছোট উপাদান গুলো pivot এর বাম দিকে থাকবে
pivot এর চেয়ে বড় উপাদান গুলো pivot এর ডান দিকে থাকবে এবং
pivotতার সঠিক জায়গায় সাজানো থাকবে।

[ Array শেষ উপাদান টি কে আমরা pivot হিসাবে ধরে নিয়েছি। ]

এখন, এই কাজগুলো করার জন্য আমাদের ২ টি variable লাগবে যেগুলো প্রথম অবস্থায় Array

এর প্রথম ইনডেক্স নির্দেশ করবে।

চিত্রে দেখা যাচ্ছে, i এবং j উভয় ই প্রথম অবস্থায় Array এর প্রথম ইনডেক্স কে নির্দেশ করছে,

এবার Array এর প্রথম ইনডেক্স এর উপাদান এর সাথে শেষ ইনডেক্স এর উপাদান মানে আমরা যাকে pivot বলছি, তার তুলনা করব, যদি প্রথম ইনডেক্স এর উপাদান pivot এর চেয়ে বড় হয়

তাহলে আমরা i এর মান ১ বাড়াব। আর যদি প্রথম ইনডেক্স এর উপাদান pivot এর চেয়ে ছোট হয় তাহলে p ইনডেক্স এ যে উপাদান আছে তার সাথে i ইনডেক্স এর উপাদান এর অদল-বদল

করব এবং তারপর p এর মান ১ বাড়িয়ে দিব।

int pivot  = A[end];
    int p = start;
    int temp;
    int i;

    for(i=start; i<end; i++) {
        if(A[i] <= pivot) {
            temp = A[i];
            A[i] = A[p];
            A[p] = temp;
            p++;
        }
    }

এখানে প্রথম ইনডেক্স এর উপাদান হচ্ছে 5 এবং pivot হচ্ছে 4 অর্থাৎ এই ২ টি উপাদান এর মধ্যে ইনডেক্স এর উপাদান pivot এর চেয়ে বড়। তাহলে শর্তানুযায়ী, আমরা ইনডেক্স এর মান ( i এর মান) ১ বাড়াব। এখন আমাদের i এর মান বেড়ে 2 হলো, কিন্তু p এর মান কিন্তু বাড়ে নি। সেটা 1 ই
আছে।

এখন, i এর বর্তমান ইনডেক্স (2 তম ইনডেক্স) এর উপাদান( 7) এর সাথে pivot এর তুলনা করব, এবার ও দেখা যাচ্ছে আগের মতই pivot ছোট। এবার ও তাহলে আমরা i এর মান 1 বাড়াব।

i এর মান 1 থেকে বেড়ে 3 হয়ে গেল! [ লক্ষ্য করুন, p এর মান কিন্তু সেই 1 ই আছে ]
এখন, i এর বর্তমান ইনডেক্স (3rd ইনডেক্স) এর উপাদান(6) এর সাথে pivot এর তুলনা করব।
যেহেতু 6>4 সুতরাং, i এর মান ১ বাড়বে এবং p বহাল তবিয়তে তার আগের জায়গা তেই থাকবে।

i এর মান ১ বেড়ে 4 হয়ে গেল! [ লক্ষ্য করুন, p এর মান কিন্তু সেই 1 ই আছে ]
এখন, i এর বর্তমান ইনডেক্স (4th ইনডেক্স) এর উপাদান(1) এর সাথে pivot এর তুলনা করব।
যেহেতু 1<4 অর্থাৎ i এর বর্তমান ইনডেক্স এর উপাদান pivot এর চেয়ে ছোটো। শর্তানুযায়ী এবার
p এর বর্তমান ইনডেক্স এর সাথে i এর বর্তমান ইনডেক্স এর মান অদলবদল করতে হবে এবং p এর মান, ১ বাড়াতে হবে। আর তার সাথে i এর মান তো ১ বাড়বেই(শর্তানুযায়ী)।

তাহলে, এতগুলো কাজ করার পর আমাদের অবস্থা নিচের ছবিটার মত হবেঃ

এখন আমাদের p এর মান বেড়ে গিয়ে 2 এবং i এর মান বেড়ে গিয়ে হলো 5.
এবার, i এর বর্তমান ইনডেক্স ( 5th ইনডেক্স) এর উপাদান(3) এর সাথে pivot এর তুলনা করব।
যেহেতু, 3<4 অর্থাৎ, i এর বর্তমান ইনডেক্স এর উপাদান pivot এর চেয়ে ছোটো। শর্তানুযায়ী এবার
p এর বর্তমান ইনডেক্স এর সাথে i এর বর্তমান ইনডেক্স এর মান অদলবদল করতে হবে এবং p এর মান, ১ বাড়াতে হবে। আর তার সাথে i এর মান তো ১ বাড়বেই(শর্তানুযায়ী)।

দেখা যাচ্ছে 2<4 অর্থাৎ, i এর বর্তমান ইনডেক্স এর উপাদান pivot এর চেয়ে ছোটো, সুতরাং আগের ধাপের মতই আমরা কাজ করব, তবে লক্ষ্য রাখতে হবে, i এর মান কিন্তু এবার বাড়বে না।
কারন i = 7 হয়ে গেলে তা লুপ থেকে বের হয়ে যাবে।

কাজ গুলো করার পর আমাদের অবস্থা নিচের ছবিটার মত হবেঃ

আর ছোট্ট একটা কাজ করলেই আমাদের partition শেষ হয়ে যাবে। সেটা হল, p এর ইনডেক্স এর উপাদান(5) এর সাথে Array এর শেষ ইনডেক্স এর উপাদান(4) এর অদলবদল করতে হবে। এবং
শেষে p এর মান টা রিটার্ন করে দিবঃ

 temp = A[p];
    A[p] = A[end];
    A[end] = temp;
    return p;

তাহলে আমরা নিচের ছবির মত কিছু একটা পাবঃ

আমরা partition এর শেষ পর্যায়ে চলে এসেছি, কারন, আমরা দেখতে পাচ্ছিঃ

pivot(4) এর চেয়ে ছোট উপাদান গুলো pivot এর বাম দিকে আছে
pivot এর চেয়ে বড় উপাদান গুলো pivot এর ডান দিকে আছে এবং
pivot তার সঠিক জায়গায় সাজানো আছে।

তাহলে, এখন আমরা partition ফাংশন টা সি ল্যাঙ্গুয়েজ দিয়ে লিখে ফেলতে পারিঃ-

int Partition(int *A, int start, int end)
{
    int pivot  = A[end];
    int p = start;
    int temp;
    int i;

    for(i=start; i<end; i++) {
        if(A[i] <= pivot) {
            temp = A[i];
            A[i] = A[p];
            A[p] = temp;
            p++;
        }
    }
    temp = A[p];
    A[p] = A[end];
    A[end] = temp;
    return p;
}

এখন, আমদের pivot ঠিক যায়গামত আছে সেটা বুঝলাম, কিন্তু তার ডান ও বামের উপাদানগুলো কিন্ত সাজানো(sorted) অবস্থায় নেই। তাদেরকে সাজাতে আমাদের দরকার হবে quick Sort এর।

Quick sort:

quick Sort ফাংশন টি কাজ করবে recursive উপায়ে। প্রথমে আমরা পার্টিশন ফাংশন টি কল করব, এবং এটা আমাদের পিভট এর ইনডেক্স রিটার্ন করবে। সেই ইনডেক্স এর উপর ভিত্তি করেই আমরা
recursive ভাবে quick Sort কে কল করব। বলে রাখা ভাল, recursive ফাংশন এর অবশ্যই একটা বেস কেস থাকতে হবে, তা না হলে সেটা আজীবন চলতেই থাকবে।আমাদের ফাংশন এর বেস কেস টা হল
যখন Array এর শুরুর ইনডেক্স শেষ ইনডেক্স এর চেয়ে বড় বা সমান হয়ে যাবে তখন। অর্থাৎ শুরুর ইনডেক্স শেষ ইনডেক্স এর বড় বা সমান হয়ে গেলেই আমরা ফাংশন থেকে বের হয়ে যাব!

নিচের চিত্র টি তে পুরো ঘটনা দেখানো হয়েছেঃ-

চিত্রের বর্ণনা দেয়ার আগে, আমরা কুইক সর্ট ফাংশন টা লিখে ফেলিঃ

void quickSort(int *A, int start, int end)
{
    int partitionIndex;
    if(start<end) {
        partitionIndex = Partition(A,start,end);
        quickSort(A,start, partitionIndex-1);
        quickSort(A,partitionIndex+1,end);
    }
}

এবার আসা যাক চিত্রের বর্ণনায়, চিত্রে কুইক সর্ট কে আমি সংক্ষেপে "QS" লিখেছি আর pivot index (partition ফাংশন যেটা রিটার্ন করে আর কি) কে লিখেছি pivot।

এখানে প্রথমে আমরা array index দিয়েছি (1,7). মানে শুরুর ইনডেক্স 1 আর শেষ ইনডেক্স 7.
এই টুকু রেঞ্জ এর মধ্যে পার্টিশন করে আমরা পিভট ইনডেক্স পাচ্ছি 4. এখন কুইক সর্ট কে আবার কল করা হবে, এবং এবার রেঞ্জ হবে (1 থেকে pivot index - ১ পর্যন্ত)
কোড দেখলেই বিষয় টা পরিস্কার হওয়ার কথা

 quickSort(A,start, partitionIndex-1);

এখানেই শেষ নয়। কুইক সর্ট কে আবার কল করা হবে এবং এবার রেঞ্জ হবে (pivotIndex + 1 থেকে 7) পর্যন্ত। মানে ৫ থেকে ৭ পর্যন্ত আর কি।

 quickSort(A,partitionIndex+1,end)

এই প্রক্রিয়া চলতে থাকবে যতক্ষন না পর্যন্ত আমাদের প্রথম ইনডেক্স শেষ ইনডেক্স এর সমান বা বড় হয়ে যায়।

তাহলে কুইক সর্ট এলগোরিদম এর সম্পূর্ণ implementation টা দেখা যাকঃ

// Quick Sort Algorithm

#include<stdio.h>

int Partition(int *A, int start, int end)
{
    int pivot  = A[end];
    int p = start;
    int temp;
    int i;

    for(i=start; i<end; i++) {
        if(A[i] <= pivot) {
            temp = A[i];
            A[i] = A[p];
            A[p] = temp;
            p++;
        }
    }
    temp = A[p];
    A[p] = A[end];
    A[end] = temp;
    return p;
}

void quickSort(int *A, int start, int end)
{
    int partitionIndex;
    if(start<end) {
        partitionIndex = Partition(A,start,end);
        quickSort(A,start, partitionIndex-1);
        quickSort(A,partitionIndex+1,end);
    }
}

int main()
{
    int A[] = {7,6,5,4,3,2,1,0};
    quickSort(A,0,7);
    int i;
    for(i=0; i<8; i++)
        printf("%d ",A[i]);
}