Write a C++ program to sort the given data using Selection Sort.
Selection sort in C++ is a simple sorting algorithm that repeatedly finds the minimum element from the unsorted portion of an array and places it at the beginning, resulting in a sorted array.
Here’s the pseudo code for the selection sort algorithm:
procedure selectionSort(arr: array of elements) n = length(arr) for i = 0 to n-2 minIndex = i for j = i+1 to n-1 if arr[j] < arr[minIndex] minIndex = j swap arr[i] and arr[minIndex] end for end procedure
In the above pseudo code, arr represents the array to be sorted. The selectionSort procedure iterates through the array, finding the index of the minimum element in the unsorted portion (minIndex). It then swaps the current element with the minimum element. This process is repeated until the entire array is sorted.
1. Starting from the beginning pick one number.
2. Compare it with others one by one.
3. replace if the other number is lesser than this one.
4. Display the result.
5. Exit.
Initially, the array is [998, 451, 2, 35, 1206].
In each iteration:
Find the minimum element in the unsorted portion and swap it with the first unsorted element.
Repeat until the entire array is sorted.
After the iterations:
- First: [2, 451, 998, 35, 1206]
- Second: [2, 35, 998, 451, 1206]
- Third: [2, 35, 998, 451, 1206]
- Fourth: [2, 35, 998, 1206, 451]
- Fifth: [2, 35, 451, 998, 1206]
The array is now sorted in ascending order: [2, 35, 451, 998, 1206].
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.
/* * Implementation of Selection Sort */ #include <iostream> using namespace std; // Sort arr[] of size n using Selection Sort. void SelectionSort (int arr[], int n) { int i, j; for (i = 0; i < n; ++i) { for (j = i+1; j < n; ++j) { // Comparing consecutive data and switching values if value at i > j. if (arr[i] > arr[j]) { arr[i] = arr[i]+arr[j]; arr[j] = arr[i]-arr[j]; arr[i] = arr[i]-arr[j]; } } // Value at i will be minimum of all the values above this index. } } int main() { int n, i; cout<<"\nEnter the number of data element to be sorted: "; cin>>n; int arr[n]; for(i = 0; i < n; i++) { cout<<"Enter element "<<i+1<<": "; cin>>arr[i]; } SelectionSort(arr, n); // Display the sorted data. cout<<"\nSorted Data "; for (i = 0; i < n; i++) cout<<"->"<<arr[i]; return 0; }
1. Take input of data.
2. Call SelectionSort() function with ‘arr’ the array of data and ‘n’ the number of values, in the argument list.
3. Implement Sorting algorithm using nested for loop.
4. The first loop will run on ‘i’ from 0 to n-1.
5. The second loop will run on ‘j’ from i+1 to n-1.
6. Compare value at i with value at j.
7. Switch the values if arr[j+1] < arr[j].
8. Return to main and display the result.
9. Exit.
Time Complexity: O(n2)
The time complexity of the Selection Sort algorithm is O(n2) in the worst and average case.
Space Complexity: O(1)
The space complexity is O(1) since it sorts the array in-place without requiring additional memory allocation.
Testcase 1: (Average Case)
Enter the number of data element to be sorted: 5 Enter element 1: 998 Enter element 2: 451 Enter element 3: 2 Enter element 4: 35 Enter element 5: 1206 Sorted Data ->2->35->451->998->1206
Testcase 2: (Best Case)
Enter the number of data element to be sorted: 5 Enter element 1: 2 Enter element 2: 332 Enter element 3: 456 Enter element 4: 1024 Enter element 5: 16565 Sorted Data ->2->332->456->1024->16565
Testcase 3: (Worst Case)
Enter the number of data element to be sorted: 5 Enter element 1: 99845 Enter element 2: 564 Enter element 3: 332 Enter element 4: 86 Enter element 5: 1 Sorted Data ->1->86->332->564->99845
To practice programs on every topic in C++, please visit “Programming Examples in C++”, “Data Structures in C++” and “Algorithms in C++”.
If you find any mistake above, kindly email to [email protected]- Practice Computer Science MCQs
- Check Programming Books
- Apply for Computer Science Internship
- Check C++ Books
- Check Computer Science Books