Паскаль
<<  Одномерные массивы Матрицы  >>
Сортировка элементов одномерного массива
Сортировка элементов одномерного массива
Понятие массива
Понятие массива
Одномерный массив
Одномерный массив
Сортировка элементов в массиве
Сортировка элементов в массиве
Способы сортировки массива
Способы сортировки массива
Сортировка массива методом «пузырька»
Сортировка массива методом «пузырька»
Принцип сортировки массива
Принцип сортировки массива
Таблица сортировки массива
Таблица сортировки массива
Блок-схема сортировки массива
Блок-схема сортировки массива
Сформировать массив
Сформировать массив
Сортировка массива методом «перестановки»
Сортировка массива методом «перестановки»
Таблица сортировки
Таблица сортировки
Сортировка массива
Сортировка массива
Блок-схема сортировки массива методом «перестановки»
Блок-схема сортировки массива методом «перестановки»
Значения элементов массива
Значения элементов массива
Задать значения
Задать значения
Сортировка массива методом «вставки»
Сортировка массива методом «вставки»
Массив из восьми элементов
Массив из восьми элементов
Блок-схема сортировки массива методом «вставки»
Блок-схема сортировки массива методом «вставки»
Фрагмент программы
Фрагмент программы
Сортировка массива по возрастанию
Сортировка массива по возрастанию
Схема сортировки массива методом «выбора»
Схема сортировки массива методом «выбора»
Быстрая сортировка
Быстрая сортировка
Выбор опорного элемента
Выбор опорного элемента
Алгоритм выбора опорного элемента
Алгоритм выбора опорного элемента
Разделение массива
Разделение массива
Сформировать массив из 10 элементов
Сформировать массив из 10 элементов
Результат работы программы
Результат работы программы
Метод быстрой сортировки
Метод быстрой сортировки
Презентация «Сумма элементов одномерного массива». Размер 268 КБ. Автор: Андрюшина.

Загрузка...

Сумма элементов одномерного массива

содержание презентации «Сумма элементов одномерного массива.ppt»
СлайдТекст
1 Сортировка элементов одномерного массива

Сортировка элементов одномерного массива

Тема: «Сортировка элементов одномерного массива» Автор: Андрюшина А.В. Школа №616 г. Зеленоград 2009 г.

2 Понятие массива

Понятие массива

А. Понятие массива. 1 2 3 4 5 6 7 8 9. -5 14 7 10 32 9 -45 34 16. Ряд однотипных данных, имеющих имя, порядковый номер и численное значение называются массивами.

3 Одномерный массив

Одномерный массив

Пример: Сформировать одномерный массив из 9 элементов и распечатать его.

4 Сортировка элементов в массиве

Сортировка элементов в массиве

Сортировка элементов в массиве. Сортировка представляет собой процесс упорядочения элементов в массиве по возрастанию или убыванию их значений. Например: Массив Х из n элементов будет отсортирован в порядке возрастания значений его элементов, если X[1] <= X[2] <= … <= X [n] И в порядке убывания, если X[1] >= X[2] >= … >= X [n].

5 Способы сортировки массива

Способы сортировки массива

Способы сортировки массива:

6 Сортировка массива методом «пузырька»

Сортировка массива методом «пузырька»

Сортировка массива методом «пузырька». Сортировка методом пузырька использует метод обменной сортировки и основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов.

7 Принцип сортировки массива

Принцип сортировки массива

Принцип сортировки массива по возрастанию методом «пузырька». Сравним первый элемент массива со вторым. Если первый окажется больше второго, то поменяем их местами. Те же действия выполним для второго и третьего, третьего и четвёртого, I-го и (I + 1)-го, (n – 1)-го и n-го элементов. В результате этих действий самый большой элемент станет на последнее (n-е) место. Теперь повторим данный алгоритм сначала, но последний (n-й) элемент, рассматривать не будем, так как он уже занял своё место. После проведения данной операции самый большой элемент оставшегося массива встанет на (n - 1) место. Так повторяем до тех пор, пока не упорядочим весь массив.

8 Таблица сортировки массива

Таблица сортировки массива

