Презентация на тему Сортировка и поиск. Пузырьковая сортировка

снизу вверх (от последнего элемента к первому), сравнивая каждый

элемент массива с расположенным выше, и если верхний больше, то меняет их местами. При этом проходе наименьший элемент – "всплывет" наверх. Операция продолжается пока наименьший элемент не станет первым.
Затем операция повторяется над подмножеством массива с номерами (индексами) элементов от 2 до N, затем над подмножеством от 3 до N и так до подмножества N-1, N. То есть, до тех пор пока массив не будет отсортирован по возрастанию элементов.
(При формировании условия сравнения "наибольший наверх" будет происходить сортировка по убыванию элементов массива).

На каждом шаге происходит три перестановки значений элементов.

Сортировка

И+ПРГ

С.
Сортировка
И+ПРГ

методом "пузырька" – по возрастанию
#include
#include
#define sz 5

// размерность массива
void main ()
{ int a[sz]; /*массив целых чисел*/
int i; //счетчик циклов сортировки
int buf; // буфер, исп. при обмене элементов массива
int k; // текущий индекс элемента массива
printf ("\nВведите в одной строке %i", sz);
printf (" целых чисел и нажмите Enter\n");
printf ("-> ");
for (k = 0; k < sz; k++) scanf ("%i", &a[k]);
// Сортировка
for (i = 0; i < sz-1; i++)
{
for (k = sz-1; k > i; k--)
{
if (a[k-1] > a[k])
{
// Меняем местами k-тый и k-1 элементы
buf = a[k-1]; a[k-1] = a[k]; a[k] = buf;
}
}
}
// Цикл сортировки закончен
// Вывод отсортированного массива
printf ("Отсортированный массив\n");
for (k = 0; k}

Сортировка

И+ПРГ

Пузырьковая сортировка

элементов. Алгоритм выборочной сортировки устраняет этот недостаток, здесь элемент

сразу занимает свою конечную позицию.

Выборочная сортировка – происходит следующим образом:
1. Просматривается весь первичный массив, определяется наименьший (наибольший) элемент массива и затем осуществляется единственный обмен в текущем массиве.
2. Потом просматривается массив-подмножество без наименьшего (наибольшего) элемента, определяется наименьший (наибольший) элемент подмножества и снова осуществляется единственный обмен в текущем подмножестве массива.
3. Шаг 2 повторяется пока весь массив не будет отсортирован.

Сортировка

И+ПРГ

С.
Сортировка
И+ПРГ

выборочн. методом
#include
#include
#define sz 5 // размерность

массива
void main ()
{ int a[sz]; // массив целых чисел
int i; // № элем., от которого ведется поиск мин. элем.
int min; // № мин. элем. в части мас. от i до конца мас.
int j; // № элемента сравниваемого с мин.
int buf; // буфер, исп. при обмене элементов массива
int k; // индекс для ввода и вывода
printf ("\nВведите в одной строке %i", sz);
printf (" целых чисел и нажмите Enter\n");

for (k=0; k // Сортировка
for (i = 0; i < sz-1; i++)
{ // Поиск мин. элем. в части мас. от a[i] до a[sz]
min = i; for (j = i+1; j < sz; j++)
if (a[j] < a[min]) min = j;
// Меняем местами a[min] и a[i]
buf = a[i]; a[i] = a[min]; a[min] = buf;
}
// Цикл сортировки закончен
// Вывод отсортированного массива
printf ("Отсортированный массив\n");
for (k = 0; k}

Сортировка

И+ПРГ

Выборочная сортировка

выборочная сортировка сравнительно неэффективны.
Среднее время работы этих алгоритмов

пропорционально N2
Существуют более быстрые методы сортировки: быстрая сортировка (Quicksort) и сортировка слиянием (метод Шелла).
Среднее время работы этих методов пропорционально N*log2(N)


Зависимость времени сортировки от количества элементов массива (N) и
мощности алгоритма

Сортировка

И+ПРГ

– Quicksort – Метод сортировки разделением:
Из массива выбирается опорный

элемент P.
Сравнивая элементы массива с P и разделяем (сортируем) массив на 2-а подмассива (подмножества). Слева от P элементы меньшие и равные P, а справа – большие или равные.
Для обоих подмножеств, если в них больше 1-го элемента, проделывается та же процедура.
Процесс повторяются для каждой части массива пока он не будет отсортирован.

Опорный элемент выбирается или случайным образом, или как среднее некоторого количества значений массива (например, первого и последнего).

Сортировка

И+ПРГ

J.
Устанавливаем начальные значения индексов I=1 и J=N.

Выбираем опорный элемент P = M[K], где K = (I +J) / 2.
Сравниваем M[I] <= P, если ДА, то увеличиваем I (I=I+1).
Затем сравниваем M[J] >= P, если ДА, то уменьшаем J (J=J-1).
Если НЕТ и I<=J, то меняем местами M[I] и M[J].
Повторяем шаги 4-6 пока I<=J.
В результате массив разделяется на 2-е части, слева от P элементы меньше или равны P, а справа – больше или равны.
Над каждой частью (подмножеством) массива повторяем шаги 2-7. Получаем 4-е подмножества.
Над каждым подмножеством повторяем шаги 2-7. Выполняем эти операции пока массив не будет отсортирован.

Быстрая сортировка (разделением):

Алгоритм быстрой сортировки

Сортировка

И+ПРГ

2. Уст. нач. знач. I=1 и J=N.

3. Выб. Опор.элем. P = M[(M[1]+M[N])/2].
4. Сравн. M[I] <= P, если ДА, то I=I+1.
5. Сравн. M[J] >= P, если ДА, то J=J-1.
6. Если НЕТ и I<=J, то меняем местами M[I] и M[J].
7. Повторяем шаги 2-6 пока I<=J.
8. Массив раздел. на 2-е части, слева от P элементы <= P, а справа >= P.
9. Над кажд. подмнож. мас. повт. шаги 2-7. Получ. 4 подмнож.
10. Над кажд. подмнож. повт. шаги 2-7. Вып. эти операции пока массив не будет отсортирован.

Пример:
1-2. {5 2 7 2 13 3 8 15 19}
3. P=13
4-7. {5 2 7 2 13 3 8 15 19} - меняем местами 13 и 8 =
{5 2 7 2 8 3 13 15 19}
8. Массив разделен на две части по 13.
9-10. Сортируем подмножество
{5 2 7 2 8 3 13 15 19}
2-7. P=7 -> {5 2 7 2 8 3 13 15 19} =
{5 2 3 2 8 7 13 15 19} –
P=2 -> {5 2 3 2 8 7 13 15 19} =
{2 2 3 5 8 7 13 15 19} –
P=8 -> {2 2 3 5 8 7 13 15 19} =
{2 2 3 5 7 8 13 15 19}

Нарисовать алгоритм быстрой сортировки.

Алгоритм быстрой сортировки

Сортировка

И+ПРГ

каждого подмножества – прямой смысл реализовать эту сортировку в

виде рекурсивной функции

Сортировка

И+ПРГ

быстрой сортировки на С.
Сортировка
И+ПРГ

быстрой сортировки
{ long i, j; int p,

temp;
// Инициализация нижней границы
i = Low;
// Инициализация верхней границы
j = High;
// опорный элемент
p = array[(int) (Low+High)/2];
do { while (array[i] < p) i++;
while (array[j] > p) j--;
if (i<=j) // Если верно, то обмен
{ temp = array[i]; array[i] = array[j];
array[j] = temp; i++; j--; } }
while (i<=j); // пока индексы не пересекутся

if (j > Low) quicksort (j, Low);
/* Если подмассив [j, Low] более одного элемента, он сортируется функцией quicksort */
if (High > i) quicksort (High, i);
// Аналогично для [High, i]
}

C / C++

Сортировка

И+ПРГ

Быстрая сортировка

C / C++

#include
#include
int array[10000]; // Объявление массива
/* Функция - Быстрая сортировка
………………………………………… */
main() // Главная функция
{ int i; int size; // количества элементов
cout << "\n Введите количество элементов сортируемого массива size = ";
cin >> size;
for (i=0; i> array[i];
// Чтение очередного элемента массива
for (i=0; i cout << array[i] << " ";
quicksort (size-1, 0);
// Вывод отсортированного массива
cout << "\n
Отсортированный массив\n ";
for (i=0; i cout << array[i] << " ";
return 0;
}

сравнении элементов массива, разделен-ных одинаковым расстоянием, таким образом, чтобы

элементы были упорядочены по расстоянию. Затем это расстояние делится пополам и процесс повторяется.

Алгоритм сортировки Шелла:

В этом методе первоначально рассматриваются элементы отстоящие друг от друга на расстояние d=[n/2], где [ ] - операция взятия целой части, и n - количество элементов исходного массива.
На следующих шагах d меняется по закону d=[d/2], при d=1 метод Шелла вырождается в метод стандартного обмена ("Метод Пузырка")

Сортировка

И+ПРГ

- сравниваем 6 и 8 ->
{6,2,4,8,3,9} - сравниваем 3

и 2, переставляем ->
{6,3,4,8,2,9} - сравниваем 4 и 9 ->
далее d=[d/2]=[3/2]=1.
И алгоритм выродился в метод "Пузырька"

В этом примере не очень видна эффективность метода, но представьте, что вы сортируете 1000 элементов. Этот метод обеспечивает более быстрое перебрасывание больших элементов вправо и меньших влево, чем метод "Пузырька" и этим обеспечивает большее быстродействие.

Сортировка методом Шелла

Сортировка

И+ПРГ

#define size 20

int mass[size];

// сортировка методом Шелла
void ShellSort(int

n, int mass[])
{
int i, j, step, tmp;
for (step = n / 2; step > 0; step /= 2)
for (i = step; i < n; i++)
{ tmp = mass[i];
for (j = i; j >= stestep)
{ if (tmp < mass[j - step])
mass[j] = mass[j - step];
else break;
}
mass[j] = tmp; }
}
см. продолжение

продолжение
int main()
{
srand(time(NULL));
// ввод элементов массива
for (int i = 0; i < size; i++)
{
mass[i]=rand() % 100;
printf ("%i ", mass[i]);
}
// сортировка методом Шелла
ShellSort(size, mass);
// вывод отсортированного массива на экран
printf("отсортированный массив:\n");
for (int i = 0; i < size; i++)
printf(%d ", mass[i]);
return 0;
}

одна из важнейших задач обработки данных.
Для решения задачи

поиска необходимо, чтобы данные в памяти ЭВМ были организованы определенным образом. Основные способы организа-ции данных: массивы элементов одинакового типа, структуры данных, линейные списки, деревья, произвольные графы.
Алгоритмы поиска существенно зависят от способа организации данных.
Рассмотрим алгоритмы поиска в МАССИВАХ:
а) последовательный (линейный) поиск -- простейший метод поиска элемента, находящегося в неупорядоченном массиве данных, это последовательный просмотр каждого элемента массива, продолжающийся до тех пор, пока не будет найден желаемый элемент. Если просмотрен весь массив, но элемент не найден – значит он отсутствует в массиве. Для последовательного поиска в среднем требуется (N+1)/2 сравнений, а в худшем N. Линейный поиск может применяться и для упорядоченных (отсортированных) массивов, НО эффективнее использовать:
б) бинарный (двоичный, дихотомический, логарифмический) поиск – он состоит в разделении упорядоченного массива пополам, определении в какой половине находится искомый элемент, затем это половина снова разделяется пополам и так пока полученное подмножество из одного элемента не станет равным искомому. Для бинарного поиска в худшем случае требуется log2(N) сравнений.

И+ПРГ

#include
#define size 5 // Размерность массива
/* Функция последовательного

поиска,
возвращает индекс искомого элемента массива */
int seq_search (int items[], int count, char key)
{ int t;
for (t=0; t < count; ++t)
if (key == items[t])
return t; // элемент найден
return -1; // элемент не найден
}
main()
{ int array[size], N; // массив
int k, i; // k-искомый элемент
cout << "\n Введите " << size << " элемента(ов), после
ввода каждого элемента -> Enter\n";
for (i=0; i> array[i]; // Ввод элемента
cout << "Введенный массив\n";
for (i=0; i cout << "\n Введите искомый элемент массива - ";
cin >> k;
N=seq_search (array, size, k); // Вызов функции
if (N==-1) cout << "Такого элемента в массиве нет";
else
cout <<"\nНомер искомого элемента в массиве–"< return 0;
}