কুইক সর্ট অ্যালগরিদম – Quick Sort Algorithm

Post updated on 15th July, 2019 at 10:29 pm

একটা অ্যারেকে সর্ট করার জন্য বেশ কিছু অ্যালগরিদম রয়েছে। একেকটার একেক বৈশিষ্ট্য বা সুবিধা-অসুবিধা রয়েছে। Efficient sorting algorithm-গুলোর মধ্যে কুইক সর্ট অন্যতম। Merge Sort এর মত Quick Sort-ও Divide and Conquer নামক algorithm design paradigm মেনে চলে। Average case এ quicksort এর complexity হচ্ছে O(n log n) কিন্তু worst case এ এর complexity O(n²) যা Bubble sort এর কমপ্লেক্সিটির সমান। অপরপক্ষে merge sort এর worst case এর কমপ্লেক্সিটিও O(n log n).

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

উপরে একটা unsorted array নেয়া হয়েছে। এটাকে কুইক সর্ট এলগরিদমের মাধ্যমে আমরা ছোট থেকে বড় আকারে সাজাবো।

এই অ্যালগদিরমের জেনারেল আইডিয়া হচ্ছে, অ্যারের একটা করে element নিবা আর তাকে বাকি element-গুলোর সাথে তুলনা করে সঠিক জায়গায় (sorted position) বসাবা। এমন ভাবে বসাতে হবে যেন এই ইলিমেন্টের বাম দিকের সবগুলো ভ্যালু তার চেয়ে ছোট হয় আর ডান দিকের ভ্যালুগুলা বড় হয়। ধরো, এই অ্যারের সর্বশেষ ইলিমেন্টকে আমরা তার সঠিক স্থানে বসাতে চাই। একটা অ্যারে বা সাব-অ্যারের যেই ইলিমেন্টকে সঠিক জায়গায় বসানোর জন্য সিলেক্ট করা হবে তাকে অ্যালগরিদমের পরিভাষায় বলা হয় pivot. কোন অ্যারের পিভট হিসেবে শুরুর ভ্যালু অথবা শেষের ভ্যালুকে সিলেক্ট করা যায়। এই উদাহরণের ক্ষেত্রে আমরা অ্যারের শেষ ভ্যালুটাকে pivot ধরি। pivot 4 এর মানকে আমরা যদি সঠিক পজিশনে বসাতে চাই তাহলে সেই পজিশনটা কত হবে? zero based index হিসেবে অ্যারের শুরুর ইন্ডেক্স হচ্ছে 0, শেষ ইন্ডেক্স 7. লিস্ট থেকে আমরা দেখতে পাই 4 এর চেয়ে ছোট মানগুলো হচ্ছে 2, 1, 3 এবং বড় মানগুলো হচ্ছে 7, 8, 6, 5. তার মানে 4 এর পজিশন হবে 2, 1, 3 এই সংখ্যাগুলোর পরে আর 7, 8, 6, 5 এই সংখ্যাগুলোর আগে। সুতরাং 3 নাম্বার ইন্ডেক্সে 4 বসবে কারণ অ্যারের ইন্ডেক্স শুরু হয়েছে 0 থেকে। এইটুকু বুঝেছো? না বুঝে থাকলে এই প্যারাটা আবারো পড়।

উপরের কাজটা করার পরে অ্যারের একটা মাত্র সংখ্যা (4) সর্টেড হয়ে নিজ পজিশনে বসলো। এখন অ্যারেটাকে আমরা দুইটা ভাগে ভাগ করে ফেলতে পারি। 4 এর বাম পাশের ছোট সংখ্যাগুলোর একটা অ্যারে (0 to 2 index) এবং 4 এর ডান পাশের বড় সংখ্যাগুলোর আরেকটা অ্যারে (4 to 7 index)। 4-কে কোন অ্যারেতেই ফেলি নাই কারণ সে sorted হয়ে গিয়েছে। এখন বাম পাশের অ্যারের শেষ সংখ্যাটাকে pivot ধরে সেটাকে তার সঠিক পজিশনে বসাতে হবে। এর ফলে এই ৩টি সংখ্যা বিশিষ্ট অ্যারেটি আবারো দুই ভাগ হবে। এভাবে রিকার্সিভলি পুরো অ্যারেকে ছোট ছোট অ্যারেতে ভাঙ্গার মাধ্যমে অ্যারেটা সর্টেড হয়ে যাবে। মার্জ সর্টের ক্ষেত্রে অ্যারেকে ভাগ করার পরে সেটাকে আবার মার্জ করতে হত। কিন্তু কুইক সর্টের ক্ষেত্রে সেরকম মার্জ করার দরকার হয় না।

অ্যারের শেষ সংখ্যাটা বা pivot-কে জায়গা মত বসানো আমাদের মানুষের পক্ষে কোন ঘটনা না। কিন্তু কম্পিউটারের পক্ষে আমাদের চিন্তা করে বসায় দেয়া সম্ভব না। তাকে কিছু রুলস ঠিক করে দিতে হবে। সে ঐ রুলসগুলো মেনে পিভটকে জায়গা মত নিয়ে আসবে। অনেক ভাবেই পিভটকে তার স্বস্থানে place করা বা অ্যারেকে পার্টিশন করা যেতে পারে। আমি একটা পদ্ধতি ধরে এগুচ্ছি।

আমাদের লিস্টটা হচ্ছেঃ 2 7 1 8 6 3 5 4. pivot = 4. শেষ সংখ্যাটাকে জায়গা মত বসাবো। তাই অ্যারেটাকে কল্পনা করি 2 7 1 8 6 3 5 পর্যন্ত। 2 7 1 8 6 3 5 এই অ্যারের উপর আমরা কাজ করবো।

এখন অ্যারের শুরু থেকে প্রতিটা মানের সাথে পিভটের কম্পেয়ার করবো। অ্যারের কোন ইনডেক্সের মান যদি পিভটের চেয়ে ছোট হয় তাহলে এর পরের মানের সাথে পিভটের চেক করবো। যতক্ষন পর্যন্ত পিভটের চেয়ে ছোট কোন সংখ্যা পাওয়া যেতে থাকবে ততক্ষণ আমরা অ্যারের বাম থেকে ডানের দিকে সরে আসতে থাকবো। আমাদের হাতে থাকা 2 7 1 8 6 3 5 অ্যারের শুরুর সংখ্যাটা পিভটের চেয়ে ছোট। তাই পরের সংখ্যার সাথে চেক করতে চলে যাব। পরের সংখ্যা 7 পিভটের চেয়ে বড়। তাই আমরা আর ডানে move করবো না।

এখন অ্যারের ডান থেকে বামে মুভ করবো। আর চেক করবো কোন সংখ্যা পিভটের চেয়ে বড় কিনা (আগেরটার উল্টা)। যদি বড় হয় তাহলে ডান থেকে বামে মুভ করবো। অন্যথায় মুভ করা থামিয়ে দিব। দেখা গেল 2 7 1 8 6 3 5 এই অ্যারের সর্বডানের সংখ্যাটা 5. যা পিভট 4 এর চেয়ে বড়। তাই ডান থেকে বামে মুভ করব। বামে গিয়ে পাওয়া গেল 3, যা পিভটের চেয়ে ছোট। তাই আবার বামে মুভ করা সম্ভব না।

এখন আমাদের কাজ হচ্ছে বাম থেকে ডানে যাবার সময় যেই ভ্যালুতে আটকে গিয়েছিলাম, তার সাথে এই ভ্যালুটার swap করা। তাহলে 7 ও 3 নিজেদের মধ্যে জায়গা বদল করবে। ফলে updated array-টা হবে  2 3 1 8 6 7 5. এসব করে কী লাভ হচ্ছে বলতে পারো? দেখো, আমরা অ্যারের শুরুর ২ টা ইন্ডেক্স আর শেষের দুইটা ইন্ডেক্সের সাথে পিভটের কম্পেয়ার করেছিলাম। এই সোয়াপ করার ফলে অ্যারের প্রথম দুইটা ইন্ডেক্সের মান পিভট 4 এর চেয়ে ছোট এবং শেষের দুইটা সংখ্যার মান পিভটের চেয়ে বড়। আমরা অ্যারেটার একটা পার্টিশন পয়েন্ট খুঁজে বের করার চেষ্টা করছি যেখানে 4-কে বসিয়ে দিতে পারি। বাম থেকে ডানে ও ডান থেকে বামে যাওয়ার কাজটা এই পার্টিশন পয়েন্ট খুঁজে পাওয়ার আগ পর্যন্ত চালিয়ে যতে হবে। প্রথম ২ টা আর শেষ ২ টা মান যেহেতু চেক করা হয়ে গেছে তাই বাকিগুলোর সাথে পিভটের চেক করবো। 2 3 1 8 6 7 5 অ্যারের তৃতীয় মানের (1) সাথে চেক করে পাওয়া গেল সেটা 4 এর চেয়ে ছোট। তাই আরেক ঘর ডানে মুভ করে 8 (৮) পাওয়া গেল। যেহেতু এটা 4 এর চেয়ে বড় তাই আর ডানে মুভ করা যাবে না। এখন ডান দিক থেকে চেক করা শুরু করতে হবে। শেষের দুইটা মান আগেই চেক করা হয়েছে তাই এখন শেষ থেকে তৃতীয় মান 6 এর সাথে কম্পেয়ার করে দেখা গেল এটা 4 এর চেয়ে বড়। তাই আরেক ঘর ডান থেকে বামে মুভ করে পাওয়া গেল 8 (৮)।

