Блог пользователя x-firdavs.95

Сортировка в C++
Автор x-firdavs.95, 11 лет назад, По-русски

Самое простое это добавление библиотеки algorithm, Example:

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[100];
    /*--------------------
    --------------------
    --------------------*/

    //кароче мы обявляем массив вводим его и после просто используем sort(begin, end); и всё
    sort(a, a + n); //n здесь количество элементов массива

    /*--------------------
    --------------------
    --------------------*/
     
    return 0;
}

Просто здесь я полностью не описал sort() Потому что для просто сортировки и этого хватает!

  • Проголосовать: нравится
  • -34
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

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

Во-первых, как и большинство других функций библиотеки algorithm функция sort реализована на итераторах — аналоге указателей для С++. Общий вид функции таков:

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

first и last задают границы сортировки, а comp — бинарный предикат, который употребляется при проверке того, меньше ли один элемент чем другой. По умолчанию вместо него используется оператор "<".

Подробнее о first и last. Как уже можно было заметить, они не обязательно должны являться итераторами, но они должны соответствовать требованиям RandomAccessIterator. Это означает, что они должны поддерживать следующие операции (в качестве примера применения операции будут использоваться произвольные переменные, выполняющие роль итераторов a и b и произвольная целочисленная переменная n):
Требования BidirectionalIterator:
- Разыменование (*a);
- Инкремент (a++);
- Декремент (a--);
Дополнительные требования:
- Увеличение\уменьшение на произвольное целое число (a+=n\a-=n);
- Сложение с целым число\вычитание целого числа (a+n\a-n);
- Расстояние между итераторами (b-a);
- Логические операции сравнения (<,>,<=,>=);

Классичесским примером структуры, отвечающей требованиям RandomAccessIterator является указатель C, который, кстати, и применяется неявно в примере автора блога.

Также отдельно стоит отметить ассимптотику. В STL реализована introsort, что гарантирует её быстроту на всех наборах данных и вычислительную сложность O(nlogn).

Что полезного можно почерпнуть из вышесказанного:

- Сортировку STL можно применять к любым диапозонам данных, которые можно задать через RandomAccessIterator. Среди примеров стоит отметить C++ vector — стек с поддержкой разименований, который способен за О(1) добавлять и удалять элементы в\из конца, при этом сохраняя ассимптотику по памяти О(n). C++ deque — дек (кольцо), также с поддержкой разименований, который помимо операции разименования способен за О(1) добавлять и доставать элементы с обоих концов. Также стоит отметить, что можно сортировать не только контейнер целиком, но и конкретные его части. В случае с массивом это можно сделать так:

sort(a+first,a+last);

В случае с векторами или деками:

sort(a.begin()+first,a.begin()+last);

где a — vector или deque, а first и last — индексы элементов, такие что сортировка происходит на отрезке [first;last) или

sort(a,b);

Где a и b — RandomAccessIterator.

- Сортировать можно не только по возрастанию. С использованием бинарного предиката, можно осуществить сортировку по убыванию, лексикографически или по какому-либо другому произвольному признаку, сопоставимому с оператором < так, чтобы в итоге для каждых двух элементов a,b таких, что comp(a,b) возвращает истину, будет выполняться, что a будет находится левее b.
- Вычислительная сложность сортировки делает её использование как в быту, так и в различных соревнованиях более, чем оправданной.

→ Ответить