Hello! In this lecture, we will cover the coding test problem “Sorting Numbers 1” using C++. This problem is a good foundation for sorting algorithms and allows us to compare the efficiency of various algorithms. We will examine the process of solving the problem step by step.<\/p>\n
The problem is as follows:<\/p>\n
\nGiven N numbers, sort them in ascending order and print them.\n(The integer N is between 1 and 1,000,000.)\n<\/pre>\nInput example:<\/p>\n
\n5\n5\n3\n2\n4\n1\n<\/pre>\nOutput example:<\/p>\n
\n1\n2\n3\n4\n5\n<\/pre>\nProblem Analysis<\/h2>\n
This problem serves as a fundamental problem for sorting algorithms, where you simply need to sort and print the given numbers. It is ideal to use an efficient algorithm with a time complexity of O(N log N). The most commonly used sorting algorithms include Quick Sort, Merge Sort, and Heap Sort. In this problem, we can conveniently use the `std::sort` function from C++’s STL (Standard Template Library) to solve the problem easily.<\/p>\n
Solve Process<\/h2>\n
1. Input Processing<\/h3>\n
First, we need to decide how to handle the input. In C++, we can use
cin<\/code> to read numbers from standard input. We will first input the number of values and then read the numbers into a vector.<\/p>\n2. Selecting a Sorting Algorithm<\/h3>\n
There are various sorting algorithms mentioned above, but it’s most convenient to use the
std::sort<\/code> function from C++ STL. This function internally uses the Quick Sort algorithm, providing an average performance of O(N log N).<\/p>\n3. Outputting the Sorted Result<\/h3>\n
To print the sorted results, we need to use a loop again. Since we need to line break with each printed number, we can utilize
cout<\/code>.<\/p>\n4. Code Implementation<\/h3>\n
Based on the above contents, let’s write the full code.<\/p>\n
\n#include\n#include \n#include \/\/ Include required for std::sort\n\nusing namespace std;\n\nint main() {\n int N;\n cin >> N; \/\/ Input the number of values\n\n vector numbers(N); \/\/ Declare vector to store the numbers\n\n \/\/ Input the numbers\n for (int i = 0; i < N; i++) {\n cin >> numbers[i];\n }\n\n \/\/ Sort in ascending order\n sort(numbers.begin(), numbers.end());\n\n \/\/ Output the sorted numbers\n for (int i = 0; i < N; i++) {\n cout << numbers[i] << endl;\n }\n\n return 0;\n}\n<\/int><\/algorithm><\/vector><\/iostream><\/pre>\n Code Explanation<\/h2>\n
Let’s examine the code line by line:<\/p>\n
\n
#include <iostream><\/code>: Library for input and output.<\/li>\n#include <vector><\/code>: Library for using dynamic arrays.<\/li>\n#include <algorithm><\/code>: Library for using STL algorithm functions.<\/li>\nusing namespace std;<\/code>: Added to use the std namespace.<\/li>\nint N;<\/code>: Declares a variable to store the number of values.<\/li>\nvectornumbers(N);<\/int><\/code>: Declares a vector to store N integers.<\/li>\n cin<\/code>: Used to receive input from the user for N numbers.<\/li>\nsort(numbers.begin(), numbers.end());<\/code>: Sorts the numbers in the vector in ascending order.<\/li>\ncout<\/code>: Outputs the sorted results.<\/li>\n<\/ul>\nTest Cases<\/h2>\n
Now that we have written the code, we will run it with various test cases. Below are some examples.<\/p>\n
Example 1<\/h3>\n
Input:<\/p>\n
\n5\n5\n3\n2\n4\n1\n<\/pre>\nOutput:<\/p>\n
\n1\n2\n3\n4\n5\n<\/pre>\nExample 2<\/h3>\n
Input:<\/p>\n
\n10\n9\n8\n7\n6\n5\n4\n3\n2\n1\n0\n<\/pre>\nOutput:<\/p>\n
\n0\n1\n2\n3\n4\n5\n6\n7\n8\n9\n<\/pre>\nExample 3<\/h3>\n
Input:<\/p>\n
\n3\n1\n1\n1\n<\/pre>\nOutput:<\/p>\n
\n1\n1\n1\n<\/pre>\nPerformance Analysis<\/h2>\n
Now let’s analyze the performance of the algorithm.
std::sort<\/code> has an average performance of O(N log N). Thus, even in cases where we input integers within the range of 1 to 1,000,000, it will operate quickly enough. While various sorting algorithms can also be used,std::sort<\/code> is the most suitable for meeting the problem’s requirements.<\/p>\nConclusion<\/h2>\n
In this lecture, we covered the “Sorting Numbers 1” problem using C++. We learned the basics of sorting as well as how to utilize STL. In the next lecture, we will explore more complex data structures and algorithms. Thank you!<\/p>\n