পাইথন কুইকসোর্ট (QuickSort) কোডিং: একটি পূর্ণাঙ্গ গাইড

একটি পাইথন কুইকসোর্ট একটি পিভট এলিমেন্ট সিলেক্ট করে এবং একটি অ্যারে-এর এলিমেন্টগুলোকে দুটি নতুন অ্যারে-এ ভাগ করে। পিভট থেকে বড় সংখ্যাগুলো এক অ্যারে-এ যায়; পিভট থেকে ছোট সংখ্যাগুলো অন্য অ্যারে-এ যায়। প্রতিটি অ্যারে সাজানো হয় এবং তারপর সব অ্যারে একত্রিত হয় একটি এ стаতে।

পাইথন কুইকসোর্ট কী?

প্রোগ্রামিং-এ তালিকা সাজানোর জন্য অনেক সাজানোর অ্যালগরিদম রয়েছে। পাইথন ইন্সারশন সোর্ট, বাবল সোর্ট, এবং আরও অনেক কিছু আছে। কুইকসোর্ট সবচেয়ে কমন সাজানোর টাইপগুলোর একটি।

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

পাইথন কুইকসোর্ট কী?

একটি পাইথন কুইকসোর্ট অ্যালগরিদম একটি অ্যারেকে সাব-অ্যারেগুলোতে ভাগ করে। এই অ্যালগরিদম এই সাব-অ্যারেগুলোকে রিকার্সিভলি কল করে লিস্টের প্রতিটি এলিমেন্ট সাজাতে। একটি সাব-অ্যারের কন্টেন্ট নির্ভর করে একটি পিভট এলিমেন্টের ওপর যা কোনো নতুন সাব-অ্যারেতে মুভ করা হয় না।

কুইকসোর্ট অ্যালগরিদম ডিভাইড-অ্যান্ড-কঙ্কর (divide-and-conquer) পদ্ধতি অনুসরণ করে। এর মানে হলো একটি লিস্ট সাজানোর টাস্ককে কিছু সাব-টাস্কে ভাগ করা হয়। সোর্টের শেষে, এই সাব-টাস্কগুলোর ফলাফল একসাথে আসে একটি সাজানো লিস্ট রিটার্ন করতে।

একটি কুইকসোর্টে, সাব-টাস্ক হলো প্রতিটি সাব-লিস্টের জন্য একটি পিভট সেট করা এবং পিভটের সাথে তাদের ভ্যালুর রিলেটিভ মানের উপর ভিত্তি করে এলিমেন্টগুলো অর্ডার করা।

পাইথন কুইকসোর্ট কখন ব্যবহার করা উচিত?

টাইম কমপ্লেক্সিটি যখন मैটার করে তখন কুইকসোর্ট উপকারী। কারণ কুইকসোর্ট অন্যান্য অ্যালগরিদম চেয়ে কম মেমরি স্পেস ব্যবহার করে, যা এটিকে একটি দক্ষতা বাড়ানোর সুযোগ দেয়।

আপনাকে কুইকসোর্ট শুধু তখন ব্যবহার করা উচিত যদি আপনি পাইথন রিকার্শনের সাথে পরিচিত হন। কারণ কুইকসোর্ট অ্যালগরিদম রিকার্সিভ ফাংশনগুলোর ওপর নির্ভর করে।

ছোট অ্যারেতে কুইকসোর্ট মার্জ সোর্ট চেয়ে বেশি দক্ষ। তবে, বড় ডেটা সেটের ক্ষেত্রে, ইন্সারশন সোর্ট বা মার্জ সোর্ট দ্রুতتر হতে পারে।

কুইকসোর্ট কীভাবে কাজ করে?

একটি কুইকসোর্ট একটি এলিমেন্ট পিক করে পিভট হিসেবে সার্ভ করতে। এটা লিস্টের যেকোনো এলিমেন্ট হতে পারে। এই টিউটোরিয়ালের জন্য, আমরা লিস্টের লাস্ট আইটেমটি বেছে নিচ্ছি (৩)।

