নির্বাচন বাছাই

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

নির্বাচন সাজানোর কৌশলের জটিলতা

• সময়ের জটিলতা:O(n^2)
• স্পেস জটিলতা:O(1)

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

Input:
The unsorted list: 5 9 7 23 78 20
Output:
Array before Sorting: 5 9 7 23 78 20
Array after Sorting: 5 7 9 20 23 78

অ্যালগরিদম

selectionSort(array, size)

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

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

Begin
   for i := 0 to size-2 do //find minimum from ith location to size
      iMin := i;
      for j:= i+1 to size – 1 do
         if array[j] < array[iMin] then
            iMin := j
      done
      swap array[i] with array[iMin].
   done
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;
}

void selectionSort(int *array, int size) {
   int i, j, imin;

   for(i = 0; i<size-1; i++) {
      imin = i;//get index of minimum data
      for(j = i+1; j<size; j++)
         if(array[j] < array[imin])
            imin = j;
      //placing in correct position
      swap(array[i], array[imin]);
   }
}

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);
   selectionSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

আউটপুট

Enter the number of elements: 6
Enter elements:
5 9 7 23 78 20      
Array before Sorting: 5 9 7 23 78 20
Array after Sorting: 5 7 9 20 23 78