Язык Си в примерах/Сортировка
Задача «сортировки» (упорядочения) — одна из первых интересных и сложных задач теории алгоритмов. Общие принципы освещает статья «Алгоритмы сортировки», здесь же мы рассматриваем способы упорядочения посредством языка Си.
Содержание
Метод «пузырька» [ править ]
Один из простейших алгоритмов решения — метод «пузырька».
Понятно, что после первого «пробега» самый большой элемент массива окажется на последнем месте. После второго пробега мы будем уверены, что второй по величине элемент находится на предпоследнем месте.
Решив эту задачу, вы докажете, что метод «пузырька» решает задачу сортировки.
Функция qsort из библиотеки stdlib [ править ]
Два оператора for, в которых происходит сортировка, можно заменить на одну строку:
Это функция, описанная в стандартной библиотеке ANSI C и объявлена в заголовочном файле stdlib.h.
Поэтому в начале программы нужно добавить
Функцией qsort можно упорядочивать объекты любой природы. По сути, она предназначена упорядочивать множества блоков байтов равной длины. Второй аргумент функции — это число таких блоков, третий аргумент — длина каждого блока. Первый аргумент — это адрес, где находится начало первого блока (предполагается, что блоки в памяти расположены друг за другом подряд).
Четвёртый аргумент функции qsort — это имя функции, которая умеет сравнивать два элемента массива. В нашем случае это
В силу указанной универсальности функции сортировки, функция сравнения получает в качества аргумента адреса двух блоков, которые нужно сравнить и возвращает 1, 0 или -1:
положительное значение, если a > b 0, если a == b отрицательное значение, если a < b
Поскольку у нас блоки байт — это целые числа (в 32-битной архитектуре это четырёхбайтовые блоки), то необходимо привести данные указатели типа (const void*) к типу (int *) и осуществляется это с помощью дописывания перед указателем выражения «(const int*)». Затем нужно получить значение переменной типа int, которая лежит по этому адресу. Это делается с помощью дописывания спереди звездочки.
Таким образом, мы получили следующую программу
Динамическое выделение памяти [ править ]
Ниже приведена программа, где память под массив выделяется динамически:
Функция malloc (от англ. memory allocation — выделение памяти) делает запрос к ядру операционной системы по выделению заданного количества байт. Единственный аргумент этой функции — число байт, которое вам нужно. В качестве результата функция возвращает указатель на начало выделенной памяти. Указатель на начало выделенной памяти &mbsah — это адрес ячейки памяти, начиная с которого идут N байт, которые вы можете использовать под любые свои нужды. Всю память, которая была выделена с помощью функции malloc, нужно освобождать с помощью функции free. Аргумент функции free — это указатель на начало выделенной когда-то памяти.
Программа упорядочения строк в алфавитном порядке [ править ]
Обратите внимание на сложное приведение типов.
Функция strcmp, объявленная в файле string.h имеет следующий прототип:
То есть функция получает два аргумента — указатели на кусочки памяти, где хранятся элементы типа char, то есть два массива символов, которые не могут быть изменены внутри функции strcmp (запрет на изменение задается с помощью модификатора const) [1] .
В то же время в качестве четвертого элемента функция qsort хотела бы иметь функцию типа
В языке Си можно осуществлять приведение типов являющихся типами функции. В данном примере тип
Как отсортировать массив строк в алфавитном порядке
Данная разновидность поразрядной MSD-сортировки «заточена» для строк. Впрочем, алгоритм так назван отнюдь не за лексическую специализацию. Автор Аллен Бичик (Allen Beechick) выбрал название в честь себя любимого, ABCsort расшифровывается как Allen Beechick Character sort.
- В среднем в 2-3 раза быстрее чем быстрая сортировка, в зависимости от списка.
- Устойчивость.
- Нет вырожденных случаев.
- Не использует сравнения.
- Не использует обмены.
- Не использует опорные элементы.
- Работает одинаково хорошо с короткими и с длинными списками.
- Экономична по памяти.
- Первые отсортированные элементы уже доступны для использования в других процессах, пока сортируется оставшаяся часть списка (другими словами – сортировка устойчива).
Site design / logo © 2022 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2022.6.10.42345
How to alphabetically sort strings?
I have been trying to use this c++ program to sort 5 names alphabetically:
If I enter Earl, Don, Chris, Bill, and Andy respectively, I get this:
Could someone please tell me whats wrong with my program?
6 Answers 6
You could use std::set or std::multiset (if you will allow repeated items) of strings, and it will keep the items sorted automatically (you could even change the sorting criteria if you want).
ABC-сортировка
Данная разновидность поразрядной MSD-сортировки «заточена» для строк. Впрочем, алгоритм так назван отнюдь не за лексическую специализацию. Автор Аллен Бичик (Allen Beechick) выбрал название в честь себя любимого, ABCsort расшифровывается как Allen Beechick Character sort.
Сам по себе Бичик примечателен тем, что он не только программист, а ещё и целый магистр богословия. Заботы по упорядочиванию неотсортированных данных интересуют его только в рамках мирской профессии. Куда более уважаемого теолога волнует наведение порядка в хаосе современного общества, накануне Вознесения для истинно верующих и Страшного Суда для всех остальных.
Что касается алгоритма, то это единственно известная мне сортировка, за использование которой её изобретатель требует деньги.
Бичик
Баптист-консерватор, ярый противник претеризма. Протестантская ересь разгромлена Алленом более 30-ти лет назад в его неувядаемом бестселлере «Вознесение в преддверии Великой Скорби» («The Pre-Tribulation Rapture», 1980 г., переиздание в 1999 г.). Итогом многолетних религиозных изысканий нашего героя является книга «Разгадка Вознесения – соберём паззл вместе» («The Rapture Solution, Putting the Puzzle Together»).
Преимущества
Автору очень нравится расхваливать свой алгоритм и на сайте сортировки (web-архив) божится, что его метод обладает многочисленными достоинствами:
- В среднем в 2-3 раза быстрее чем быстрая сортировка, в зависимости от списка.
- Устойчивость.
- Нет вырожденных случаев.
- Не использует сравнения.
- Не использует обмены.
- Не использует опорные элементы.
- Работает одинаково хорошо с короткими и с длинными списками.
- Экономична по памяти.
- Первые отсортированные элементы уже доступны для использования в других процессах, пока сортируется оставшаяся часть списка (другими словами – сортировка устойчива).
Как и любая разновидность MSD-radix sort бичиковское творение сортирует не по всем разрядам. Процесс прекращается сразу как только список будет отсортирован, а не до тех пор пока не обработаются все разряды. Так же можно указать количество первых разрядов по которым произведётся упорядочивание, если старшинство по младшим разрядам не имеет особого значения.
Алгоритм
Для сортировки требуется два вспомогательных массива.
Один из них назовём трекер слов (WT – word tracker), с помощью него мы будем группировать слова, имеющих одинаковые буквы в i-м разряде. Для самого первого найденного такого слова в списке заносится значение 0. Для каждого последующего найденного слова с той же буквой в i-м разряде в трекере слов отмечается индекс предыдущего слова, соответствующего этому же признаку.
В приведённой таблице показан первый этап сортировки, когда слова группируются по первой букве. В процессе сортировки, когда происходит переход от разряда к разряду значения в этом массиве меняются, отражая цепочки слов, начинающихся с одной буквы и имеющие одинаковые литеры в том или ином месте.
Ещё один массив – трекер символов (LT – letter tracker). В нём отмечаются индексы самого первого (или последнего) слова в списке, в котором в соответствующем разряде находится определённый символ. Отталкиваясь от этого слова, с помощью трекера слов восстанавливается цепочка всех остальных лексем, имеющих в i-м разряде соответствующую букву.
Сейчас в таблице приведены индексы последних слов из списка, которые начинаются с той или иной буквы.
В данных момент с помощью этих двух таблиц можно вытащить все слова, к примеру, начинающиеся на букву «B». Для этого нужно взять значение ячейки LT[1, b] = 9 – это индекс последнего слова из списка начинающегося на «b» — Beckie. У данного слова в трекере слов трек-значение сейчас: WT[9] = 8. Это индекс предыдущего слова на «b» — Belinda. В ячейке WT[8] хранится значение 6 – под этим индексом обнаруживается Barbara, которая в свою очередь указывает на индекс Beatrix: WT[6] = 3. Трек-значение для Beatrix равно нулю, то есть относительно неё в списке нет предыдущих слов начинающихся на B.
Создавая и прослеживая подобные цепочки слов, рекурсивно продвигаясь от старших разрядов к младшим, в итоге весьма быстро формируются новые последовательности, упорядоченные в алфавитном порядке. Отсортировав слова на «A», затем сортируется «B», затем «C» и далее по алфавиту.