Сортиране е една от най-основните и полезни функции, приложени към данните. Той има за цел да подреди данните по определен начин, който може да се увеличава или намалява според изискванията. В C ++ STL има вградена функция с името ‘sort ()’, която ни позволява да изпълняваме лесно алгоритъма за сортиране. В тази статия ще изследваме функцията за сортиране в C ++,
Следните указания ще бъдат разгледани в тази статия:
- Функция сортиране ()
- Пример - за сортиране на данни във възходящ ред
- Пример - за сортиране на данни в низходящ ред
- Частично_сортиране
Продължавайки с тази статия за функцията за сортиране в C ++
Вид ( ) функция
Това е вградена функция на заглавния файл на алгоритъма, използва се за сортиране на контейнерите като масив, вектори в определен ред. Вътрешно тази функция е реализирана като Бързо сортиране
Quicksort е алгоритъм за разделяне и завладяване. Quicksort първо разделя голям списък с елементи на два по-малки под-списъка: долните елементи и по-горните елементи. След това Quicksort рекурсивно сортира под-списъците.
Стъпките са както следва:
1. Изберете произволен елемент (обикновено последния елемент), наречен опорен елемент, от списъка.
2. Пренаредете списъка по такъв начин, че всички елементи със стойности, по-малки от pivot, да идват преди pivot, докато всички елементи със стойности, по-големи от pivot, идват след него и еднакви стойности могат да вървят по двата начина, това е процесът се нарича операция на разделяне.
3. Рекурсивно сортирайте под-списъка с по-малки елементи и под-списъка с по-големи елементи, отново изберете ос в под-списъка и ги разделете.
Основният случай на рекурсията са списъци с размер нула или един, които никога не трябва да бъдат сортирани и по този начин чрез комбинирането им ние сортираме нашия списък.
сортиране на списък c ++
Quicksort е на практика по-бърз от другите O (n log n) алгоритми като Insertion Sort или Bubble sort. Quicksort може да бъде реализиран с алгоритъм за разделяне на място, което означава, че цялото сортиране може да се извърши само с O (log n) допълнително пространство. Quicksort не е стабилен сорт.
Сложността му е следната:
Най-добрият случай - O (n log n)
Най-лошият случай - O (n ^ 2)
Среден случай - O (n log n)
Синтаксис:
сортиране (първо, последно)
Тук,
first - е индексът (показалеца) на първия елемент в диапазона, който трябва да бъде сортиран.
последен - е индексът (показалеца) на последния елемент в диапазона, който трябва да бъде сортиран.
Например искаме да сортираме елементи от масив ‘arr’ от 1 до 10 позиция, ще използваме сортиране (arr, arr + 10) и то ще сортира 10 елемента във възходящ ред.
Върната стойност
Нито един
Сложност
Средната стойност за сложност на сортиране е N * log2 (N), където N = последно - първо.
Обхват на данните
Обектът в диапазона [първи, последен) са променени.
Изключения
Претоварванията с параметър на шаблон, който е наречен като грешки в отчета за изпълнение, както следва:
Ако алгоритъмът не успее да разпредели паметта, std :: bad_alloc се изхвърля като изключение.
Ако изпълнението на функция, извикана като част от алгоритъма, изхвърля изключение std :: terminate.
Продължавайки с тази статия за функцията за сортиране в C ++
Пример - За да сортирате данните във възходящ ред:
#include използвайки пространство от имена std int main () {int array [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = sizeof (array) / sizeof (array [0] ) // 'sizeof' дава размера на общия масив, т.е. размера на всеки знак * не. от символи // така че да се получи не. от символи // разделяме sizeof (масива) с размера на който и да е символ от масива // тук е масив [0] сортиране (масив, масив + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 }
Изход:
Обяснение
От горния пример виждаме, че функцията sort () по подразбиране сортира масив във възходящ ред.
абстрактен клас и разлика в интерфейса
Продължавайки с тази статия за функцията за сортиране в C ++
Пример - За да сортирате данните в низходящ ред:
За да сортираме данните от масива в низходящ ред, трябва да въведем трети параметър, който се използва за определяне на реда, в който трябва да се сортират елементите. Можем да използваме функцията “larger ()”, за да сортираме данните в низходящ ред.
#include използвайки пространство от имена std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = sizeof (array) / sizeof (array [0] ) сортиране (масив, масив + n, по-голям ()) cout<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 }
Изход:
Опит л анация
Тук функцията sort () прави сравнение по начин, който поставя по-голям елемент преди.
Продължавайки с тази статия за функцията за сортиране в C ++
Частично_сортиране
C ++ STL ни предоставя функция за частично сортиране, функцията е подобна на функцията sort (), но за разлика от функцията sort () не се използва за сортиране на целия диапазон, а се използва за сортиране само на част от нея. Той сортира елементите в диапазона на [първи, последен), по такъв начин, че елементите преди средния елемент да бъдат сортирани във възходящ ред, докато елементите след средата са оставени такива, каквито са.
Може да се използва за намиране на най-големия елемент, ако използваме функционален обект за сортиране за първата позиция
Пример
#include #include #include с помощта на пространство от имена std int main () {vector vec = {10, 45, 60, 78, 23, 21, 30} vector :: iterator iptr частично_сортиране (vec.begin (), vec.begin () + 1, vec.end (), по-голяма ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 }
Изход:
Обяснение:
Горният код може да се използва за намиране на най-голямото число в серия, за да намерим най-малкото число в серия, просто трябва да премахнем по-голямата команда.
По този начин стигнахме до края на тази статия за „Функция за сортиране в C ++“. Ако искате да научите повече, разгледайте Java Training от Edureka, доверена компания за онлайн обучение. Edureka’s Курсът е предназначен да ви обучи както за основни, така и за разширени Java концепции, заедно с различни Java рамки като Hibernate & Spring.
Имате въпрос към нас? Моля, споменете го в раздела за коментари на този блог и ние ще се свържем с вас възможно най-скоро.