Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Внешняя и внутреняя сортировка
Понятие сортировки Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. "Внешней" сортировкой принято называть сортировку последовательных файлов, располагающихся во внешней памяти и слишком больших, чтобы можно было целиком переместить их в основную память и применить один из рассмотренных в предыдущем разделе методов внутренней сортировки. Внутренняя сортировка является базовой для любого алгоритма внешней сортировки — отдельные части массива данных сортируются в оперативной памяти и с помощью специального алгоритма сцепляются в один массив, упорядоченный по ключу.
Сортировка с простым включением Пусть имеется массив ключей a[1], a[2],..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2]...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива). Массив: 23, 8, 5, 65, 47, 34, 1, 6 Шаг 1: i1= 8, 23, 5, 65, 47, 34, 1, 6 Шаг 2: i2= 8, 5, 23, 65, 47, 34, 1, 6 5, 8, 23, 65, 47, 34, 1, 6 Шаг 3: i3= 5, 8, 23, 65, 47, 34, 1, 6 Шаг 4: i4= 5, 8, 23, 47, 65, 34, 1, 6 Шаг 5: i5= 5, 8, 23, 47, 34, 65, 1, 6 5, 8, 23, 34, 47, 65, 1, 6 Шаг 6: i6= 5, 8, 23, 34, 47, 1, 65, 6 5, 8, 23, 34, 1, 47, 65, 6 5, 8, 23, 1, 34, 47, 65, 6 5, 8, 1, 23, 34, 47, 65, 6 5, 1, 8, 23, 34, 47, 65, 6 1, 5, 8, 23, 34, 47, 65, 6 Шаг 7: i7= 1, 5, 8, 23, 34, 47, 6, 65 1, 5, 8, 23, 34, 6, 47, 65 1, 5, 8, 23, 6, 34, 47, 65 1, 5, 8, 6, 23, 34, 47, 65 1, 5, 6, 8, 23, 34, 47, 65
Сортировка методом Шелла Метод состоит в том, что упорядочиваемая таблица разделяется на группы элементов, каждая из которых упорядочивается методом вставки. В процессе упорядочения размеры таких
d=[n/2] Массив: 23, 8, 5, 65, 47, 34, 1, 6, 13, 52 Шаг 1: d=5 (сортируются элементы, расстояние между которыми пять) 23, 8, 5, 65, 47, 34, 1, 6, 13, 52 –массив не меняется 23, 8, 5, 65, 47, 34, 1, 6, 13, 52 23, 1, 5, 65, 47, 34, 8, 6, 13, 52 23, 1, 5, 65, 47, 34, 8, 6, 13, 52– массив не меняется 23, 1, 5, 65, 47, 34, 8, 6, 13, 52 23, 1, 5, 13, 47, 34, 8, 6, 65, 52 23, 1, 5, 13, 47, 34, 8, 6, 65, 52 – массив не меняется Шаг 2: d=3 (сортируются элементы, расстояние между которыми три) 23, 1, 5, 13, 47, 34, 8, 6, 65, 52 13, 1, 5, 23, 47, 34, 8, 6, 65, 52 13, 1, 5, 23, 47, 34, 8, 6, 65, 52– массив не меняется 13, 1, 5, 23, 47, 34, 8, 6, 65, 52– массив не меняется 13, 1, 5, 23, 47, 34, 8, 6, 65, 52 13, 1, 5, 8, 47, 34, 23, 6, 65, 52 13, 1, 5, 8, 47, 34, 23, 6, 65, 52 13, 1, 5, 8, 6, 34, 23, 47, 65, 52 13, 1, 5, 8, 6, 34, 23, 47, 65, 52– массив не меняется 13, 1, 5, 8, 6, 34, 23, 47, 65, 52 – массив не меняется
Шаг 3: d=2 (сортируются элементы, расстояние между которыми два) 13, 1, 5, 8, 6, 34, 23, 47, 65, 52 5, 1, 13, 8, 6, 34, 23, 47, 65, 52 5, 1, 13, 8, 6, 34, 23, 47, 65, 52– массив не меняется 5, 1, 13, 8, 6, 34, 23, 47, 65, 52 5, 1, 6, 8, 13, 34, 23, 47, 65, 52 5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется 5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется 5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется 5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется 5, 1, 6, 8, 13, 34, 23, 47, 65, 52 – массив не меняется
Шаг 4: d=1 (сортируются элементы, расстояние между которыми один) 5, 1, 6, 8, 13, 34, 23, 47, 65, 52 1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется 1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется 1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется 1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется 1, 5, 6, 8, 13, 34, 23, 47, 65, 52 1, 5, 6, 8, 13, 23, 34, 47, 65, 52 1, 5, 6, 8, 13, 23, 34, 47, 65, 52– массив не меняется 1, 5, 6, 8, 13, 23, 34, 47, 65, 52– массив не меняется 1, 5, 6, 8, 13, 23, 34, 47, 65, 52 1, 5, 6, 8, 13, 23, 34, 47, 52, 65
Сортировка «методом пузырька» Начиная с конца массива сравниваются два соседних элемента (a[n] и a[n-1]). Если выполняется условие a[n-1] > a[n], то значения элементов меняются местами. Процесс продолжается для a[n-1] и a[n-2] и т.д., пока не будет произведено сравнение a[2] и a[1]. Понятно, что после этого на месте a[1] окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются a[3] и a[2]. И так далее. На последнем шаге будут сравниваться только текущие значения a[n] и a[n-1]. Массив: 23, 8, 5, 65, 47, 34, 1, 6 Шаг 1: i1= 23, 8, 5, 65, 47, 34, 1, 6 Шаг 2: i2= 23, 8, 5, 65, 47, 34, 1, 6 5, 8, 23, 65, 47, 1, 34, 6 5, 8, 23, 65, 1, 47, 34, 6 5, 8, 23, 1, 65, 47, 34, 6 5, 8, 1, 23, 65, 47, 34, 6 5, 1, 8, 23, 65, 47, 34, 6 1, 5, 8, 23, 65, 47, 34, 6 Шаг 3: i3= 1, 5, 8, 23, 65, 47, 34, 6 1, 5, 8, 23, 65, 47, 6, 34 1, 5, 8, 23, 65, 6, 47, 34 1, 5, 8, 23, 6, 65, 47, 34 1, 5, 8, 6, 23, 65, 47, 34 1, 5, 6, 8, 23, 65, 47, 34 Шаг 4: i4= 1, 5, 6, 8, 23, 65, 47, 34 1, 5, 6, 8, 23, 65, 34, 47 1, 5, 6, 8, 23, 34, 65, 47 Шаг 5: i5= 1, 5, 6, 8, 23, 34, 65, 47 1, 5, 6, 8, 23, 34, 47, 65
Шейкерная сортировка. Массив: 23, 8, 5, 65, 47, 34, 1, 6 Шаг 1: 23, 8, 5, 65, 47, 34, 1, 6 23, 8, 5, 65, 47, 1, 34, 6 23, 8, 5, 65, 1, 47, 34, 6 23, 8, 5, 1, 65, 47, 34, 6 23, 8, 1, 5, 65, 47, 34, 6 23, 1, 8, 5, 65, 47, 34, 6 1, 23, 8, 5, 65, 47, 34, 6 Шаг 2: 1, 23, 8, 5, 65, 47, 34, 6 1, 23, 5, 8, 65, 47, 34, 6 1, 5, 23, 8, 65, 47, 34, 6 Шаг 3: 1, 5, 23, 8, 65, 47, 34, 6 1, 5, 23, 8, 65, 47, 6, 34 1, 5, 23, 8, 65, 6, 47, 34 1, 5, 23, 8, 6, 65, 47, 34 1, 5, 23, 6, 8, 65, 47, 34 1, 5, 6, 23, 8, 65, 47, 34 Шаг 4: 1, 5, 6, 23, 8, 65, 47, 34 1, 5, 6, 8, 23, 65, 47, 34 Шаг 5: 1, 5, 6, 8, 23, 65, 47, 34 1, 5, 6, 8, 23, 65, 34, 47 1, 5, 6, 8, 23, 34, 65, 47 Шаг 6: 1, 5, 6, 8, 23, 34, 65, 47 1, 5, 6, 8, 23, 34, 47, 65 Сортировка выбором. При сортировке массива a[1], a[2],..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3],..., a[n],... a[j], a[j+1],..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение.
Массив: 23, 8, 5, 65, 47, 34, 1, 6 Шаг 1: 23, 8, 5, 65, 47, 34, 1, 6 1, 8, 5, 65, 47, 34, 23, 6 Шаг 2: 1, 8, 5, 65, 47, 34, 23, 6 1, 5, 8, 65, 47, 34, 23, 6 Шаг 3: 1, 5, 8, 65, 47, 34, 23, 6 1, 5, 6, 65, 47, 34, 23, 8 Шаг 4: 1, 5, 6, 65, 47, 34, 23, 8 1, 5, 6, 8, 47, 34, 23, 65 Шаг 5: 1, 5, 6, 8, 47, 34, 23, 65 1, 5, 6, 8, 23, 34, 47, 65
Сортировка разделением.
1. В исходном неотсортированном массиве выбрать некоторый элемент x = a(k) (барьерный элемент). 2. Переставить элементы массива таким образом, чтобы слева от x оказались элементы массива, меньшие или равные x, а справа элементы массива, большие чем х.
3. Для дальнейшей сортировки необходимо применить п. 1, 2 для каждой из этих частей. И так до тех пор. Пока не останутся подмассивы, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.
Массив: 23, 8, 5, 65, 47, 34, 1, 6 1. Выбираем средний элемент: 23, 8, 5, 65, 47, 34, 1, 6 2. Сортируем вправо от среднего элемента числа больше выбранного, а влево меньше: 23, 8, 5, 65, 47, 34, 1, 6 23, 8, 5, 65, 47, 34, 1, 6 – массив без изменений 23, 8, 5, 65, 47, 34, 1, 6 – массив без изменений 23, 8, 5, 65, 47, 34, 1, 6 – массив без изменений 23, 8, 5, 65, 47, 34, 1, 6 – меняем местами 6 и 65, т.к. 6<34 и 65>34: 23, 8, 5, 6, 47, 34, 1, 65 23, 8, 5, 6, 47, 34, 1, 65– меняем местами 1 и 47, т.к. 1<34 и 47>34: 23, 8, 5, 6, 1, 34, 47, 65 Правая часть упорядочена, теперь выбираем среднее значение для левой части исключая число 34: 23, 8, 5, 6, 1, 34, 47, 65 23, 8, 5, 6, 1, 34, 47, 65 – меняем местами 1 и 23, т.к. 1<5 и 23>5: 1, 8, 5, 6, 23, 34, 47, 65 1, 8, 5, 6, 23, 34, 47, 65 – меняем местами 8 и 5, т.к. 8>5: 1, 5, 8, 6, 23, 34, 47, 65 1, 5, 8, 6, 23, 34, 47, 65 – меняем местами 8 и 6, т.к. 8>6: 1, 5, 6, 8, 23, 34, 47, 65
|
|||||||
|
|
Последнее изменение этой страницы: 2020-12-09; просмотров: 44; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.116.8.110 (0.029 с.) |