একটি কুইকসোর্ট পিভটের ভ্যালুকে লিস্টের আইটেমগুলোর মধ্য দিয়ে লুপ করার সময় প্রতিটি নম্বরের সাথে তুলনা করে। যদি কোনো আইটেম পিভট নম্বরের চেয়ে বড় হয়, তবে আমরা নম্বরটিকে পিভটের পরে মুভ করি; অন্যথায়, আমরা নম্বরটিকে পিভটের আগে মুভ করি:

ভ্যালু ৩ আমাদের লিস্টে নিচে নামিয়ে এসেছে। ৩ থেকে ছোট সব আইটেমরা তার বামে যাবে; ৩ থেকে বড় সব ভ্যালুরা তার ডানে যাবে।

আমাদের পাইথন অ্যারে দুটি হ্যালফে ভাগ হয়েছে: পিভট থেকে বড় আইটেমরা এবং পিভট থেকে ছোট আইটেমরা।

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

এরপর, আমরা পিভট থেকে বড় সব ভ্যালুকে পিভটের ডানে মুভ করি। পিভট থেকে ছোট সব ভ্যালুকে পিভটের বামে মুভ করি।

এই প্রক্রিয়া আমাদের লিস্ট সাজানো পর্যন্ত চলতে থাকে:

আমাদের ফাইনাল অ্যারে এরকম দেখে:

পাইথন কুইকসোর্ট উদাহরণ

কুইকসортуর দুটি ফাংশন দরকার: একটি পার্টিশন ফাংশন এবং একটি কুইকসোর্ট ফাংশন।

চলুন পার্টিশন ফাংশন দিয়ে শুরু করি। এটি অ্যারেকে পিভট এলিমেন্টের ভ্যালু অনুযায়ী পার্টিশন বা প্রিপেয়ার করবে।

আমাদের পার্টিশন ফাংশন:

1. পিভট এলিমেন্ট সিলেক্ট করবে
2. পিভট থেকে বড় সব আইটেমকে পিভটের ডানে মুভ করবে
3. পিভট থেকে ছোট সব আইটেমকে পিভটের বামে মুভ করবে

পাইথন কুইকসোর্ট প্রোগ্রাম

চলুন এই অ্যালগরিদম ইমপ্লিমেন্ট করার একটি প্রোগ্রাম লিখি:

def prepare(numbers, low, high):
    pivot = numbers[high]
    item = low - 1
    for i in range(low, high):
        if numbers[i] <= pivot:
            item = item + 1
            (numbers[item], numbers[i]) = (numbers[i], numbers[item])
    (numbers[item + 1], numbers[high]) = (numbers[high], numbers[item + 1])
    return item + 1

প্রথমে, আমরা একটি পিভট এলিমেন্ট সিলেক্ট করি। এটি আমাদের লিস্টের হাইएস্ট নম্বরের সমান।

এরপর, আমরা একটি পাইথন for লুপ ব্যবহার করে লিস্টের সব আইটেমের মধ্য দিয়ে লুপ করি। যদি কোনো নম্বর পিভট থেকে ছোট বা সমান হয়, তবে সেটি পিভটের বামে মুভ করা হয়। অন্যথায়, সেটি পিভটের ডানে যায়।

আমাদের পাইথন ফাংশন নতুন হাই ভ্যালু রিটার্ন করে। নতুন হাই ভ্যালু হলো item + 1।

এরপর, আমাদের অ্যালগরিদম রান করতে হবে। এজন্য আমরা একটি আলাদা ফাংশন লিখব:

def quick_sort(numbers, low, high):
    if low < high:
        pivot = prepare(numbers, low, high)
        quick_sort(numbers, low, pivot - 1)
        quick_sort(numbers, pivot + 1, high)

এই ফাংশন চেক করে low-এর ভ্যালু কি high-এর ভ্যালুর চেয়ে কম। যদি হয়, তবে আমাদের সোর্ট চালু থাকতে পারে। অন্যথায়, আমাদের সোর্ট বন্ধ হয়। যদি আমাদের সোর্ট বন্ধ হয়, এর মানে আমরা লিস্টটি সাজিয়ে ফেলেছি।

এরপর, আমাদের ফাংশন prepare() মেথড কল করে। এটি পিভটের জন্য একটি পয়েন্টার আইডেন্টিফাই করে এবং আইটেমগুলোকে তাদের সঠিক জায়গায় মুভ করে।

