## Data Structure Tutorial Index

Selection Sort is a fundamental sorting algorithm in computer science that arranges an array by repeatedly finding the minimum element from the unsorted section and placing it at the beginning. This tutorial aims to clarify the algorithm's working principle and provide practical code examples for implementing it.

## Understanding Selection Sort Algorithm

Selection Sort is an in-place comparison-driven sorting algorithm that divides an input list into a sorted sublist and an unsorted sublist. At each iteration, it selects the smallest (or largest) element from the unsorted portion and swaps it with the first element of the unsorted section. This process does not involve comparing the selected smallest (or largest) element with those in the sorted section; instead, comparisons are made only within the unsorted part to identify the minimum (or maximum) element.

## How Selection Sort Works

Consider you have an unsorted array: `[29, 10, 37, 14, 13]`, and you want to sort it in ascending order utilizing the Selection Sort algorithm. Unlike Bubble Sort, which iterates through the list to swap adjacent elements, Selection Sort improves efficiency by minimizing swaps.

Pass Operation Resulting Array
1 Find minimum (`10`) and swap with the first element (`29`) `[10, 29, 37, 14, 13]`
2 Find minimum (`13`) in the unsorted section and swap it with the first unsorted element (`29`) `[10, 13, 37, 14, 29]`
3 Find minimum (`14`) in the unsorted section and swap it with the first unsorted element (`37`) `[10, 13, 14, 37, 29]`
4 Find minimum (`29`) in the unsorted section and swap it with the first unsorted element (`37`) `[10, 13, 14, 29, 37]`

## Implementation Examples

### C++ Example

Implementing Selection Sort in C++ is straightforward. The following code snippet demonstrates this process:

Example:

``````#include <iostream>
using namespace std;

// Function to perform selection sort on an array
void selectionSort(int arr[], int n) {
// Loop through each element of the array except the last one
for (int i = 0; i < n-1; i++) {
// Assume the first unsorted element is the minimum
int minIndex = i;

// Compare this element with the rest of the unsorted portion of the array to find the true minimum
for (int j = i+1; j < n; j++) {
// If a smaller element is found, update minIndex with the new minimum element's index
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}

// Swap the found minimum element with the first unsorted element
swap(arr[i], arr[minIndex]);
}
}

int main() {
// Initialize array with unsorted elements
int arr[] = {29, 10, 37, 14, 13};
// Calculate number of elements in the array
int n = sizeof(arr)/sizeof(arr[0]);

// Call selectionSort function to sort the array
selectionSort(arr, n);

// Print the sorted array
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
``````

Output:

``Sorted array: 10 13 14 29 37``

Here is a C++ code snippet for implementing the Selection Sorting Algorithm by taking user input:

Example:

``````#include <iostream>
using namespace std;

// Function to perform selection sort on an array
void selectionSort(int arr[], int n) {
// Loop through each element of the array except the last one
for (int i = 0; i < n-1; i++) {
// Assume the first unsorted element is the minimum
int minIndex = i;

// Compare this element with the rest of the unsorted portion of the array to find the true minimum
for (int j = i+1; j < n; j++) {
// If a smaller element is found, update minIndex with the new minimum element's index
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}

// Swap the found minimum element with the first unsorted element
swap(arr[i], arr[minIndex]);
}
}

int main() {
int arr[100], n;

// Input the number of elements
cout << "Enter the number of elements: ";
cin >> n;

// Input the elements
cout << "\nEnter " << n << " elements:\n";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}

// Sorting the array using Selection Sort
selectionSort(arr, n);

// Output the sorted array
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
``````

Output:

``````Enter the number of elements: 5

Enter 5 elements:
29
10
37
14
13

Sorted array: 10 13 14 29 37``````

### Python Example

In Python, the Selection Sort algorithm can be implemented as follows:

Example:

``````def selectionSort(arr):
# Traverse through all array elements
for i in range(len(arr)):
# Find the minimum element in the remaining unsorted array
minIndex = i
for j in range(i+1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j

# Swap the found minimum element with the first element
arr[i], arr[minIndex] = arr[minIndex], arr[i]

# Example usage
arr = [29, 10, 37, 14, 13]
selectionSort(arr)
print("Sorted array is:", arr)
``````

Output:

``Sorted array is: [10, 13, 14, 29, 37]``

### Java Example

Here's the Java code for implementing the Selection Sort algorithm:

Example:

``````public class SelectionSort {
void selectionSort(int arr[]) {
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++) {
// Find the minimum element in unsorted array
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}

// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

public static void main(String args[]) {
SelectionSort ob = new SelectionSort();
int arr[] = {29, 10, 37, 14, 13};
ob.selectionSort(arr);
System.out.println("Sorted array is: ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
``````

Output:

``Sorted array is: 10 13 14 29 37``

## Time Complexity

The time complexity of the Selection Sort algorithm is `O(n^2)` in both the best-case and worst-case scenarios. Like Bubble Sort, this quadratic complexity means that the time it takes to sort a list of elements increases significantly with the square of the number of elements. This behavior makes the Selection Sort inefficient for sorting large datasets compared to more advanced sorting algorithms that offer better time complexity.

## Conclusion

Selection Sort is a simple yet effective sorting algorithm that is an excellent starting point for understanding how sorting works. Although it may not be the most efficient for large data sets, it's a great way to learn sorting algorithms because of its simplicity and clarity. This algorithm helps to understand fundamental concepts such as iteration and swapping, which are essential for many computer science algorithms.