সর্টিং হলো এলিমেন্টগুলোকে উন্নতিমুখী (অথবা) অবরোহী ক্রমে সাজানোর প্রক্রিয়া।
সর্টিং এর প্রকার
C ভাষা পাঁচটি সর্টিং টেকনিক প্রদান করে:
- বাবল সোর্ট (অথবা) এক্সচেঞ্জ সোর্ট
- সিলেকশন সোর্ট
- ইনসার্শন সোর্ট (অথবা) লিনিয়ার সোর্ট
- কুইক সোর্ট (অথবা) পার্টিশান এক্সচেঞ্জ সোর্ট
- মার্জ সোর্ট (অথবা) এক্সটার্নাল সোর্ট
কুইক সোর্ট (Quick Sort)
এটি একটি ডিভাইড এন্ড কঙ্কর অ্যালগরिदম।
- স্টেপ ১ - অ্যারে থেকে একটি এলিমেন্ট বাছাই করুন, এটিকে পিভট এলিমেন্ট বলুন।
- স্টেপ ২ - অনসর্টেড অ্যারে এলিমেন্টকে দুটি অ্যারেতে ভাগ করুন।
- স্টেপ ৩ - যদি মান পিভট এলিমেন্টের চেয়ে কম হয় তবে প্রথম সাব-অ্যারেতে আসবে, বাকি এলিমেন্ট যেগুলোর মান পিভটের চেয়ে বেশি সেগুলো দ্বিতীয় সাব-অ্যারেতে আসবে।
নিচের উদাহরণটি বিবেচনা করুন, যেখানে
- P হলো পিভট এলিমেন্ট।
- L হলো লেফট পয়েন্টার।
- R হলো রাইট পয়েন্টার।
এলিমেন্টগুলো হলো ৬, ৩, ৭, ২, ৪, ৫।
এখন,
- পিভট ফিক্সড পজিশনে আছে।
- সব বাম এলিমেন্ট কম।
- ডান এলিমেন্টগুলো পিভটের চেয়ে বেশি।
- এখন, অ্যারেকে ২টি সাব-অ্যারেতে ভাগ করুন: বাম অংশ এবং ডান অংশ।
- বাম পার্টিশনে কুইক সোর্ট প্রয়োগ করুন।
এখন,
- পিভট ফিক্সড পজিশনে আছে।
- সব বাম এলিমেন্ট কম এবং সর্টেড।
- ডান এলিমেন্টগুলো বেশি এবং সর্টেড অর্ডারে।
- ফাইনাল সর্টেড লিস্ট দুটি সাব-অ্যারে কম্বাইন করলে: ২, ৩, ৪, ৫, ৬, ৭
উদাহরণ
কুইক সোর্ট টেকনিক ব্যবহার করে এলিমেন্টগুলো সর্ট করার C প্রোগ্রাম:
#include<stdio.h> void quicksort(int number[25],int first,int last){ int i, j, pivot, temp; if(first<last){ pivot=first; i=first; j=last; while(i<j){ while(number[i]<=number[pivot]&&i<last) i++; while(number[j]>number[pivot]) j--; if(i<j){ temp=number[i]; number[i]=number[j]; number[j]=temp; } } temp=number[pivot]; number[pivot]=number[j]; number[j]=temp; quicksort(number,first,j-1); quicksort(number,j+1,last); } } int main(){ int i, count, number[25]; printf("How many elements are u going to enter?: "); scanf("%d",&count); printf("Enter %d elements: ", count); for(i=0;i<count;i++) scanf("%d",&number[i]); quicksort(number,0,count-1); printf("Order of Sorted elements: "); for(i=0;i<count;i++) printf(" %d",number[i]); return 0; }
আউটপুট
উপরোক্ত প্রোগ্রামটি এক্সিকিউট করলে নিচের আউটপুটটি দেখায়:
How many elements are u going to enter?: 10 Enter 10 elements: 2 3 5 7 1 9 3 8 0 4 Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9
