10.Сортировка Хоара или Quicksort
В основе лежит пузырьковая сортировка. Сначала выбирается базовый элемент ( средний или выбранный случайным образом ) После выбора все элементы большие или равные базовому перемещаются вправо, а меньшие – влево. Затем аналогичные действия повторяются до отдельно для каждой части до тех пор, пока массив не будет отсортирован.
Работает метод следующим образом: В качествек базового элемента выбирается средний элемент, массив просматривается слева на право до тех пор пока не будет найден элемент больший или равный базовому. После этого массив просматривается справа на лево дое тех пор, пока не будет найден элемент меньший либо равный базовому. Найденные элементы меняются местами. После этого массив разбивается на 2 части, большая часть помещается в стэк, а меньшая сортируется дальше. Когда размер сортируемого участка уменьшается до одного элемента, из стэка извлекается неотсортированный участок. Процесс сортироки продолжается до тех пор, пока не будут отсортированы все участки.
В большинстве случаев эта сортировка дает наилучший результат, но данный метод не любит массивов, имеющих много одинаковых массивов, а также больших отсортированных участков. Не следует использовать при сортировке небольших массивов, т.к. данный метод имеет сложный алгоритм , что снижает его эффективность.
11. Выбор метода сортировки. Поиск в массиве
1. В большинстве случаев быстр. сортировка даёт наилучший результат. Однако данный метод не любит массивов, имеющ. много одинаковых элементов и больших отсортированных участков.
2. Если сортируемый список частично упорядочен, то лучше использовать метод Шелла.
3. Для внешних корректировок хорошо подходит корректировка слияния.
4. При сортировке небольших массивов (до 1000эл.) можно использовать прямые методы, т.к. сложный алгоритм имеет длинный код, что несколько уменьшает их эффективность.
Поиск в массиве структур: Задача поиска эл. в массиве структур заключается в нахождении такого индекса, который удолетворяет условию mas [i]. X= key.
Линейный поиск ( использ. Когда нет никакой доп. Информации о нахождении искомого элемента) – представляет собой послед. Перебор элемента массива до обнаружения элемента, либо до конца, если элемент не найден.
Бинарный поиск (используется когда элементы отсортированы по заданному ключу)
12.Понятие списка, стека и очереди уже есть в вопросе 13.Понятие рекурсивного типа данных
Подобно рекурсивной ф-ии вызыв. Саму себя рекурсивный тип данных при своем списании допускает обращение к самому себе struct tinf { char fio [50]; Char adr [70]; Int otc; }; Struct tstk { tinf s; Tstk*a; }spis; Struct tstr {int inf; Tstr*a; }sp;
При размещении элементов списка в каждой адресной ячейке находится указатель на следующий элемент списка. Для работы достаточно знать указатель на 1-ый элемент списка. Доступ к основным элементам осуществ. Путем последоват. Перехода от предыдущей ячейки к последующей. Адрес последней ячейки=0. Используемый способ адресации называется косвенным. В отличии от адресации по индексу(массива) косвенная адресация менее наглядна, однако обладает большей плоскостью и например позволяют сортировать списки не перемещая элементы в памяти.