Б) алгоритм сортировки методом пузырька

1) Сравнить х(1) и х(2):

· если х(1)>х(2), сделать перестановку

· если х(1)<=х(2), перейти к 2

2) Сравнить х(2) и х(3)

· если х(2)<=х(3), перейти к 3

· если х(2)>х(3), поменять местами х(2) и х(3)

· сравнить х(2) и х(1), сделать перестановку, если она нужна

3) И вообще, если х (i) - последний элемент в упорядоченном списке, то сравнить х (i) и x (i+1)

4) Если х (i)<= х (i+1), установить i= i+ 1 и, если i<= n-1, перейти к 3, в противном случае сортировка закончена.

если х (i)> х (i+1), то

· Поменять местами х (i) и х (i+1)

· Убедиться, что х (i) находится на своем месте в упорядоченном списке

· Установить k=i

5)Сравнить х (k-1) и х (k):

· если x(k) меньше, то сделать перестановку; установить k=k-l и, если k>l, перейти к 5

· если x(k)>=x(k- 1), то перейти к 4

На рис.13 представлен один из возможных алгоритмов сортировки метода “ пузырька ”. Элементы массива сортируются в порядке убывания

for i =1 to n step -1

for j = 1 to i-1

if a(j) < a(j+1) then

swap a(j), a(j+1)

end if

next j

next i

да

нет

да

Рис.13

Пузырьковая сортировка (bubble) может быть выполнена и с помощью следующих подпрограмм

Для выполнения лабораторной работы студент получает задание от преподавателя из вариантов задания по данной работе, составляет блок – схему алгоритм решения, программу на QBASIK, решает задачу на ЭВМ.

В отчет входят:

· математическая постановка задачи;

· блок – схема решения;

· программа на QBASIC;

· результаты решения задачи с той формой распечатки, что требуется по условия задачи.

Пример оформления самостоятельной работы.

Лист № 1.

Задание.

Дан массив а, не содержащий нулевых элементов, из 20 элементов. Посчитать среднее среди отрицательных элементов. Если оно больше заданного числа, положительные элементы исходного массива уменьшить на это число, а отрицательные – увеличить. В новом массиве найти максимальный элемент и его индекс. Результат представить в виде:

Мах =

I max =

Математическая постановка задачи.

Дано: а_i i = 1,20

число р

Определить:

Если a_i > 0

a_i – p если

b_i =

a_i + p если

max{b_i}, i max

b_i если b_i≥ max

max

max если b_i < max

Лист № 2.

Блок – схема поставленной задачи.

Лист № 3.

Программа, выполненная на языке QBASIC.

CLS

DIM 3(1 TO 20), b(1 TO 20)

FOR i = 1 TO 20

PRINT “a(“;i;”)=”;

INPUT “”, a(i)

NEXT i

INPUT “введите заданное число=”; p

max = -10 10

S = 0

K = 0

FOR i = 1 TO 20

IF a(i)<0 THEN

S=S+a(i)

K=k+1

END IF

NEXT i

PRINT: PRINT

IF Sr > p THEN

END IF

FOR i = 1 TO 20

IF a(i)>0 THEN b(i)=a(i)-P

IF a(i)<0 THEN b(i)=a(i)+P

IF b(i) >= max THEN max = b(i); imax = i

NEXT i

PRINT “*********”

PRINT “r/n*Исходный массив*Полученный массив*”

FOR i = 1 TO 20

PRINT USING “*##*######*####*”; i; a(i); b(i)

NEXT i

PRINT “********”

PRINT: PRINT

SLEEP

PRINT “max=”;max

PRINT “imax=”;imax

END

Лист № 4

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

А(1) = 1

А(2) = 2

А(3) = 3

А(4) = 4

А(5) = 5

А(6) = 6

А(7) = 7

А(8) = 8

А(9) = 9

А(10) = 0

А(11) = -1

А(12) = -2

А(13) = -3

А(14) = -4

А(15) = -5

А(16) = -6

А(17) = -7

А(18) = -8

А(19) = -9

А(20) = 20

Введите заданное число = -100

Sr = -5

*п/п *Исходный массив *Полученный массив *

*1 *1 *101 *

*2 *2 *102 *

*3 *3 *103 *

*4 *4 *104 *

*5 *5 *105 *

*6 *6 *106 *

*7 *7 *107 *

*8 *8 *108 *

*9 *9 *109 *

*10 *0 *0 *

*11 *-1 *-101 *

*12 *-2 *-102 *

*13 *-3 *-103 *

*14 *-4 *-104 *

*15 *-5 *-105 *

*16 *-6 *-106 *

*17 *-7 *-107 *

*18 *-8 *-108 *

*19 *-9 *-109 *

*20 *20 *120 *

MAX = 120

IMAX = 20

Не нашли, что искали? Воспользуйтесь поиском: