লিনিয়ার-টাইম পার্টিশন করা

কুইকসর্টের মূল কাজটি হয়ে থাকে ভাগ করার ধাপটিতে কাজ করার সময়, যেটা একটি সাবঅ্যারে থেকে অঙ্কন করা পিভটের চারপাশ দিয়ে array[p..r] এর একটি পার্টিশন তৈরি করবে। যদিও আমরা সাবঅ্যারের যেকোন উপাদানকে পিভট হিসেবে নির্বাচিত করতে পারি, আমরা যদি সাব অ্যারের সঠিক উপাদানগুলো নির্বাচিত করতে পারি তাহলে পার্টিশন বাস্তবায়ন করা সহজ হবে এবং পিভট হিসেবে A[r] নির্বাচিত করা যেতে পারে।

একটি পিভট নির্বাচিত করার পরে, সাবঅ্যারের মধ্য দিয়ে যাবার মাধ্যমে এটাকে পার্টিশন করতে পারি, বামপাশ থেকে ডানপাশে, পিভটের সাথে প্রতিটি উপাদান তুলনা করতে হবে। সাবঅ্যারেতে দুইটিসূচক q এবং j আমাদের রাখতে হবে যেটা পরবর্তীতে চারটি শ্রেণিতে বিভক্ত করবে। চলকের নাম হিসেবে আমরা q ব্যবহার করছি কারণ ঐ ইন্ডেক্স ধীরে ধীরে পিভটের দিকে নির্দেশ করবে। আমরা এখানে j নামটি ব্যবহার করছি কারণ এটা সবচেয়ে সাধারণ ব্যবহার হওয়া গণনার চলক এবং চলকটি বাতিল করে দেওয়া হলে যখন আমাদের কাজ করা শেষ হয়ে যাবে।

প্রাথমিকভাবে, q এবং j সমান p। প্রতিটি ধাপে, আমরা A[j] তুলনা করতে পারি, U গ্রুপের সর্ববামে থাকা পিভটসহ উপাদানটি। যদি A[j] পিভটের থেকে বড় হয়ে থাকে তাহলে আমরা এখানে j বাস্তবায়ন করতে পারি, যাতে যে লাইনটি গ্রুপ G এবং U কে বিভক্ত করছে সেই লাইনটি একঘর ডানে সরে যাবে:

যদি A[j] পিভটের থেকে ছোট অথবা সমান হয়, তাহলে A[j] এর সাথে A[q] স্থানান্তর করব (গ্রুপ G এর সর্ববামে থাকা উপাদানটি), j এর মান বৃদ্ধি করব এবং q এর মান বৃদ্ধি করতে হবে। সুতরাং, গ্রুপ L এবং G আর গ্রুপ G এবং U কে যে লাইনটি বিভক্ত করছে সেই লাইনটিকে ডানদিকে একঘর সরে যাবে:

আমরা যখন একবার পিভটটি পেয়ে যাব, গ্রুপ U টি তখন খালি হয়ে যাবে। আমরা পিভটটি গ্রুপ G এ থাকা সর্ববামে থাকা উপাদানের সাথে স্থানান্তর করব: A[r] এর সাথে A[q] স্থানান্তর করা যাক। এই স্থানান্তরটি পিভটকে গ্রুপ L ও G এর মধ্যে রাখবে এবং যদি গ্রুপ L অথবা গ্রুপ G শূন্যও থাকে তাহলেও এটা সঠিক কাজটি করবে। (যদি গ্রুপ L শূন্য হয়, তাহলে q তার মূল মান p থেকে কখনই বৃদ্ধি পাবে না এবং তাই পিভট সাবঅ্যারেতে তার সর্ববামের অবস্থানে চলে যাবে। যদি গ্রুপ G শূন্য হয়, তাহলে q প্রতিবার বৃদ্ধি পেয়ে j এর স্থানে যাবে এবং একবার যখন j পিভটের ইনডেক্স r এ পৌঁছাবে, তখন q সমান r হবে এবং এই স্থানান্তরটি পিভটটিকে সাবঅ্যারের সর্বডানের স্থানে নিয়ে আসবে।) যে পার্টিশন ফাংশনটি এই ধারণাটি বাস্তবায়িত করছে সেটিও ইনডেক্স q এ ফিরে আসবে যেখানে কাজ শেষ করার পরে ফাংশনটি পিভটটি রেখেছিল, যাতে এই কুইকসর্ট ফাংশনটি, যেটা এটাকে কল করছে, জানতে পারে যে পার্টিশন কোথায় আছে। সাবঅ্যারেটি পার্টিশন করবার জন্য ধাপগুলো এখানে দেওয়া হল [12, 7, 14, 9, 10, 11] in array[4..9]:

$n$‍ সংখ্যক উপাদান নিয়ে একটি সাবঅ্যারে পার্টিশন করার জন্য $\mathrm{\Theta }(n)$‍ সময়ের প্রয়োজন হয়। প্রতিটি উপাদান A[j], একবার করে পিভটের সাথে তুলনা করা হয়। A[j], A[q] এর সাথে স্থানান্তরিত হতেও পারে আবার নাও হতে পারে, q এর মান বাড়তেও পারে আবার নাও বাড়তে পারে এবং j এর মান সবসময়ের জন্য বৃদ্ধি পাবে। সাবঅ্যারের প্রতিটি উপাদানের জন্য মোট সম্পাদিত হওয়া লাইনের সংখ্যা হল একটি ধ্রুবক। যেহেতু সাবঅ্যারেতে $n$‍ সংখ্যক উপাদান আছে, তাই পার্টিশন করার সময়টি হল $\mathrm{\Theta }(n)$‍: লিনিয়ার-টাইম পার্টিশন করা।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।