Внутренние детали std :: sort () в C ++

Опубликовано: 30 Декабря, 2021

Сортировка - одна из самых основных функций, применяемых к данным. Это означает упорядочивание данных определенным образом, который может увеличиваться или уменьшаться. В C ++ STL есть встроенная функция sort ().

std :: sort () - это общая функция в стандартной библиотеке C ++ для выполнения сортировки по сравнению.

Синтаксис:

 сортировка (начальный адрес, конечный адрес, компаратор)

куда:
startaddress: адрес первого элемента массива
endaddress: адрес последнего элемента массива
компаратор: сравнение с массивом. 
            Это необязательный аргумент.

Пример:

 // C++ program to demonstrate
 // behaviour of sort() in STL.
 
#include <bits/stdc++.h>
 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);
   
    cout << "
Array after sorting using "
         "default sort is : 
" ;
 
    for ( int i = 0; i < n; ++i)
        cout << arr[i] << " " ;
   
    return 0;
 }

Выход:

Массив после сортировки с использованием сортировки по умолчанию: 
0 1 2 3 4 5 6 7 8 9

Сложность времени

Лучший случай - O (N log N)
Средний случай - O (N log N)
Худший случай - O (N log N)

где N = количество элементов для сортировки.

Алгоритмы, используемые sort ()

Алгоритм, используемый sort (), - IntroSort . Introsort, являющийся гибридным алгоритмом сортировки, использует три алгоритма сортировки для минимизации времени выполнения: быстрая сортировка, Heapsort и сортировка вставкой. Проще говоря, это лучший алгоритм сортировки. Это гибридный алгоритм сортировки, что означает, что он использует более одного алгоритма сортировки в качестве процедуры.

Стандартная библиотека C предоставляет qsort (), который можно использовать для сортировки массива. Как следует из названия, функция использует алгоритм QuickSort для сортировки заданного массива.
Лучше использовать sort () вместо qsort (), потому что:

sort () не использует небезопасные указатели void, такие как qsort ().
qsort () выполняет большое количество вызовов функций для функции сравнения по сравнению с sort ().
Код C ++ с sort () относительно быстрее, чем код с qsort ().

Подробная статья: Сравнение sort () с qsort ()

Хотите узнать о лучших видео и практических задачах, ознакомьтесь с базовым курсом C ++ для базового и продвинутого уровня C ++ и курсом C ++ STL для базового уровня плюс STL. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

C++

Внутренние детали std :: sort () в C ++

Синтаксис:

Пример:

Сложность времени

Алгоритмы, используемые sort ()

РЕКОМЕНДУЕМЫЕ СТАТЬИ