Таблица сортировки массива по возрастанию. Сортировка массива А состоящего из 5 элементов, по возрастанию методом «пузырька». Номер элемента. Номер элемента. Номер элемента. Номер элемента. Номер элемента. Номер элемента. Исходный массив. 7. 3. 5. 4. 2. Первый просмотр. 3. 5. 4. 2. 7. Второй просмотр. 3. 4. 2. 5. 7. Третий просмотр. 3. 2. 4. 5. 7. Четвертый просмотр. 2. 3. 4. 5. 7. 1. 2. 3. 4. 5.

9 Блок-схема сортировки массива

Блок-схема сортировки массива

Блок-схема сортировки массива методом «пузырька».

10 Сформировать массив

Сформировать массив

Сформировать массив из n элементов и упорядочить элементы в массиве по возрастанию их значений (метод «пузырька»).

11 Сортировка массива методом «перестановки»

Сортировка массива методом «перестановки»

Сортировка массива методом «перестановки».

12 Таблица сортировки

Таблица сортировки

Таблица сортировки массива по убыванию методом «перестановки». 1. 7. 14. 14. 14. 14. 2. 9. 9. 9. 9. 9. 3. 1. 1. 1. 7. 7. 4. 14. 7. 7. 1. 5. 5. 5. 5. 5. 5. 1. Перестановки. Перестановки. Перестановки. Перестановки. Первая. Вторая. Третья. Четвертая. № Элементов. Значения элементов массива. Если n элементов, то количество перестановок n2.

13 Сортировка массива

Сортировка массива

Перестановки. Перестановки. Перестановки. Перестановки. Таблица сортировка массива по возрастанию методом «перестановки». 1. 7. 1. 1. 1. 1. 2. 9. 9. 5. 5. 5. 3. 1. 7. 7. 7. 7. 4. 14. 14. 14. 14. 9. 5. 5. 5. 9. 9. 14. Первая. Вторая. Третья. Четвертая. № Элементов. Значения элементов массива. Если n элементов, то количество перестановок n2.

14 Блок-схема сортировки массива методом «перестановки»

Блок-схема сортировки массива методом «перестановки»

Блок-схема сортировки массива методом «перестановки». i:=1. J:=i+1. Нет. Да. a[i]>a[j]. Pr:=a[j] A[j:]=a[i] A[i]:=pr. j:=j+1. Нет. Да. j < n. i:=i+1. Да. i< n-1.

15 Значения элементов массива

Значения элементов массива

Сформировать массив А размерностью 10. Задать значения элементов массива с помощью ГСЧ . Расположить элементы массива по возрастанию (метод перестановки).

16 Задать значения

Задать значения

Сформировать массив А размерностью 10. Задать значения элементов массива с помощью ГСЧ . Расположить элементы массива по убыванию (метод перестановки).

17 Сортировка массива методом «вставки»

Сортировка массива методом «вставки»

Сортировка массива методом «вставки». Сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум. Четвёртый элемент помещают в список из уже упорядоченных трёх элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.

18 Массив из восьми элементов

Массив из восьми элементов

ПРИМЕР : Дан массив из восьми элементов. Первые шесть уже упорядочены, а седьмой нужно вставить между вторым и четвёртым. Сохраним его во вспомогательной переменной Х. Пятый элемент переместим на место шестого, четвёртый – на место пятого, а третий на место четвёртого. То есть выполнили сдвиг элементов массива на одну позицию вправо. Запишем содержимое вспомогательной переменной в третью позицию.

19 Блок-схема сортировки массива методом «вставки»

Блок-схема сортировки массива методом «вставки»

Блок-схема сортировки массива методом «вставки». 1. Ввод n. Yi. i=1,n. Yj+1=Yj. J=j -1. i=2,n. Yj+1=X. X=Yi. i=1,n. j=i -1. Yj. Конец. Начало. 1.

20 Фрагмент программы

Фрагмент программы

Фрагмент программы, реализующей сортировку массива методом вставки. For i:=1 to n do Begin x:=y[i];{Сохраним текущий элемент массива.} {В переменной j будем хранить номера элементов, предшествующих текущему.} J:=i-1; {Сдвиг массива на одну позицию в право до тех пор, пока} While (x<y[j]) and (j>0) do Begin y[j+1] :=y[j]: j:=j-1; End; {Запись текущего элемента на соответствующую позицию,} {то есть перед элементами, превышающими его.} y[j+1]:=x; end;

21 Сортировка массива по возрастанию

Сортировка массива по возрастанию

