Блог пользователя Algorithm

Нужна помощь с сортировкой на C++
Автор Algorithm, 13 лет назад, По-русски
Недавно перешел на C++. Помогите пожалуста с написанием алгоритма сортировки строк в лексикографическом порядке.
  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
объявляешь массив строк или массивов charов
и пользуешься функцией sort :
string s[100500];
int n;
sort (s, s+n);
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Используя библиотеку, которая по названию совпадает с вашим именем (#include <algorithm>):

sort(a+x,a+y,cmp); 

Где а - массив строк. Сортируем от x до y-1. Функция cmp задаёт функцию сортировки строк.

либо sort(a+x,a+y); если известно что используется оператор по умолчанию "<"

<это меня уже кроет>

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ещё не надо забывать про stable_sort, которая не меняет порядка одинаковых (по заданному критерию сортировки) элементов. :)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
еще есть C-шный qsort() =)) мало кто им юзается, одна он побыстрее sort будет  
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится
    Сомневаюсь, и даже если быстрее, надо? В С++ очень хороший логарифм, быстрее... даже не знаю что... разве напрямую по битовой записи числа сортировать, однако это еще надо хорошо написать, я лично пока не умею писать чтобы было ровно за линейное время
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      она тоже O(n*log(n)) :)
      Просто указательный хардкор там :) 
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Что, серьезно, существует реализация qsort за n log n?

        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится
          +2:) я знаю лишь решение которое с определенной вероятностью за логарифм работает:). Правда вероятность хорошая, но отклонение от чистого логарифма есть
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Существует. В Кормене описан алгоритм поиска k-ой порядковой статистики за O(n) в худшем случае. Очевидно, что эта же идея применима к быстрой сортировке. И тогда она будет работать за nlogn в худшем случае. Однако там константа будет.....
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Вопрос.... А что насчёт heapsort?
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится
              Насколько я знаю, sort сортирует быстрой сортировкой, а если она сильно в рекурсию уходит, то он бросает это дело и сортирует кучей. Если очень хочется, юзаем make_heap, потом sort_heap и радуемся.
              → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится
              Речь шла именно про qsort за nlogn.  

              А sort он вообще умный. Я еще слышал, что он если совсем мало осталось вставками все сортирует, так как они на маленьких массивах быстрее работают.
              → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
    А вот неправда. На самом деле при правильном использовании sort значительно быстрее qsort чисто технически. Потому что qsort работает исключительно через указатель на функцию сравнения, а sort можно заставить ее заинлайнить и тем самым сэкономить на вызовах. Подробнее можно у Мейерса почитать.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо за ссылку. Просто в свое время довелось поэкспериментировать на эту тему, и qsort вел себя заметно быстрее на случайно сгенерированных данных.
      На сколько я понимаю и там и там быстрая сортировка используется.

      → Ответить
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
правда он к stl не применим :)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    sort (v.begin(), v.end());
    чтоб знал:)
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Не понимаю, почему не применим к stl?

    если вы о том что он с итераторами не работает это так, но в vector элементы лежат в памяти последовательно, и вы можете вызвать скажем вот так qsort(&v[0], (&v[0]) + v.size(), cmp);

    → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Еще важный момент который я знаю по олимпиадам,

но использовал и на работе это то что sort и qsort использует

больше вызовов оператора сравнения, чем stable_sort.

Если мы сортируем суффиксы строки оператором сравнения

рабатающим за O( Log N ) то stable_sort гораздо эффективнее.

сортировка слиянием вроде бы ещё меньше раз использует оператор,

надо протестить. это важно если объекты небольшие (можно сортить указатели),

а сравнение тормозное.

→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Если я ничего не путаю, sort для каждой проверяемой пары запускает функцию сравнения дважды (по крайней мере если она указана отдельно), это можно пронаблюдать запустив дебуг. Вначале запускается cmp(a,b) потом cmp(b,a).

    Вероятно это сделано, чтобы проверять корректна ли заданная функция (то есть обязательно должно быть cmp(a,b)!=cmp(b,a))

    UPD. небольшая ошибка: ...обязательно должно быть (cmp(a,b) && cmp(b,a))==0

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      э... возможно я что то путаю, но в случае a=b cmp(a,b)==cmp(b,a). по идее, на самом деле никогда не должно выполняться cmp(a,b) && cmp(b,a).
      а так sort точно как то иногда отлавливает кривой компаратор - однажды сокомандник час подряд получал RE на тупой задача - оказалось из-за кривого компаратора , который sort отловил.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да.. что-то я точно недопонимаю, как он отлавливает случай равенства элементов... тем не менее если написать например return a!=b; то прога выдаст ошибку, что компаратор по-разному реагирует на одни и те же данные (если продебужить, заметно, что именно после вызова cmp(a,b) и cmp(b,a))...

        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          ну так все правильно.
          cmp подразумевает "<".
          если вдруг одновременно a<b и b<a, то упорядочить эти два элемента невозможно и sort будет ругаться (для компаратора a!=b как раз такая фигня происходит).
          а если a=b, то оба выражения a<b и b<a не верны - и sort на них не ругается.
          → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      в дебаге совершенно другой код генерируется, релиз следует тестировать на скорость и кол-во сравнений
      → Ответить