Сортування. STL (частина 12)




сортування в с ++, СТЛАбсолютно особливу групу алгоритмів складають сортування - сортувати в практиці доводиться найрізноманітніші об'єкти і з найрізноманітніших критеріям. Аналіз алгоритмів сортування добре і докладно вивчено, як жоден інший розділ обчислювальної математики. Основним питанням будь-якого алгоритму сортування є його обчислювальна складність - число операцій порівняння-обміну, необхідних для сортування послідовності довжини N, так зване O( N ).

Неприємним обставиною є те, що для різних алгоритмів розрізняються середня складність (на більшості тестових послідовностей) і максимальна складність (на найгіршою для методу тестової послідовності). Для кількох десятків алгоритмів сортування, пропонованих в процесі навчання програмуванню, показано, що переважна більшість з них (інтуїтивно зрозумілих) є гіршими і в сенсі середньої і в сенсі максимальної складності. Як приклад, популярна у студентів пузырьковая сортировка є найгіршою з усіх взагалі відомих.

ефективними (за складністю) з усього безлічі методів є тільки кілька методів швидких рекурсивних угруповань. Вони то і представлені в реалізаціях алгоритмів STL. Стандарти не наполягають на жорсткому обмеженні на внутрішніх механізмах їх реалізації, тому можуть бути варіанти в залежності від використовуваної бібліотеки.

тепер, володіючи деякими знаннями про алгоритмах, функторах і загалом станом справ з угрупованнями, ми готові розглянути варіанти реалізації всього цього в своєму коді. Для початку ми різноманітними способами сортуємо числові послідовності. приклад Velikon, але він призначений не тільки, і не скільки, для ілюстрації, як для подальшого самостійного експериментування:

Перед компіляцією програми, в MVS натисніть Alt + F7 і внесіть Аргументи команди ?30 +3:сортування в с ++

Деяка громіздкість прикладу пов'язана з тим, що ми в одному коді об'єднуємо і всі надані STL алгоритми сортування, і різноманітні тестові сортовані послідовності, например:

  • кілька випадкових (?) послідовностей довжини 30, сортируемих з використанням (3) функтора порівняння, і деталізованим (+) висновком вхідний і вихідний послідовності:

    сортування в с ++

  • інверсна (зворотна, спадна) послідовність, сортируемое (6) «В купі» з використанням бінарного дерева (аргументи команди -30 +6 ):сортування в с ++

  • довга (1000000) послідовність, в тих же, що і попередній випадок, умовах, але з висновком тільки діагностики коректності результату (аргументи команди -1000000 6 ):

    сортування в с ++

Бібліотека STL надає 3 групи алгоритмів сортування:

  • сортувати() – найбільш швидке сортування в середньому ( O( N * журнал( N ) ), але яка може «провалюватися» в гіршому випадку до O( N * N ) (а це дуже поганий показник);

  • sort_heap() – сортування в «в купі», з використанням бінарного дерева, складність якої завжди не гірше O( N + N * журнал( N ) ) (це гірше сортувати() в середньому, але краще в найгіршому випадку);

  • stable_sort() – «Стійка» сортування злиттям, стійкість якої означає, що вона зберігає відносний порядок рівних елементів після сортування. Це іноді дуже важливо. Складність цього алгоритму не набагато поступається сортувати();

Використовуйте той алгоритм, який найбільше відповідає обмеженням вашого завдання.

Нові уроки з програмування:

дата
сторінка
Сортування. STL (частина 12)
рейтинг
51зірка1зірка1зірка1зірка1зірка
Olej

Про Olej

Стаж практичних програмних розробок близько 40 лет. Викладач міжнародної софтверної компанії Global Logic. Постійний автор публікацій IBM Developer Works. Науковий редактор книжкового видавництва комп'ютерної літератури "Символ-Плюс", Санкт-Петербург.

залишити коментар

Код розміщуйте в тегах: <pre class="lang:C ++ декодуванням:true ">ВАШ КОД</заздалегідь>