দ্রুত বাছাই হল একটি সাজানোর অ্যালগরিদম যা ডিভাইড অ্যান্ড কনক্যুয়ার পদ্ধতি ব্যবহার করে৷ এটি একটি পিভট উপাদান নেয় এবং এটিকে সঠিক অবস্থানে রাখে। তারপর পিভট এলিমেন্টের বাম এবং ডানদিকের অ্যারে আবার Quick Sort ব্যবহার করে সাজানো হয়। পুরো অ্যারে সাজানো না হওয়া পর্যন্ত এটি করা হয়।
একটি প্রোগ্রাম যা C# তে পুনরাবৃত্তি ব্যবহার করে দ্রুত সাজানোর প্রদর্শন করে তা নিম্নরূপ দেওয়া হল -
উদাহরণ
using System;
namespace QuickSortDemo {
class Example {
static public int Partition(int[] arr, int left, int right) {
int pivot;
pivot = arr[left];
while (true) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left < right) {
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
} else {
return right;
}
}
}
static public void quickSort(int[] arr, int left, int right) {
int pivot;
if (left < right) {
pivot = Partition(arr, left, right);
if (pivot > 1) {
quickSort(arr, left, pivot - 1);
}
if (pivot + 1 < right) {
quickSort(arr, pivot + 1, right);
}
}
}
static void Main(string[] args) {
int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
int n = 10, i;
Console.WriteLine("Quick Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
quickSort(arr, 0, 9);
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
} আউটপুট
উপরের প্রোগ্রামের আউটপুট নিম্নরূপ।
Quick Sort Initial array is: 67 12 95 56 85 1 100 23 60 9 Sorted Array is: 1 9 12 23 56 60 67 85 95 100
এখন আসুন উপরের প্রোগ্রামটি বুঝতে পারি।
main() ফাংশনে, প্রথমে প্রাথমিক অ্যারে প্রদর্শিত হয়। তারপর, অ্যারেতে দ্রুত সাজানোর জন্য quickSort() ফাংশনটিকে বলা হয়। এর জন্য কোড স্নিপেট নিম্নরূপ দেওয়া হয়েছে -
int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
int n = 10, i;
Console.WriteLine("Quick Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
quickSort(arr, 0, 9); QuickSort() ফাংশনে, Partition() ফাংশন কল করে একটি পিভট উপাদান নির্বাচন করা হয়। তারপর quickSort() কে আবার আর্গুমেন্ট সহ কল করা হয় যা পিভটের মানের উপর নির্ভর করে। এর জন্য কোড স্নিপেট নিম্নরূপ দেওয়া হয়েছে -
if (left < right) {
pivot = Partition(arr, left, right);
if (pivot > 1) {
quickSort(arr, left, pivot - 1);
}
if (pivot + 1 < right) {
quickSort(arr, pivot + 1, right);
}
} Partition() ফাংশনে, প্রদত্ত অ্যারের সবচেয়ে বাঁদিকের উপাদান হিসেবে পিভট উপাদান নির্বাচন করা হয় এবং তারপর এটি অ্যারের সঠিক অবস্থানে সেট করা হয়। কোড স্নিপেট যা এর জন্য সমস্ত পদক্ষেপগুলি প্রদর্শন করে তা নিম্নরূপ দেওয়া হল৷
৷int pivot;
pivot = arr[left];
while (true) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left < right) {
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
} else {
return right;
}
} 