Problem Description
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.
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.
Input Format
The first line contains the number of elements N (1 ≤ N ≤ 100,000).
Starting from the second line, N lines will contain the numbers.
Output Format
Print the sorted numbers, one per line.
Example Input
5
5
4
3
2
1
Example Output
1
2
3
4
5
Problem Solving Process
1. Understanding the Problem
This problem is a basic number sorting problem, and various sorting algorithms can be applied.
In C++, the standard library’s sorting function can be used, providing an efficient solution.
However, implementing sorting algorithms manually is also a good practice, so I will introduce two methods: selection sort and insertion sort.
2. Basic Data Collection and Storage
To receive input data, an array or vector can be used. In C++, using a vector is common.
Here is how to store data using a vector.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N; // Input the number of elements
vector<int> numbers(N);
for (int i = 0; i < N; i++) {
cin >> numbers[i]; // Input numbers
}
return 0;
}
3. Sorting Algorithms
Let’s implement two methods for sorting the vector that contains the input numbers, namely selection sort and insertion sort.
3-1. Selection Sort
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.
The time complexity of selection sort is O(N^2).
void selectionSort(vector<int> &arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]); // Swap elements
}
}
3-2. Insertion Sort
Insertion sort inserts each element of the array into its appropriate position to sort the array.
The time complexity of insertion sort is O(N^2), which is efficient when the data is nearly sorted.
void insertionSort(vector<int> &arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // Move elements
j--;
}
arr[j + 1] = key; // Insert
}
}
4. Final Code
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.
#include <iostream>
#include <vector>
#include <algorithm> // Includes sort() function
using namespace std;
int main() {
int N;
cin >> N; // Input the number of elements
vector<int> numbers(N);
for (int i = 0; i < N; i++) {
cin >> numbers[i]; // Input numbers
}
sort(numbers.begin(), numbers.end()); // Perform sorting
for (int i = 0; i < N; i++) {
cout << numbers[i] << endl; // Print sorted numbers
}
return 0;
}
5. Time Complexity
By using the standard library’s sort function as shown above, sorting can be done with an average time complexity of O(N log N).
This is much more efficient than selection sort and insertion sort.
6. Conclusion
Through the “Sorting Numbers 2” problem, we practiced the basic concepts of sorting algorithms and how to use C++ vectors.
Understanding and implementing various sorting algorithms is a very useful process for improving programming skills.
It will enhance understanding of sorting algorithms commonly used in practice and lay the groundwork for solving more complex algorithms.