মার্জ সর্টের মত কুইক সর্টও ডিভাইড এবং কনকার কৌশল ব্যবহার করে কোন লিস্টকে সর্ট করে। কুইক সর্ট নিচের মত করে কাজ করেঃ
- কুইক সর্টে কোন লিস্টকে সাব লিস্টে ভাগ করা হয়। এই ভাগ করার জন্য লিস্ট থেকেই একটা ইলিমেন্ট নেওয়া হয় পিভেট (pivot) ইলিমেন্ট হিসেবে। এই পিভেট ইলিমেন্ট এমন ভাবে লিস্টের মাঝে রাখা হয়, যেন লিস্টের এক পাশে থাকে পিভেট ইলিমেন্ট থেকে ছোট সংখ্যা গুলো, অন্য পাশে থাকে পিভেট থেকে বড় সংখ্যা গুলো।
- পিভেটের বাম এবং ডান পাশ থেকে একই ভাবে একটা করে পিভেট ইলিমেন্ট সিলেক্ট করা হয়। এভাবে পিভেটের বামের লিস্ট এবং পিভেটের ডানের লিস্টকে আবারো ভাগ করা হয় যতক্ষণ না সাব-লিস্টে একটা করে ইলিমেন্ট থাকে।
- লিস্ট এটমিক স্টেট পৌঁছালে বা প্রতিটা লিস্টে একটা করে আইটেম থাকা মানে হচ্ছে ঐ লিস্ট গুলো আলাদা আলাদা ভাবে সর্টেড। এরপর লিস্ট গুলোকে একত্র করা হয়। তখন একটা সর্টেড লিস্ট পাওয়া যায়।
উপরের ধাপ গুলোকে যদি এবার একটা লিস্ট যেমন 7, 3, 9,4, 2, 5 ব্যবহার করে সর্ট করি, তাহলে সবার আগে আমাদের একটা পিভেট ইলিমেন্ট সিলেক্ট করতে হবে।
ধাপ ১ঃ পিভেট ইলিমেন্ট নির্বাচন
কুইক সর্টের অনেক গুলো ভ্যারিয়েশন রয়েছে যেখানে পিভেট ইলিমেন্ট একেক ভাবে নির্বাচন করা হয়। কমন দুইটা ভ্যারিয়েশন হচ্ছে লিস্টের সর্বশেষ আইটেমকে পিভেট হিসেবে সিলেক্ট করা। অথবা লিস্টের যে কোন পজিশন থেকে একটা আইটেম নিয়ে এরপর লিস্টের একেবারে শেষ আইটেমের সাথে পিভেট আইটেমের ইনডেক্স বা জায়গা বদল করা।
আমরা মিডেল থেকেই একটা আইটেম পিভেট হিসেবে সিলেক্ট করি। যেমন সিলেক্ট করলাম 4। এবার এই 4 কে লিস্টের শেষ ইনডেক্সের আইটেমের সাথে বদলি করি। তাহলে লিস্টি হবে এমনঃ
ধাপ ২ঃ লিস্টকে রিএরেঞ্জ করা
আমরা জেনেছি পিভেট ইলিমেন্ট নির্বাচন করার পর লিস্টকে এমন ভাবে সাজাতে হবে যেন পিভেটের বাম পাশে থাকে ছোট সংখ্যা গুলো, ডান পাশে থাকে পিভেট থেকে বড় সংখ্যা গুলো।
এর জন্য লিস্টের বাম পাশ থেকে পিভেট থেকে বড় একটা সংখ্যা নির্বাচন করা হয় এবং ডান পাশ থেকে পিভেট থেকে ছোট একটা ইলিমেন্ট নির্বাচন করা হয়। এরপর এই দুইটা আইটেমের স্থান বদল করা হয়।
এই জন্য আমরা দুইটা পয়েন্টারের সাহায্য নিতে পারি। lo & hi। বাম পাশের বড় সংখ্যাটা বের করার জন্য lo পয়েন্টার ব্যবহার করব। ডান পাশের ছোট সংখ্যাকে বের করার জন্য hi পয়েন্টার ব্যবহার করব।
লিস্টের সবার আগের ইলিমেন্টকে পয়েন্ট করব lo দিয়ে এবং লিস্টের শেষে পিভেট ব্যাতিত ইলিমেন্টকে পয়েন্ট করব hi দিয়ে।
আমাদের লক্ষ্য হচ্ছে বাম থেকে পিভেট থেকে বড় সংখ্যাটি খুঁজে বের করা। লিস্টের শুরুতেই রয়েছে 7। 7 যেহেতু পিভেট 4 থেকে বড়, এর মানে আমরা বাম দিক থেকে বড় সংখ্যাটি পেয়ে গেছি। ডান দিক থেকে খুঁজে বের করতে হবে পিভেট 4 থেকে ছোট সংখ্যা। ডান দিকে প্রথমেই রয়েছে 2। এটি পিভেট 4 থেকে ছোট। এবার এই দুইটা আইটেমের স্থান বদল করতে হবে।
বদল করার পর lo এর ইনডেক্স 1 বাড়াতে হবে। hi এর ইনডেক্স 1 কমাতে হবে।
এবারও আমাদের কাজ হচ্ছে বাম থেকে বড় সংখ্যা বের করা। যেহেতু 3 পিভেট 4 থেকে ছোট, তাই lo এর ইনডেক্স আরো 1 বাড়াতে হবে। এই মুহুর্তে lo এর ইনডেক্স পয়েন্ট করা রয়েছে 9 তে।
ডান পাশে রয়েছে 5, যা পিভেট 4 থেকে বড়। আমাদের লক্ষ্য হচ্ছে ডান দিক থেকে পিভেট 4 থেকে ছোট আইটেম বের করা। যেহেতু 5 পিভেট 4 থেকে বড়, তাই hi এর ইনডেক্স এক কমিয়ে নিব।
এখন আমরা দেখব lo এবং hi দুইটাই একই সংখ্যা পয়েন্ট করে রয়েছে। যেহেতু এদের মধ্যে বদল করার অপশন নেই। তাই এই আইটেমটি পিভেট আইটেমের সাথে স্থান বদল করে নিব। অর্থাৎ 9 এবং 4 এর স্থান বদল করে নিব।
এই মুহুর্তে এসে দেখব পিভেট আইটেম 4 থেকে ছোট সংখ্যা গুলো লিস্টের এক পাশে এবং বড় সংখ্যা গুলো আরেক পাশে রয়েছে। অর্থাৎ পিভেট আইটেমটি লিস্টটাকে দুইটা ভাগে ভাগ করে দিয়েছে। এবার ঐ দুইটা লিস্টে উপের ধাপ গুলো ফলো করে আবারও ভাগ করতে হবে। এভাবে একটা সময় আমরা একটা সর্টেড লিস্ট পেয়ে যাবো।
পাইথনে যদি উপরের নিয়মে কুইক সর্ট ইমপ্লিমেন্ট করি, তাহলে নিচের মত করে কোড লিখতে পারিঃ
# divide function
def partition(lst, lo, hi):
pivot = lst[hi]
# pointer for greater element
i = (lo - 1)
for j in range(lo, hi):
# if current item is smaller
if lst[j] <= pivot:
i = i + 1
# swapping item of i & j index
lst[i], lst[j] = lst[j], lst[i]
# swap the pivot item
lst[i + 1], lst[hi] = lst[hi], lst[i + 1]
# return partition position
return i + 1
# quick sort
def quick_sort(lst, low, high):
if low < high:
pivot = partition(lst, low, high)
# sort the sub lists
quick_sort(lst, low, pivot - 1)
quick_sort(lst, pivot + 1, high)
num = [7, 3, 9, 4, 2, 5]
quick_sort(num, 0, len(num) - 1)
print(num)
প্রোগ্রামটি সহজে বোঝার সুবিদার্থে লিস্টের শেষ আইটেমকে পিভেট হিসেবে সেট করেছি।
পাইথনে আরো সহজেই কুইক সর্ট ইমপ্লিমেন্ট করা যায়। যেমন পিভেট আইটেম সিলেক্ট করার পর যেহেতু এর এক পাশে থাকবে এর থেকে ছোট ইলিমেন্ট গুলো, অন্য পাশে থাকবে এর থেকে বড় ইলিমেন্ট গুলো আমরা আরো সহজ ভাবে দুইটা লিস্ট ব্যবহার করে নিচের মত করে কুইক সর্ট ইমপ্লিমেন্ট করতে পারিঃ
import random
def quick_sort(lst):
# base case
if len(lst) <= 1:
return lst
# randomly select pivot
pivot = random.choice(lst)
lst.remove(pivot)
l_list = []
r_list = []
for item in lst:
if item <= pivot:
l_list.append(item)
else:
r_list.append(item)
# recursively call quick sort
return quick_sort(l_list) + [pivot] + quick_sort(r_list)
sort_list = [7, 3, 9, 4, 2, 5]
print(quick_sort(sort_list))
এই ভার্সনটা আসলে সহজেই বুঝা যায়। যেটা সত্যিকারের কুইক সর্ট 😀