Problems
Until now, we have sorted arrays with a time complexity of O(N2) using double for loops, such as selection sort, insertion sort, and bubble sort.
Therefore, if the number of elements to sort is very large, such as 100,000 or more, a time limit exceeded error will occur.
What we will learn in this problem is a simple function that sorts an array with a time complexity of O(N log N) .
It is the sort function.
In Python, sorting is possible as follows.
A = [3, 5, 2, 6, 4, 1]
A.sort() # Code to change list A into a sorted state
B = sorted(A) # Code to store each element of list A in B in a sorted state without modifying list Alist_name.sort() is a command that sorts the elements of the list and is a function with no return value.
sorted(list_name) is a function that returns a list consisting of sorted values without modifying the original list. In this case, if the returned value is not stored in a variable or used immediately, it appears as if nothing happened.
Depending on the situation, you can use one of the two methods to sort.
If you want to sort only a specific part, you can reconstruct it by slicing that part.
Let's look at the input and output formats and try to solve the problem.
#####################################################################################################################
The sort function can be used by adding the #include <algorithm> header.
The usage is very, very simple.
If you want to sort array A from index s to index e, you can write it as follows. ( s ≤ e )
std::sort ( A + s , A + e + 1 ) ;Note that the right term becomes A + e + 1.
However, there is a disadvantage that it is tedious to attach std:: in front every time.
To prevent this, you can write using namespace std; at the beginning of the code.
If you write this, you can omit std:: from now on.
In other words, the preparation process for using the sort function is as follows.
#include <algorithm> ← Header for using the sort() function
using namespace std; ← By adding this code, you can omit std:: from std::sort() and just use sort().Now, additional examples are as follows.
sort ( A + 3 , A + 7 ); ← This code sorts A[3] ~ A[6].
sort ( A + 0 , A + 5 ); ← This code sorts A[0] ~ A[4].
sort ( A , A + 5 ); ← Just like above, this code sorts A[0] ~ A[4]. A + 0 can be written as A.To understand more easily, look at the figure below. When array A is given as follows,
sort ( A + 1 , A + 5 );If you execute the above command,
It means sorting only A[1] ~ A[4], and the final result is as follows.
You can quickly sort the desired part with just one line of code!
Since it is one of the essential STL functions, make sure to memorize the syntax well.
Input
In the first line, the number of integers N is input. ( 1 ≤ N ≤ 100,000 )
In the second line, A[0], A[1], ..., A[N - 1] are input. ( All are integers within the 32-bit int range )
In the last line, the index range x y to be sorted is input. ( 0 ≤ x ≤ y ≤ N - 1 )
Output
On the first line, print the result of sorting array A from index x to index y.
On the second line, print the result of sorting the entire array A.
Example #1
9
10 5 7 4 8 2 6 8 5
1 4
10 4 5 7 8 2 6 8 5
2 4 5 5 6 7 8 8 10
Example #2
5
5 4 3 2 1
2 3
5 4 2 3 1
1 2 3 4 5
You must sign in to write code.