\n The “Sorting Numbers 2” problem is about sorting the given sequence of numbers and outputting it. This problem aims to understand and implement common sorting algorithms.
\n Given N numbers, the task is to sort this sequence in ascending order and output the result. The numbers are integers that are greater than or equal to -1000 and less than or equal to 1000.\n <\/p>\n
\n The first line contains the number of elements N (1 \u2264 N \u2264 100,000).
\n Starting from the second line, N lines will contain the numbers.\n <\/p>\n
\n Print the sorted numbers, one per line.\n <\/p>\n
\n5\n5\n4\n3\n2\n1\n <\/pre>\nExample Output<\/h2>\n
\n1\n2\n3\n4\n5\n <\/pre>\nProblem Solving Process<\/h2>\n
1. Understanding the Problem<\/h3>\n
\n This problem is a basic number sorting problem, and various sorting algorithms can be applied.
\n In C++, the standard library’s sorting function can be used, providing an efficient solution.
\n However, implementing sorting algorithms manually is also a good practice, so I will introduce two methods: selection sort and insertion sort.\n <\/p>\n2. Basic Data Collection and Storage<\/h3>\n
\n To receive input data, an array or vector can be used. In C++, using a vector is common.
\n Here is how to store data using a vector.\n <\/p>\n\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nint main() {\n int N;\n cin >> N; \/\/ Input the number of elements\n\n vector<int> numbers(N);\n for (int i = 0; i < N; i++) {\n cin >> numbers[i]; \/\/ Input numbers\n }\n return 0;\n}\n <\/code><\/pre>\n3. Sorting Algorithms<\/h3>\n
\n Let’s implement two methods for sorting the vector that contains the input numbers, namely selection sort and insertion sort.\n <\/p>\n
3-1. Selection Sort<\/h4>\n
\n Selection sort selects the smallest (or largest) element from the given array and moves it to the front. This is repeated until sorting is complete.
\n The time complexity of selection sort is O(N^2).\n <\/p>\n\nvoid selectionSort(vector<int> &arr) {\n int n = arr.size();\n for (int i = 0; i < n - 1; i++) {\n int minIndex = i;\n for (int j = i + 1; j < n; j++) {\n if (arr[j] < arr[minIndex]) {\n minIndex = j;\n }\n }\n swap(arr[i], arr[minIndex]); \/\/ Swap elements\n }\n}\n <\/code><\/pre>\n3-2. Insertion Sort<\/h4>\n
\n Insertion sort inserts each element of the array into its appropriate position to sort the array.
\n The time complexity of insertion sort is O(N^2), which is efficient when the data is nearly sorted.\n <\/p>\n\nvoid insertionSort(vector<int> &arr) {\n int n = arr.size();\n for (int i = 1; i < n; i++) {\n int key = arr[i];\n int j = i - 1;\n while (j >= 0 && arr[j] > key) {\n arr[j + 1] = arr[j]; \/\/ Move elements\n j--;\n }\n arr[j + 1] = key; \/\/ Insert\n }\n}\n <\/code><\/pre>\n4. Final Code<\/h3>\n
Let’s complete the final code by choosing one of the sorting algorithms above. Below is a method using the vector and the standard library’s sort function.<\/p>\n
\n#include <iostream>\n#include <vector>\n#include <algorithm> \/\/ Includes sort() function\nusing namespace std;\n\nint main() {\n int N;\n cin >> N; \/\/ Input the number of elements\n\n vector<int> numbers(N);\n for (int i = 0; i < N; i++) {\n cin >> numbers[i]; \/\/ Input numbers\n }\n\n sort(numbers.begin(), numbers.end()); \/\/ Perform sorting\n\n for (int i = 0; i < N; i++) {\n cout << numbers[i] << endl; \/\/ Print sorted numbers\n }\n\n return 0;\n}\n <\/code><\/pre>\n5. Time Complexity<\/h3>\n