{"id":34220,"date":"2024-11-01T09:25:40","date_gmt":"2024-11-01T09:25:40","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34220"},"modified":"2024-11-01T10:58:07","modified_gmt":"2024-11-01T10:58:07","slug":"c-coding-test-course-selection-sort-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34220\/","title":{"rendered":"C++ Coding Test Course, Selection Sort"},"content":{"rendered":"<\/p>\n
Problem Description<\/h2>\n
Write a function to sort a given integer array in ascending order. The sorting algorithm to be used is Selection Sort.<\/p>\n
Input<\/h3>\n
\n
The first line contains an integer N<\/code>. (1 \u2264 N \u2264 1000)<\/li>\n
The second line contains N<\/code> integers. (Integer A[i]<\/code> is -10000 \u2264 A[i]<\/code> \u2264 10000)<\/li>\n<\/ul>\n
Output<\/h3>\n
Output the sorted array in ascending order in a single line, separated by spaces.<\/p>\n
Concept Review of Selection Sort<\/h2>\n
The selection sort is one of the simplest sorting algorithms. It works by finding the smallest value in the given list and swapping it with the value at the front. This process is repeated until the list is sorted.<\/p>\n
Process of Selection Sort<\/h3>\n\n
Find the smallest value in the current list.<\/li>\n
Swap that value with the value at the current position.<\/li>\n
Repeat steps 1 and 2 to sort the list.<\/li>\n<\/ol>\n
Problem-Solving Process<\/h2>\n
1. Understanding for Problem Solving<\/h3>\n
To solve the problem, we start by finding the smallest value in the array and placing it at the front, then we find the next smallest value and place it in the second position. This process is repeated for the length of the array, and we need to search the remainder of the array to find the smallest value at each step.<\/p>\n
2. Implementation of Selection Sort Algorithm<\/h3>\n
Now let’s implement the selection sort algorithm in C++. First, we will take the input for the array, then apply the selection sort algorithm to sort it, and finally print the result.<\/p>\n
\n#include <iostream>\nusing namespace std;\n\nvoid selectionSort(int arr[], int n) {\n for (int i = 0; i < n - 1; i++) {\n \/\/ Set the current position as the index of the minimum value\n int minIndex = i;\n for (int j = i + 1; j < n; j++) {\n if (arr[j] < arr[minIndex]) {\n minIndex = j; \/\/ If a minimum value is found\n }\n }\n \/\/ Swap the current position with the minimum value's position\n int temp = arr[i];\n arr[i] = arr[minIndex];\n arr[minIndex] = temp;\n }\n}\n\nint main() {\n int n;\n cin >> n;\n int arr[n];\n for(int i = 0; i < n; i++) {\n cin >> arr[i];\n }\n\n selectionSort(arr, n);\n\n for(int i = 0; i < n; i++) {\n cout << arr[i];\n if (i < n - 1) cout << \" \";\n }\n cout << endl;\n\n return 0;\n}\n <\/code><\/pre>\n
3. Code Explanation<\/h3>\n
Let me explain each part of the code.<\/p>\n
\n
void selectionSort(int arr[], int n)<\/code>: This function performs selection sort. It takes an array and its size as parameters.<\/li>\n
for (int i = 0; i < n - 1; i++)<\/code>: Iterates through the array to perform sorting.<\/li>\n
int minIndex = i;<\/code>: Initializes the index of the minimum value at the current index.<\/li>\n
if (arr[j] < arr[minIndex])<\/code>: Updates the new minimum value’s index if the current value is smaller than the minimum value.<\/li>\n
int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;<\/code>: Swaps the value at the current index with the value at the minimum value’s index.<\/li>\n<\/ul>\n
4. Example Execution<\/h3>\n
Below is an example execution of the selection sort algorithm. First, we input N<\/code> and the array values.<\/p>\n
The time complexity of selection sort is O(N2<\/sup>)<\/code>. It requires two nested loops since we need to traverse all the elements to find the minimum value. Thus, performance can degrade with a large amount of data.<\/p>\n
Conclusion<\/h2>\n
In this post, we implemented selection sort using C++ and learned the basic concepts of sorting algorithms. Although selection sort is simple, it is not very efficient, so we should consider other sorting algorithms for larger datasets.<\/p>\n
Additional Resources<\/h2>\n
Many sorting algorithms exist beyond selection sort. It is recommended to learn the following algorithms:<\/p>\n
\n
Bubble Sort<\/li>\n
Insertion Sort<\/li>\n
Merge Sort<\/li>\n
Quick Sort<\/li>\n<\/ul>\n
If you want to learn more about algorithms and data structures, please refer to the following resources:<\/p>\n