우리는 논의했습니다 C의 qsort() C++ STL은 벡터 또는 배열(랜덤 액세스가 가능한 항목)을 정렬하는 유사한 함수 정렬을 제공합니다.
일반적으로 두 개의 매개변수를 사용합니다. 첫 번째 매개변수는 정렬을 시작해야 하는 배열/벡터의 지점이고 두 번째 매개변수는 배열/벡터가 정렬되기를 원하는 최대 길이입니다. 세 번째 매개변수는 선택사항이며 요소를 사전순으로 정렬하려는 경우에 사용할 수 있습니다.
기본적으로 sort() 함수는 요소를 오름차순으로 정렬합니다.
다음은 sort()의 작동을 보여주는 간단한 프로그램입니다.
CPP
// C++ program to demonstrate default behaviour of> // sort() in STL.> #include> using> namespace> std;> int> main()> {> >int> arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };> >int> n =>sizeof>(arr) />sizeof>(arr[0]);> >/*Here we take two parameters, the beginning of the> >array and the length n upto which we want the array to> >be sorted*/> >sort(arr, arr + n);> >cout <<>'
Array after sorting using '> >'default sort is :
'>;> >for> (>int> i = 0; i cout << arr[i] << ' '; return 0; }> |
>
>산출
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>
시간 복잡도: O(N로그N)
보조 공간: 오(1)
내림차순으로 정렬하는 방법은 무엇입니까?
sort()는 요소가 정렬되는 순서를 지정하는 데 사용되는 세 번째 매개변수를 사용합니다. 더 큰() 함수를 전달하여 내림차순으로 정렬할 수 있습니다. 이 함수는 더 큰 요소를 앞에 두는 방식으로 비교를 수행합니다.
CPP
// C++ program to demonstrate descending order sort using> // greater().> #include> using> namespace> std;> int> main()> {> >int> arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };> >int> n =>sizeof>(arr) />sizeof>(arr[0]);> >sort(arr, arr + n, greater<>int>>());> >cout <<>'Array after sorting :
'>;> >for> (>int> i = 0; i cout << arr[i] << ' '; return 0; }> |
>
>산출
Array after sorting : 9 8 7 6 5 4 3 2 1 0>
시간 복잡도: O(N로그N)
보조 공간: 오(1)
주어진 범위에서만 배열을 정렬합니다. 이러한 유형의 문제를 처리하려면 정렬 기능 내에서 범위를 언급하면 됩니다.
위 사례의 구현은 다음과 같습니다.
C++
// C++ program to demonstrate sort()> #include> using> namespace> std;> int> main()> {> >int> arr[] = { 0, 1, 5, 8, 9, 6, 7, 3, 4, 2 };> >int> n =>sizeof>(arr) />sizeof>(arr[0]);> >// Sort the elements which lies in the range of 2 to> >// (n-1)> >sort(arr + 2, arr + n);> >cout <<>'Array after sorting :
'>;> >for> (>int> i = 0; i cout << arr[i] << ' '; return 0; } // This code is contributed by Suruchi Kumari> |
>
>산출
Array after sorting : 0 1 2 3 4 5 6 7 8 9>
시간 복잡도: O(N log N)
보조 공간: O(1)
에서 정렬하는 방법 특별한 순서?
또한 자체 비교 함수를 작성하여 세 번째 매개변수로 전달할 수도 있습니다. 이 비교 함수는 값을 반환합니다. bool로 변환 가능하며 이는 기본적으로 전달된 첫 번째 인수가 전달된 두 번째 인수 앞에 배치되어야 하는지 여부를 알려줍니다.
예: 아래 코드에서 간격 {6,8} 및 {1,9}가 CompareInterval 함수(비교기 함수)의 인수로 전달된다고 가정합니다. 이제 i1.first(=6)로
CPP
// A C++ program to demonstrate> // STL sort() using> // our own comparator> #include> using> namespace> std;> // An interval has a start> // time and end time> struct> Interval {> >int> start, end;> };> // Compares two intervals> // according to starting times.> bool> compareInterval(Interval i1, Interval i2)> {> >return> (i1.start } int main() { Interval arr[] = { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } }; int n = sizeof(arr) / sizeof(arr[0]); // sort the intervals in increasing order of // start time sort(arr, arr + n, compareInterval); cout << 'Intervals sorted by start time :
'; for (int i = 0; i cout << '[' << arr[i].start << ',' << arr[i].end << '] '; return 0; }> |
>
>산출
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>
std::sort()의 시간 복잡도 이다:
자바를 두 배로 늘리는 정수
- 최선의 경우 - O(N log N)
- 평균 사례 – O(N log N)
- 최악의 경우 - O(N log N)
공간 복잡도: O(log N)개의 보조 공간을 사용할 수 있습니다.
C++
#include> #include> using> namespace> std;> template> <>class> T>> class> Comparator {>// we pass an object of this class as> >// third arg to sort function...> public>:> >bool> operator()(T x1, T x2)> >{> >return> x1 } }; template |
>
>산출
The array before sorting is : 1 5 8 9 6 7 3 4 2 0 The array after sorting is(asc) :0 1 2 3 4 5 6 7 8 9 The array after sorting is(desc) :9 8 7 6 5 4 3 2 1 0 The array after sorting is(asc but our comparator class) :0 1 2 3 4 5 6 7 8 9 The array after sorting is(asc but our comparator function) :0 1 2 3 4 5 6 7 8 9>
시간 복잡도: O(N로그N)
보조 공간: 오(1)