Абдуманнонов С. Сортировка одномерного массива методом пузырька
 Скачать 58.63 Kb.
|
|
МИНИСТЕРСТВО ПО РАЗВИТИЮ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ МУХАММАДА АЛЬ-ХОРАЗМИ САМОСТОЯТЕЛЬНАЯ РАБОТА По предмету: Программирование На тему: Сортировка одномерного массива методом пузырька Выполнил студент группы 0175-21 SAXr заочного отделения: Абдуманнонов с Проверила: Хайдарова М Ташкент 2021 Сортировка одномерного массива методом пузырька Сортировка — перестановка местами объектов в определенном порядке. Известно несколько сотен алгоритмов сортировки и их модификаций. Пусть дана последовательность элементов – A1, А2, …, Аn. Сортировка означает перестановку этих элементов в новом порядке Аk1 , Аk2, …, Akn. Этот порядок соответствует значениям некоторой функции F, такой, что справедливо отношение F(Ak1) < F(Ak2)< ... Как у любого вычислительного процесса у сортировки есть свои критерии для сравнительной оценки качества программы и соответствующего ей алгоритма. Такими критериями являются: объем используемой памяти и время работы программы. Хорошей по критерию памяти считается такая сортировка, при которой данные сортируются в том же самом массиве, где находились исходные данные. При оценке времени сортировки используют два показателя: число сравнений ключей (С), число пересылок данных (М). Хорошими по времени считаются сортировки, в которых число сравнений С=N*Ln(N). К простым, то есть не очень хорошим, относятся такие сортировки, в которых число сравнений пропорционально квадрату размерности N исходного массива С?N2. Следует отметить, что показатели С и М существенно зависят от первоначальной упорядоченности сортируемого массива. Наиболее тяжелым (Мах) считается случай, когда массив упорядочен в обратном порядке. Ниже мы рассмотрим три наиболее известных способа сортировки одномерного массива. Сравнительные временные характеристи ки этих способов приведены в следующей таблице:  Сортировка простым обменом. Метод пузырька. Пример 32. Методом пузырька упорядочить (отсортировать) в порядке возрастания массив из 8 целых чисел (44, 55, 12, 42, 94, 18, 06, 67). Концептуальную модель сортировки рассмотрим на примере восьми целых чисел, которые расположим в первом вертикальном столбце. Вертикальное расположение сортируемого массива наглядно иллюстрирует «всплывание легких элементов (чисел) вверх к поверхности» по мере сортировки массива. Элементы массива рассматриваются попарно снизу-вверх. Если нижний элемент меньше, то они меняются местами. При первом просмотре (проходе) самый «легкий» элемент оказывается самым верхним. Поэтому при втором просмотре его можно уже не рассматривать. В таблице стрелками показаны перемещения элементов массива после каждого прохода.  Элементы всплывают вверх к поверхности в соответствии с их весами, пока не встретят элемент с более малым весом. С каждым проходом наиболее легкий элемент из оставшихся поднимается на свое место, показанное жирными цифрами. Таким образом, нет необходимости на каждом проходе проверять элементы, стоящие выше выделенных, поскольку они уже отсортированы ранее. Начиная с 6 прохода, состояние массива не изменяется, что объясняется начальной упорядоченностью элементов в исходном массиве. Эта программа предназначена для изучения сортировки методом пузырька, поэтому взят массив из восьми целых чисел. Массив заранее известен, следовательно, инициализировать Х[1...8] проще всего в разделе констант. Ввод данных с клавиатуры в этой программе не требуется. Алгоритм программы представляет собой двойной вложенный цикл. Индекс I внешнего арифметического цикла соответствует номеру прохода сортировки. Индекс J это номер элемента в массиве. Для перестановки двух соседних элементов X[J-1] и X[J] местами используется промежуточная рабочая ячейка с идентификатором L. Для качественного обследования используется томография МРТ в Саратове адреса и отзывы указаны на сайте диагностического центра. PROGRAM PR32; CONST X: ARRAY [1.. 8] OF INTEGER = (44, 55,12,42,94,18,06, 67); VAR L, I, J: INTEGER; BEGIN { Вывод на экран исходного массива X } FOR I := 1 ТО 8 DO WRITE(X[I]:5); WRITELN; FOR I := 2 TO 8 DO FOR J:=8 DOWNTO I DO IF X[J-1] > X[J] THEN BEGIN {Переставить X[J-1] с Х[J] местами} L:=X[J-1]; X[J-1]:=X[j]; X[J]:=L END; {IF} { Вывод на экран отсортированного массива X } FOR I := 1 ТО 8 DO WRITE(X[I]:5); WRITELN END.  Сортировка методом пузырька заключается в том, что по массиву осуществляются множественные проходы. На каждом проходе очередной элемент сравнивается со следующим за ним. И если он больше (при сортировке по возрастанию), то элементы массива меняются местами. Таким образом при первом проходе по массиву при сортировке по возрастанию последним в массиве оказывается самое большое значение. При следующем проходе на предпоследнем месте окажется максимальное из оставшихся чисел. Сравнивать последнее и предпоследнее числа нет смысла. Поэтому количество просматриваемых элементов массива на каждом проходе сокращается на 1. Количество проходов равно количеству элементов массива за вычетом единицы, т.к. происходит попарное сравнение. Pascal сортировка пузырьком паскаль const N = 10; var arr: array[1..N] of integer; i, j, k: integer; begin randomize; for i:=1 to N do begin arr[i] := random(256); write (arr[i]:4); end; writeln; for i:=1 to N-1 do for j:=1 to N-i do if arr[j] > arr[j+1] then begin k := arr[j]; arr[j] := arr[j+1]; arr[j+1] := k end; for i:=1 to N do write (arr[i]:4); writeln; end. 97 8 156 88 3 99 217 170 135 133 3 8 88 97 99 133 135 156 170 217 Язык Си #include #define N 10 main() { int a[N], i, j, b; srand(time(NULL)); for (i=0; i< N; i++) { a[i] = rand()%100; printf("%3d", a[i]); } printf("\n"); for (i=0; i < N-1; i++) { for (j=0; j < N-i-1; j++) { if (a[j] > a[j+1]) { b = a[j]; a[j] = a[j+1]; a[j+1] = b; } } } for (i=0; i< N; i++) printf("%3d", a[i]); printf("\n"); } 71 62 25 3 46 61 25 31 56 12 3 12 25 25 31 46 56 61 62 71 Python сортировка пузырьком Python (питон) from random import random a = [0]*10 for i in range(10): a[i] = int(random()*100) print(a) for i in range(9): for j in range(9-i): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] print(a) [42, 9, 95, 78, 59, 14, 50, 79, 54, 84] [9, 14, 42, 50, 54, 59, 78, 79, 84, 95] В Питоне при обмене значений переменных можно обойтись без буферной переменной. Это делается с помощью присваивания в одном выражении. Такая возможность существует, т.к. в Python перед присваиванием в подобных выражениях сначала формируются кортежи. КуМир алг сортировка пузырьком нач цел N = 10 цел таб arr[1:N] цел i,j,k нц для i от 1 до N arr[i] := int(rand(0,100)) вывод arr[i], " " кц вывод нс нц для i от 1 до N-1 нц для j от 1 до N-i если arr[j] > arr[j+1] то k := arr[j] arr[j] := arr[j+1] arr[j+1] := k все кц кц нц для i от 1 до N вывод arr[i], " " кц кон 41 38 95 61 71 1 20 14 83 61 1 14 20 38 41 61 61 71 83 95 Basic-256 dim a(10) for i =0 to 9 a[i] = int(rand()*100) print a[i] + " "; next i for i=0 to 8 for j=0 to 8-i if a[j] > a[j+1] then b = a[j] a[j] = a[j+1] a[j+1] = b endif next j next i for i =0 to 9 print a[i] + " "; next i 6 61 17 0 51 36 43 32 88 6 0 6 6 17 32 36 43 51 61 88 |