- •Код процедуры быстрой сортировки
- •Способ выбора опорного элемента
- •Эффективность алгоритма
- •Задача сортировки данных. Определения:
- •Примеры:
- •Задача сортировки данных. Определения:
- •Примеры:
- •Алгоритм сортировки обменом.
- •Задача сортировки данных. Определения:
- •Примеры:
- •Код процедуры сортировки по методу Шелла
- •Задача сортировки данных. Определения:
- •Примеры:
- •Идея метода
- •Рекурсивный характер алгоритма
- •Алгоритм:
- •Пирамидальная сортировка:
- •Две формы хеширования
- •Выбор хеш-функции
- •Выбор хеш-функции в методе деления
- •Выбор хеш-функции в методе умножения
Задача сортировки данных. Определения:
Сортировкой называется упорядочение множества однотипных объектов по тому или иному признаку
Признак, по которому осуществляется упорядочение объектов, называется ключом сортировки
Примеры:
При составлении списка студентов их фамилии располагаются в алфавитном порядке
Мастерская по ремонту бытовой техники выполняет заявки на обслуживание в порядке их поступления – заявки упорядочиваются по времени
Порядок доставки товара торговым предприятием может определяться объемом торговой сделки – заказы будут сортироваться по стоимости
Сортировкой одномерного массива называется упорядочение значений его элементов по возрастанию или убыванию.
Простые алгоритмы сортировки.
Определение:
В эту группу входят три алгоритма, которые реализуют методы сортировки, известные как метод выбора, метод включений и метод обмена (пузырька).
Сравнение методов
Все три алгоритма имеют, в среднем, одинаковую эффективность и выбор одного из них может определяться особенностями задачи, а также личными пристрастиями программиста.
Алгоритм сортировки выбором.
Основная идея этого метода заключается в последовательном формировании отсортированной части массива путем добавления в ее конец очередного элемента, выбранного в его неотсортированной части.
const int N = 10;
void main()
{ int i, j, nMin, A[N], c;
// здесь нужно ввести массив A
for ( i = 0; i < N-1; i ++ )
{ nMin = i; // ищем минимальный, начиная с A[i]
for ( j = i+1; j < N; j ++ ) ;
if ( A[j] < A[nMin] ) nMin = j;
if ( nMin != i ) // если минимальный не стоит на своем месте,…
{ c = A[i]; A[i] = A[nMin]; A[nMin] = c; } // ставим его на место
}
printf("\n Отсортированный массив:\n");
for ( i = 0; i < N; i ++ )
printf("%d ", A[i]);
}
8.Задача сортировки данных. Сортировка одномерных массивов. Простые алгоритмы сортировки. Алгоритм сортировки включениями.
Задача сортировки данных. Определения:
Сортировкой называется упорядочение множества однотипных объектов по тому или иному признаку
Признак, по которому осуществляется упорядочение объектов, называется ключом сортировки
Примеры:
При составлении списка студентов их фамилии располагаются в алфавитном порядке
Мастерская по ремонту бытовой техники выполняет заявки на обслуживание в порядке их поступления – заявки упорядочиваются по времени
Порядок доставки товара торговым предприятием может определяться объемом торговой сделки – заказы будут сортироваться по стоимости
Сортировкой одномерного массива называется упорядочение значений его элементов по возрастанию или убыванию.
Простые алгоритмы сортировки.
Определение:
В эту группу входят три алгоритма, которые реализуют методы сортировки, известные как метод выбора, метод включений и метод обмена (пузырька).
Сравнение методов
Все три алгоритма имеют, в среднем, одинаковую эффективность и выбор одного из них может определяться особенностями задачи, а также личными пристрастиями программиста.
Алгоритм сортировки включениями.
Как и в предыдущем методе, отсортированная часть массива формируется путем последовательного добавления в нее элементов из его неотсортированной части.
Однако теперь в качестве очередного берется первый элемент неотсортированной части.
Место его размещения в отсортированной части выбирается так, чтобы сохранить уже имеющийся там порядок сортировки.
const int N = 10;
void main()
{ int i, j, nMin, A[N], c;
// здесь нужно ввести массив A
for ( i = 1; i < N; i ++ )
{ c = A[i];
j = i -1; // ищем минимальный, начиная с A[i]
while (j > =0 && A[j] > c) A[j+1] = A[j--];
A[j+1] = c;
}
printf("\n Отсортированный массив:\n");
for ( i = 0; i < N; i ++ )
printf("%d ", A[i]);
}
9.Задача сортировки данных. Сортировка одномерных массивов. Простые алгоритмы сортировки. Алгоритм сортировки обменом.