Сортировка массива по возрастанию методом «выбора». Найдем в массиве самый большой элемент и поменяем его местами с последним элементом. Повторим алгоритм поиска максимального элемента, уменьшив количество просматриваемых элементов на единицу и поменяем его местами с предпоследним элементом. Описанную выше операцию поиска проводим до полного упорядочивания элементов в массиве.. Для упорядочивания массива по убыванию необходимо перемещать минимальный элемент.

22 Схема сортировки массива методом «выбора»

Схема сортировки массива методом «выбора»

Блок – схема сортировки массива методом «выбора».

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

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

Быстрая сортировка. Принцип работы. Один из самых быстрых алгоритмов, позволяющих достигать производительности ~ O(n*log n). 1. В исходной последовательности выбирается некоторый опорный элемент a[i]. 2. Пробегаемся по всей последовательности и элементы, меньшие, либо равные a[i] располагаем слева от него, большие - справа. Эту же самую процедуру рекурсивно запускаем для 2-х полученных половинок. <= a[i] a[i] >=a[i] Т.е. в 2-х полученных последовательностях слева и справа от выбранного на первом шаге элемента - также выбираем некоторый опорный ключ и перебрасываем соответствующие большие и меньшие чем он элементы. 4. В уже 4-х полученных последовательностях - тоже самое. Пока не получим последовательности, состоящие лишь из одного элемента. После выполнения всех рекурсий в результате получаем отсортированную исходную последовательность.

24 Выбор опорного элемента

Выбор опорного элемента

Выбор опорного элемента. При быстрой сортировке выбор опорного элемента на каждом шаге играет очень значительную роль, т.к. от этого зависит суммарная скорость выполнения всего алгоритма при различных условиях сортировки. Варианты выбора опорного элемента. Частичная упорядоченность элементов. Наиболее хаотичное расположение элементов. Самые распространенные варианты: • выбор середины отрезка • выбор случайного элемента последовательности • выбор первого элемента последовательности.

25 Алгоритм выбора опорного элемента

Алгоритм выбора опорного элемента

Алгоритм выбора опорного элемента последовательности. Этот алгоритм был впервые описан К. А. Р. Хоаром в его классической статье «Быстрая сортировка».

26 Разделение массива

Разделение массива

Разделение массива. 4. 9. 7. 6. 2. 3. 8. i. j. 4. 9. 7. 6. 2. 3. 8. 4. 3. 7. 6. 2. 9. 8. 4. 3. 2. 6. 7. 9. 8. Чтобы отсортировать массив, мы разделяем его на два под массива и сортируем каждый из них рекурсивно. Например, для сортировки массива из семи элементов: Положение первого обмена. Исходное положение. i. j. i. Положение второго обмена. j. i. j. Положение третьего обмена.

27 Сформировать массив из 10 элементов

Сформировать массив из 10 элементов

Пример: Сформировать массив из 10 элементов. Значения задать ГСЧ. Отсортировать массив методом «быстрой сортировки». program Quitsort; uses crt; Const N=10; Type Mas=array[1..n] of integer; var a: mas; k: integer; function Part(l, r: integer):integer; var v, i, j, b: integer; begin V:=a[r]; I:=l-1; j:=r; repeat repeat dec(j) until (a[j]<=v) or (j=i+1); repeat inc(i) until (a[i]>=v) or (i=j-1); b:=a[i]; a[i]:=a[j]; a[j]:=b; until i>=j; a[j]:=a[i]; a[i]:= a[r]; a[r]:=b; part:=i; end; procedure QuickSort(l, t: integer); var i: integer; begin if l<t then begin i:=part(l, t); QuickSort(l,i-1); QuickSort(i+1,t); end; end; begin clrscr; randomize; for k:=1 to 10 do begin a[k]:=random(100); write(a[k]:3); end; QuickSort(1,n); writeln; for k:=1 to n do write(a[k]:3); readln; end.

28 Результат работы программы

Результат работы программы

Результат работы программы.

29 Метод быстрой сортировки

Метод быстрой сортировки

Заключение. Метод быстрой сортировки позволяет существенно сократить количество операций. Например: Все предыдущие методы требовали N2 операций, где N – количество элементов. Метод быстрой сортировки требует в среднем N*Log2N операций. В случае N=100, выигрыш составляет порядка 100 раз.

«Сумма элементов одномерного массива»
Сайт

5informatika.net

115 тем
5informatika.net > Паскаль > Сумма элементов одномерного массива.ppt