Lecture 339:- Selection Sort

Selection Sort is a simple comparison-based sorting algorithm that repeatedly selects the minimum (or maximum) element from the unsorted part of the array and moves it to the beginning (or end) of the sorted part. It is an in-place sorting algorithm and has a worst-case and average-case time complexity of O(n^2).

Algorithm:

1. Start with the first element of the array and assume it as the minimum (or maximum).
2. Compare the current minimum (or maximum) with the next element in the unsorted part of the array.
3. If a smaller (or larger) element is found, update the minimum (or maximum) to the new element's index.
4. Repeat steps 2 and 3 until the end of the unsorted part of the array is reached.
5. Swap the minimum (or maximum) element with the first element of the unsorted part of the array.
6. Move the boundary between the sorted and unsorted parts of the array by incrementing (or decrementing) it.
7. Repeat steps 1 to 6 until the entire array is sorted.

Here's the C++ implementation of the Selection Sort algorithm:

cppCopy code

#include <iostream> #include <vector> using namespace std; void selectionSort(vector<int>& arr) {    int n = arr.size();    for (int i = 0; i < n - 1; i++) {        int minIdx = i;        // Find the minimum element in the unsorted part of the array        for (int j = i + 1; j < n; j++) {            if (arr[j] < arr[minIdx]) {                minIdx = j;            }        }        // Swap the minimum element with the first element of the unsorted part        swap(arr[i], arr[minIdx]);    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};    cout << "Original Array: ";    display(arr);    selectionSort(arr);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this implementation, the selectionSort function takes a vector of integers as input and sorts it using the Selection Sort algorithm. The outer loop runs for n-1 passes, and the inner loop finds the minimum element in the unsorted part of the array. The display function is used to print the elements of the array before and after sorting.

When you run this code, it will display the original array and then the sorted array after applying the Selection Sort algorithm.