Selection Sort

Selection Sort is a simple sorting algorithm that repeatedly selects the smallest (or largest, depending on the desired order) element from the unsorted part of the array and moves it to the beginning of the sorted part. Here's a detailed explanation of the Selection Sort algorithm along with an example:

Algorithm: Selection Sort

1.Initialization: Start with the first element as the minimum (assuming it's the smallest).

2.Find the Minimum: Scan the unsorted part of the array to find the minimum element.

Compare the current element with the minimum found so far.

If a smaller element is found, update the minimum.

3.Swap: Once you've found the minimum element in the unsorted part, swap it with the first element in the unsorted part.

4.Repeat: Repeat steps 2 and 3 for the remaining unsorted part of the array, excluding the element that was just swapped into the sorted part.

5.Continue: Keep repeating steps 2 to 4 until the entire array is sorted. The sorted part of the array grows with each iteration, while the unsorted part shrinks.

6.Termination: When the unsorted part is empty, the array is sorted.

Example:

Let's illustrate the Selection Sort algorithm with a simple example using a list of numbers in ascending order:

Original List: [64, 25, 12, 22, 11]

Step 1: The first element (64) is assumed to be the minimum.

Step 2: The algorithm scans the unsorted part and finds that 11 is smaller than 64, so 11 becomes the new minimum.

Step 3: Swap the first element (64) with the minimum (11):

Updated List: [11, 25, 12, 22, 64]

Step 4: Repeat the process for the remaining unsorted part:

Minimum of [25, 12, 22, 64] is 12. Swap 25 and 12. Updated List: [11, 12, 25, 22, 64]

Minimum of [25, 22, 64] is 22. Swap 25 and 22. Updated List: [11, 12, 22, 25, 64]

Step 5: Repeat the process until the entire array is sorted.

Minimum of [25, 64] is 25. Swap 25 and 25 (no change). Updated List: [11, 12, 22, 25, 64]

Minimum of [64] is 64. Swap 64 and 64 (no change). Updated List: [11, 12, 22, 25, 64]

Step 6: The unsorted part is now empty, and the array is sorted.

Final Sorted List: [11, 12, 22, 25, 64]

Selection Sort works by finding the minimum element in each pass and moving it to its correct position in the sorted part of the array. This process continues until the entire array is sorted in ascending order. However, note that Selection Sort is not the most efficient sorting algorithm for large datasets but is useful for educational purposes due to its simplicity.

Pseudo code

procedure selectionSort(arr):

    n = length(arr)

    

    for i from 0 to n-1:

        # Assume the current element is the minimum

        min_index = i

        

        # Find the minimum element in the unsorted part

        for j from i+1 to n-1:

            if arr[j] < arr[min_index]:

                min_index = j

        

        # Swap the minimum element with the first element in the unsorted part

        swap(arr[i], arr[min_index])

In this pseudocode:

arr is the input array to be sorted.

n represents the length of the array.

The outer loop iterates through the array from the first element to the second-to-last element.

In each iteration of the outer loop:

• We assume the current element (arr[i]) is the minimum (min_index).
• The inner loop scans the unsorted part of the array to find the index of the minimum element.
• If a smaller element is found, we update min_index to the index of that element.
• After scanning the unsorted part, we swap the minimum element (arr[min_index]) with the first element in the unsorted part (arr[i]).

This pseudocode represents the core steps of the Selection Sort algorithm, which repeats until the entire array is sorted in ascending order.

Let's analyze the time and space complexity of the Selection Sort algorithm:

Time Complexity:

Selection Sort has a time complexity of O(n^2) in the worst, average, and best cases. This is because it contains nested loops.

In the outer loop, you perform n iterations, where n is the number of elements in the array.

In the inner loop, for each iteration of the outer loop, you perform (n - i) iterations, where i is the current iteration of the outer loop.

The total number of comparisons and swaps is approximately (n^2)/2, which is still considered quadratic time complexity.

Space Complexity:

Selection Sort is an in-place sorting algorithm, which means it doesn't require additional memory allocation for temporary storage. It sorts the array in place, modifying the original array.

The space complexity of Selection Sort is O(1), which means it uses a constant amount of extra memory, regardless of the size of the input array.

The only additional memory used is for a few variables (e.g., min_index and temp) to keep track of indices and temporary values, and this memory usage remains constant regardless of the array size.

In summary, Selection Sort's time complexity is O(n^2) in all cases, and its space complexity is O(1). While it's a simple sorting algorithm to understand and implement, it's not the most efficient choice for sorting large datasets due to its quadratic time complexity. For larger datasets, more efficient algorithms like Quick Sort or Merge Sort are generally preferred.

C Program- Selection Sort

/*******************************************************************************/

#include<stdio.h>

void selectionsort(int a[],int n)

{

int i,j,temp,min_index;

for(i=0;i<n-1;i++)  // finding smallest element and placing in position

    { min_index=i;

        for(j=i+1;j<n;j++)

        {

            if(a[j]<a[min_index])

            {

            min_index=j;

            }

        }

        if(min_index!=i) { temp=a[i];a[i]=a[min_index];a[min_index]=temp;}

 }

}

int main(){

int size,i;

printf("Enter size of the array: ");

scanf("%d",&size);

int a[size];

printf("Enter %d elements: ",size);

for(i=0;i<size;i++)

scanf("%d",&a[i]);

selectionsort(a,size);

printf("Sorted elements: ");

for(i=0;i<size;i++)

printf(" %d",a[i]);

return 0;

}