• দুটি সংখ্যা সোয়াপ করার তিনটি পদ্ধতি জানা যাবে এখান থেকে

লক্ষ্য করো, বাম থেকে ডানে আসার সময় ৮ এ এসে আটকে গেছিলাম, আবার ডান থেকে বামে যাওয়ার সময়ও ৮ এ এসে আটকে গেছি। তার মানে আমাদের আর কোন মানের সাথে পিভটের কম্পেয়ার করা বাকি নাই। যেই ভ্যালুতে এসে আটকে গেছি সেই পজিশনটাই আমাদের পিভটের sorted position. তাই 8 (৮) এর সাথে pivot 4 এর মধ্যে সোয়াপ করে দিব। পুরো অ্যারেটার আপডেটেড অবস্থা হল এখনঃ 2 3 1  4   6 7 5 8। এর মাধ্যমে কুইক সর্টের একটা iteration শেষ হল। ফলে প্রথম pivot-টা তার স্বস্থানে বসে গেছে। একই প্রসেস তুমি খাতায় করো বাম পাশের অ্যারে 2 3 1 এবং 6 7 5 8 এর জন্য। এগুলোকেও ভাংতে থাকো যতক্ষন ভাঙ্গা যায়। এক সময় দেখবে অ্যারেটা সর্টেড হয়ে গিয়েছে।

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

void quickSort(int left, int right) {

   if(right-left <= 0)
      return;
   else {
      int pivot = arr[right];
      int partitionPoint = partitionFunction(left, right, pivot);
      
      quickSort(left,partitionPoint-1);
      quickSort(partitionPoint+1,right);
   }
}

এটা একটা রিকার্সিভ ফাংশন। তাই শুরুতেই base case চেক করা হয়েছে। আগেই বলেছি এই ফাংশনটা অ্যারেকে জাস্ট পার্টিশন করবে বা ভাগ করবে। কতক্ষণ ভাগাভাগির কাজ চলতে থাকবে? উপরের উদাহরণের কথা চিন্তা কর। অ্যারেগুলোকে ভাংতে ভাংরে যখন কোন অ্যারের সাইজ হবে ১, অর্থাৎ কোন অ্যারেতে মাত্র একটা ইলিমেন্ট থাকবে তখন আমরা অ্যারেকে আর পার্টিশন করব না। শুরুতে আলোচনা করা উদাহরণে অ্যারের শুরুর ইনডেক্স ছিল 0 (left) আর শেষের ইন্ডেক্স ছিল 7 (right). এই দুইটা ভ্যালু দিয়েই quickSort() ফাংশন প্রথমে কল করা হয়। এই ফাংশন কলের সময় বেজ কেসে চেক হয়েছিল if(right-left < = 0) কিন্তু তা সত্য হয় নি। কখন এটা মিথ্যা হবে? যখন কোন একটা অ্যারের শুরুর ইন্ডেক্স আর শেষ ইন্ডেক্স একই হবে তখন (শুরু আর শেষ ইন্ডেক্স একই হওয়ার মানে অ্যারেতে একটা মান থাকা। সেক্ষেত্রে right-left করা হলে ফলাফল আসে 0. তাই IF কনডিশনটি সত্য হয়)। আবার যখন এই ফাংশনকে এমন দুইটা ইন্ডেক্স দিয়ে কল করা হয় যেখানে left বড় আর right ছোট। তখন right-left এর ফলাফল আসে ঋণাত্মক সংখ্যা। এই দুইটা ঘটনাই বেজ কেসে চেক করা হয়েছে।

• রিকার্সিভ ফাংশনের ব্যাসিক আইডিয়া পাওয়া যাবে এখান থেকে

যদি বেজ কেস সত্য না হয় তাহলে ঐ অ্যারেটাকে আবারো দুই টুকরা করে ফেলতে হবে। তাই আমাদেরকে পার্টিশন পয়েন্টটা জানা লাগবে। অর্থাৎ pivot-কে কোন পজিশনে ঢুকিয়ে দিতে হবে সেটা জানা লাগবে। এটা জানার জন্য ৭ নাম্বার লাইনে partitionPoint=  partitionFunction(left, right, pivot); এই ফাংশন কল করা হয়েছে। পার্টিশন পয়েন্টের মান নিয়ে পরের দুই লাইনে অ্যারেটাকে দুই ভাগ করা হয়েছে।

এখন দেখবো partitionFunction কিভাবে পার্টিশন পয়েন্ট find out করে।