আমাদের ফাংশন তারপর quick_sort() মেথড দুবার কল করে। প্রথমবার, আমরা পিভটের বামে থাকা এলিমেন্টগুলোর ওপর কুইকসোর্ট চালাই। দ্বিতীয়বার, আমরা পিভটের ডানে থাকা এলিমেন্টগুলোর ওপর কুইকসোর্ট চালাই। তাই, আমাদের ফাংশন রিকার্সিভ কারণ এটি নিজেই নিজেকে কল করে।

এটি তখন까지 চলে যতক্ষণ না লিস্টের সব আইটেম সাজানো হয়।

মেইন মেথড লিখা

চলুন একটি মেইন প্রোগ্রাম লিখি যা একটি লিস্ট ডিফাইন করে সাজানোর জন্য:

values = [8, 4, 5, 2, 1, 3]
total_values = len(values)
quick_sort(values, 0, total_values - 1)
print(values)

প্রথমে, আমরা সাজানোর জন্য একটি ভ্যালু লিস্ট স্পেসিফাই করি। আমরা পাইথন len() মেথড ব্যবহার করে আমাদের ভ্যালু লিস্টের দৈর্ঘ্য ক্যালকুলেট করি। এরপর, আমরা quick_sort() মেথড কল করি।

আমরা values পাস করি যেই নম্বরগুলো আমরা সাজাতে চাই। তারপর আমরা ০ পাস করি লো নম্বর হিসেবে। values-এর দৈর্ঘ্য মাইনাস ১ হলো হাই ভ্যালু যা আমরা স্পেসিফাই করি। হাই ভ্যালু হলো দৈর্ঘ্য মাইনাস ১ কারণ লিস্টের প্রথম আইটেমের ইনডেক্স নম্বর ০।

প্রোগ্রামটি রান করি:

[1, 2, 3, 4, 5, 8]

আমাদের কোড একটি সাজানো লিস্ট রিটার্ন করেছে! আমরা করলাম। নিজের পিঠে একটু ধাপ দিন। কুইকসোর্ট বুঝতে এবং ইমপ্লিমেন্ট করতে সহজ নয়।

কমপ্লেক্সিটি ওভারভিউ

গড়ে, এই অ্যালগরিদম O(n*log n)-এ পারফর্ম করে। এটা হয় যখন পিভট এলিমেন্ট না সবচেয়ে বড় বা ছোট এলিমেন্ট এবং না মিডল এলিমেন্টের কাছে।

কুইকসোর্টের ওয়ার্স্ট কেস কমপ্লেক্সিটি O(n²)। এটা ঘটে যখন পিভট হিসেবে সিলেক্ট করা এলিমেন্ট হয় সবচেয়ে বড় বা সবচেয়ে ছোট এলিমেন্ট। যদি এটা হয়, তবে পিভট এলিমেন্ট সবসময় একটি সাজানো অ্যারেতে শেষে থাকবে। এটা অনাবশ্যক সাব-অ্যারেগুলো তৈরি করবে।

এই অ্যালগরিদমের বেস্ট কেস কমপ্লেক্সিটি O(n*log n)। এটা হয় যখন পিভট এলিমেন্ট হয় মিডল এলিমেন্টের সমান বা তার কাছে।

অ্যালগরিদম কমপ্লেক্সিটি সম্পর্কে আরও জানতে, আমাদের Big O Notation গাইডটি চেক করুন।

উপসংহার

পাইথন কুইকসোর্ট রিকার্শন ব্যবহার করে একটি লিস্টকে ছোট ছোট লিস্টগুলোর ভাগ করে যা তারপর সাজানো হয়। প্রতিটি লিস্ট একটি পিভট এলিমেন্টের চারপাশে সাজানো হয়। পিভট থেকে বড় এলিমেন্টগুলো তার ডানে মুভ করা হয়; ছোট এলিমেন্টগুলো তার বামে মুভ করা হয়।

টপ পাইথন লার্নিং রিসোর্স, অনলাইন কোর্স, এবং বইয়ের জন্য আমাদের সমৃদ্ধ How to Learn Python গাইডটি পড়ুন।