দ্রুত বাছাই

কুইকসর্ট কৌশলটি তালিকাটিকে দুটি অংশে বিভক্ত করে করা হয়৷ প্রাথমিকভাবে, পার্টিশন অ্যালগরিদম দ্বারা একটি পিভট উপাদান নির্বাচন করা হয়। পিভটের বাম অংশটি পিভটের চেয়ে ছোট মান ধারণ করে এবং ডান অংশটি বড় মান ধারণ করে। পার্টিশন করার পরে, প্রতিটি পৃথক তালিকা একই পদ্ধতি ব্যবহার করে বিভাজন করা হয়।

কুইকসোর্ট টেকনিকের জটিলতা

• সময়ের জটিলতা:সেরা ক্ষেত্রে ও গড় ক্ষেত্রে O(n log n), সবচেয়ে খারাপ ক্ষেত্রে O(n^2)।
• স্পেস জটিলতা:O(log n)

ইনপুট এবং আউটপুট

Input:
The unsorted list: 90 45 22 11 22 50
Output:
Array before Sorting: 90 45 22 11 22 50
Array after Sorting: 11 22 22 45 50 90

অ্যালগরিদম

পার্টিশন (অ্যারে, লোয়ার, আপার)

ইনপুট: ডেটা সেট অ্যারে, নিম্ন সীমানা এবং উপরের সীমানা

আউটপুট: সঠিক অবস্থানে পিভট করুন

Begin
   pivot := array[lower]
   start := lower and end := upper
   while start < end do
      while array[start] <= pivot AND start < end do
         start := start +1
      done

      while array[end] > pivot do
         end := end – 1
      done
      if start < end then
         swap array[start] with array[end]
   done

   array[lower] := array[end]
   array[end] := pivot
   return end
End

দ্রুত সাজানো(অ্যারে, বাম, ডান

ইনপুট - ডেটার একটি অ্যারে, এবং অ্যারের নিম্ন এবং উপরের সীমা

আউটপুট - সাজানো অ্যারে

Begin
   if lower < right then
      q = partition(arraym left, right)
      quickSort(array, left, q-1)
      quickSort(array, q+1, right)
End

উদাহরণ

#include<iostream>
using namespace std;

void swapping(int &a, int &b) { //swap the content of a and b
   int temp;
   temp = a;
   a = b;
   b = temp;
}

void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}

int partition(int *array, int lower, int upper) {
   //Hoare partitioning technique to find correct location for pivot
   int pivot, start, end;
   pivot = array[lower];      //first element as pivot
   start = lower; end = upper;

   while(start < end) {
      while(array[start] <= pivot && start<end) {
         start++;      //start pointer moves to right
      }

      while(array[end] > pivot) {
         end--;      //end pointer moves to left
      }

      if(start < end) {
         swap(array[start], array[end]); //swap smaller and bigger element
      }
   }

   array[lower] = array[end];
   array[end] = pivot;
   return end;
}

void quickSort(int *array, int left, int right) {
   int q;

   if(left < right) {
      q = partition(array, left, right);
      quickSort(array, left, q-1);    //sort left sub-array
      quickSort(array, q+1, right);   //sort right sub-array
   }
}

int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n]; //create an array with given number of elements
   cout << "Enter elements:" << endl;

   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }

   cout << "Array before Sorting: ";
   display(arr, n);
   quickSort(arr, 0, n-1); //(n-1) for last index
   cout << "Array after Sorting: ";
   display(arr, n);
}

আউটপুট

Enter the number of elements: 6
Enter elements:
90 45 22 11 22 50
Array before Sorting: 90 45 22 11 22 50
Array after Sorting: 11 22 22 45 50 90