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

Рассмотрим два способа сортировки одномерного массива.

1. Сортировка одномерного массива методом «пузырька» (случай сортировки по возрастанию). В массиве находят min элемент и меняют его местами с первым элементом. После этого первый элемент из обработки исключается. Теперь в массиве, начиная уже со второго элемента, вновь находят min элемент и меняют его местами со вторым элементом. Каждый раз число обрабатываемых элементов массива уменьшается на единицу. Процесс повторяется до тех пор, пока весь массив не будет упорядочен (рис. 6.2). Блок-схема алгоритма приведена на рис. 6.1.

Hачало

Ввод ak

L t1UKDXHTtVBSKC5JzEtJzMnPS7VVqkwtVrK34+UCAAAA//8DAFBLAwQUAAYACAAAACEAeOu/WsQA AADdAAAADwAAAGRycy9kb3ducmV2LnhtbESPQWsCMRCF70L/Q5iCN01aodjVKKVQUU9WC3ocN9PN 4maybKLGf98IBW8zvDfvezOdJ9eIC3Wh9qzhZahAEJfe1Fxp+Nl9DcYgQkQ22HgmDTcKMJ899aZY GH/lb7psYyVyCIcCNdgY20LKUFpyGIa+Jc7ar+8cxrx2lTQdXnO4a+SrUm/SYc2ZYLGlT0vlaXt2 mXta2eNC7RerAybcrOVYpTpo3X9OHxMQkVJ8mP+vlybXV6N3uH+TR5CzPwAAAP//AwBQSwECLQAU AAYACAAAACEA8PeKu/0AAADiAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnht bFBLAQItABQABgAIAAAAIQAx3V9h0gAAAI8BAAALAAAAAAAAAAAAAAAAAC4BAABfcmVscy8ucmVs c1BLAQItABQABgAIAAAAIQAzLwWeQQAAADkAAAAQAAAAAAAAAAAAAAAAACkCAABkcnMvc2hhcGV4 bWwueG1sUEsBAi0AFAAGAAgAAAAhAHjrv1rEAAAA3QAAAA8AAAAAAAAAAAAAAAAAmAIAAGRycy9k b3ducmV2LnhtbFBLBQYAAAAABAAEAPUAAACJAwAAAAA= ">

k=1, n-1

Вывод ak

конец

p=ak; ak=aj; aj=p

ak>aj

да

нет

L t1UKDXHTtVBSKC5JzEtJzMnPS7VVqkwtVrK34+UCAAAA//8DAFBLAwQUAAYACAAAACEAxHgAksMA AADdAAAADwAAAGRycy9kb3ducmV2LnhtbERP22rCQBB9F/oPywh9qxstaUvqKlVqqfgUmw8YspML ZmfX7DbGv+8WBN/mcK6zXI+mEwP1vrWsYD5LQBCXVrdcKyh+dk9vIHxA1thZJgVX8rBePUyWmGl7 4ZyGY6hFDGGfoYImBJdJ6cuGDPqZdcSRq2xvMETY11L3eInhppOLJHmRBluODQ062jZUno6/RsHz eB5MnvL+06Wbsqi+UjodnFKP0/HjHUSgMdzFN/e3jvOT9BX+v4knyNUfAAAA//8DAFBLAQItABQA BgAIAAAAIQDw94q7/QAAAOIBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1s UEsBAi0AFAAGAAgAAAAhADHdX2HSAAAAjwEAAAsAAAAAAAAAAAAAAAAALgEAAF9yZWxzLy5yZWxz UEsBAi0AFAAGAAgAAAAhADMvBZ5BAAAAOQAAABAAAAAAAAAAAAAAAAAAKQIAAGRycy9zaGFwZXht bC54bWxQSwECLQAUAAYACAAAACEAxHgAksMAAADdAAAADwAAAAAAAAAAAAAAAACYAgAAZHJzL2Rv d25yZXYueG1sUEsFBgAAAAAEAAQA9QAAAIgDAAAAAA== " adj="4803">

j=k+1,n-1

 

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

М1

М2

М1

М1

М2

М3

М1

М2

М3

Мn

М1

М2

М3

Мn

….

 

 

Рис. 6.2. Сортировка одномерного массива методом «пузырька»

2. Метод линейной сортировки одномерного массива. В методе линейной сортировки сравнивают значения каждой пары соседних элементов:

Если два соседних элемента не упорядочены, то их меняют местами (выполняется перестановка элементов массива). Если не производилось ни одной замены, это означает, что массив упорядочен и вычисления заканчивают. Если не все пары соседних элементов упорядочены сравнение и перестановку проводят снова.

Рассмотрим алгоритм линейной сортировки одномерного массива (рис. 6.3):

1) число k – счетчик для подсчета упорядоченных пар приравнивают нулю;

2) сравнивают первый элемент со вторым, если они не упорядочены то их меняют местами, иначе увеличивают k на 1;

3) сравнивают второй элемент с третьим, если они не упорядочены, тогда их меняют местами, иначе увеличивают k на 1;

4) процесс продолжается до n -1 (n – размерность массива);

5) анализируют значение k:

- если k >= n -1 это означает, что замен не было (т.е. последовательность упорядочена) и вычисления завершают;

- если k < n -1 возвращаются к шагу 1.

Пример. Дан массив а (n) упорядочить его в порядке возрастания методом линейной сортировки, n – размерность массива задается константой в программе.

Начало

Ввод ai

k=0

j=1, n-1

k>=n-1

k=k+1

Вывод ai

конец

да

нет

p=ai; ai=ai+1; ai+1=p

да

нет

(while, repeat)

 

 

Рис.6.3. Блок-схема метода линейной сортировки одномерного массива

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

for k:=1 to n-1 do

for j:=k+1 to n do

if a[k]>a[j] then

begin

p:=a[k];

a[k]:=a[j];

a[j]:=p;

end;

{Метод линейной сортировки одномерного массива}

repeat

k:=0;

for i:=1 to n-1 do

if a[i]>a[i+1] then

begin

p:=a[i];

a[i]:=a[i+1];

a[i+1]:=p;

end

else

k:=k+1;

until k>=n-1;