int partitionFunction(int left, int right, int pivot) {

   int leftPointer = left -1;
   int rightPointer = right;

   while(true) {

      while(arr[++leftPointer] < pivot) {
         //do nothing
      }

      while(rightPointer > 0 && arr[--rightPointer] > pivot) {
         //do nothing
      }

      if(leftPointer >= rightPointer)
         break;
      else
         swapFunction(leftPointer,rightPointer); //swaping between arr[leftPointer] and arr[rightPointer]
      
   }

   swapFunction(leftPointer,right);
   
   return leftPointer;
}

৬ থেকে ২১ নাম্বার লাইনের লুপটা একটা ইটারেশনের জন্য কাজ করে। এর ভিতরে আরো দুইটা লুপ রয়েছে। ৮ নাম্বার লাইনের লুপের কাজ হচ্ছে যতক্ষণ ছোট সংখ্যা পাওয়া যাবে ততক্ষণ বাম থেকে ডানে আসতে থাকবে। ১২ নাম্বার লাইনের লুপের কাজ হচ্ছে ডান থেকে বামের দিকে যেতে থাকবে। এভাবে বাম থেকে ডান ও ডান থেকে বামে যাওয়ার কাজ শেষ হলে চেক করা হবে কোনো একটা ভ্যালুতে গিয়ে মানটা ঠেকেছে কিনা। যদি একটা নির্দিষ্ট মানে গিয়েই ঠেকে তাহলে লুপটা ব্রেক করবে। কিন্তু যদি একটা ভ্যালুকেই দুই দিক থেকে পয়েন্ট না করা হয় তখন ভ্যালু দুটি নিজেদের মধ্যে সোয়াপ করবে।

এই লুপের কাজটা শেষ হয়ে গেলে অ্যারেটার প্রথম ভাগে সবগুলোই হবে পিভটের চেয়ে ছোট সংখ্যা আর দ্বিতীয় ভাগের সবগুলো সংখ্যা হবে পিভটের চেয়ে বড়। এই অবস্থায় আমাদের কী করণীয় থাকে? এই অবস্থায় আমরা প্রথম অ্যারের পরেই কিন্তু পিভটটাকে ঢুকিয়ে দেই। সেই কাজটাই করা হয়েছে ২৩ নাম্বার লাইনে। right আর rightPoint কিন্তু দুইটা আলাদা ভেরিয়েবল। rightPiont এর মাধ্যমে ডান থেকে বামে যাওয়া নিয়ন্ত্রণ করা হচ্ছে। কিন্তু right ভেরিয়েবলটা হচ্ছে (যেই অ্যারের জন্য একে কল করা হয়েছে তার) সর্বশেষ ভ্যালুর ইন্ডেক্স নাম্বার। আর সর্বশেষ ভ্যালুটাই যেহেতু পিভট হিসেবে কাজ করছে তাই leftPointer বা বাম পাশের অ্যারের সর্বশেষ ইন্ডেক্সের ভ্যালুর সাথে পিভটের ভ্যালুকে swap করা হয়েছে। এরপর পিভটকে যেই ইন্ডেক্সে ঢুকানো হল সেটাকে পাঠিয়ে দেয়া হচ্ছে quickSort() এর কাছে, যেন সে এই পার্টিশন পয়েন্ট দিয়ে আবারো ঐ অ্যারেকে পার্টিশন করতে পারে।

সোয়াপ ফাংশনটা হচ্ছেঃ

void swapFunction(int leftIndex, int rightIndex) {

   int temp = arr[leftIndex];
   arr[leftIndex] = arr[rightIndex];
   arr[rightIndex] = temp;

}

এই ফাংশনে প্যারামিটার হিসাবে অ্যারের দুইটা ইনডেক্স এর মান পাঠানো হচ্ছে। সে অ্যারের এই দুইটা ইনডেক্সে থাকা মান দুইটিকে সোয়াপ করে দিবে।

এই ছিল আমাদের কুইক সর্ট। কোথাও বুঝতে কোন সমস্যা হয়েছে? আগে কুইক সর্ট পড়ে বুঝো নাই আজকে বুঝেছ এমন হলে কমেন্ট করো। আগে বুঝতা না বা আজকেই প্রথম পড়লা কুইক সর্ট, কিন্তু এই লেখা পড়েও বুঝো নাই তাহলেও কমেন্ট করো। কোথায় বুঝতে পারো নাই সেটা জানালে আরো সহজ করে কিভাবে লিখা যায় সেটা নিয়ে চিন্তা করতে পারবো। কোথাও কোন ভুল পরীলক্ষিত হলেও কমেন্ট করবেন প্লিজ…

পুরো কোডটি একসাথে পাওয়া যাবে গিটহাব রিপোজিটরিতে।

সবগুলো সর্টের ভিজুয়ালাইজেশন দেখা যাবে এখান থেকে।