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

Сортування. STL (частина 12)
1 (20%) 1 голосування




сортування в с ++, СТЛАбсолютно особливу групу алгоритмів складають сортування - сортувати в практиці доводиться найрізноманітніші об'єкти і з найрізноманітніших критеріям. Аналіз алгоритмів сортування добре і докладно вивчено, як жоден інший розділ обчислювальної математики. Основним питанням будь-якого алгоритму сортування є його обчислювальна складність - число операцій порівняння-обміну, необхідних для сортування послідовності довжини 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() – «Стійка» сортування злиттям, стійкість якої означає, що вона зберігає відносний порядок рівних елементів після сортування. Це іноді дуже важливо. Складність цього алгоритму не набагато поступається сортувати();

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

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

Olej

Про Olej

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

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

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