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

↑

▷ Содержание

⇐ ПредыдущаяСтр 9 из 14Следующая ⇒

Этот метод также называют методом пузырька. Его называют так потому, что в процессе выполнения сортировки более «лёгкие» элементы (элементы с заданным свойством, например максимальные) мало-помалу всплывают на «поверхность» (оказываются на своём месте).

Суть метода: организация упорядоченного списка элементов, в который на соответствующие им места добавляются один за другим неотсортированные элементы. Для реализации этого метода элементы массива просматриваются в направлении от меньших значений индекса к большим, сравниваются очередные два элементы, индексы которых отличаются на 1. Если эти элементы между собой не упорядочены, то производится их взаимный обмен. На следующем шаге рассматривается меньшее количество элементов массива. И так до тех пор, пока не будут проанализированы все элементы массива. 

Упорядочим массив {2, 4,10,11,0,9}.

Первый просмотр: рассматривается весь массив.

2, 4, 10, 11, 0, 9 i=0

2<4

2, 4, 10, 11, 0, 9 i=1

4<10

2, 4, 10, 11, 0, 9 i=2

   10<11

2, 4, 10, 11, 0, 9 i=3

        11>0

2, 4, 10, 0, 11, 9 i=4

            11>9

2, 4, 10, 0, 9, 11 результат просмотра – максимальный элемент на своём месте.   

Второй просмотр: рассматривается часть массива с нулевого до предпоследнего элемента.

2, 4, 10, 0, 9, 11 i=0

2<4

2, 4, 10, 0, 9, 11 i=1

4<10

2, 4, 10, 0, 9, 11 i=2

   10>0

2, 4, 0, 10, 9, 11 i=3

       10>9

2, 4, 0, 9, 10, 11 10- на своём месте.   

Третий просмотр: рассматривается часть массива с нулевого до третьего элемента.

2, 4, 0, 9, 10, 11 i=0

2<4

2, 4, 0, 9, 10, 11 i=1

4>0

2, 0, 4, 9, 10, 11 i=2

   4<9

2, 0, 4, 9, 10, 11 9- на своём месте.   

Четвёртый просмотр: рассматриваемая часть массива содержит три первых элемента.

2, 0, 4, 9, 10, 11 i=0

2>0

0, 2, 4, 9, 10, 11 i=1

2<4

0, 2, 4, 9, 10, 11 4- на своём месте.    

Пятый просмотр: рассматриваем последнюю пару элементов.

0, 2, 4, 9, 10, 11 i=0

0<2

0, 2, 4, 9, 10, 11          

При сортировке методом пузырька выполняется N-1 просмотров, причём i –ом просмотре производится N – i сравнений. Общее количество сравнений: C= N*(N-1)/2.  

  // переменные: a- исходный массив;

 //       i,k- параметры циклов;

 //       n- количество обрабатываемых элементов массива;

//       x-вспомогательная переменная;

#include <stdio.h>

#include <conio.h>

void main()

{

 int i,n,k;

 float x,a[100];

 clrscr();

 printf("введите количество элементов массива ");

 scanf("%d",&n);

printf("введите %d чисел\n ",n);

 for (i=0; i<n; i++)

scanf("%f",&a[i]);

 printf(" исходный массив: ");

 for (i=0; i<n; i++)

printf("%8.2f",a[i]);

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

 for (i=0; i<n-1; i++)

for (k=0; k<n-i; k++)

if(a[k]>a[k+1])

{ x=a[k];

a[k]=a[k+1];

a[k+1]=x;

}

 // вывод результата

 for (i=0; i<n; i++)

 { if (i%5==0) printf("\n");

printf(" %8.2f",a[i]);

 }

 getch();

 }

Сортировки методом простых вставок (метод прямого включения).

Сортировка этим методом производится последовательно шаг за шагом. На i -ом шаге считается, что часть массива, содержащая первые i -1 элементов, уже упорядочена, то есть А[0]£ A[1]£... £A[i-1].Далее берётся i -й элемент, и для него подбирается место в отсортированной части массива, такое, что после вставки упорядоченность не нарушается, то есть требуется найти такое j (0£ j £ i-1), что А[j]£ A[i]<A[j+1] (при j=0 элемент ставится на первое место, а при j=i-1 он остаётся на своём месте). Затем выполняется вставка элемента A[i] на место j. На каждом шаге отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить N-1 шаг.

Рассмотрим этот процесс на примере.

Пусть требуется отсортировать по возрастанию массив, состоящий из 9 элементов.

6 8 13- рассматриваемая часть массива;

6 13 - место вставки;

8        - вставляемый элемент.

1-й шаг. 13  6  8 11 1 5 9 15 7 Рассматриваем часть массива из одного элемента 13. Вставляем 1-ый элемент массива 6так, чтобы упорядоченность сохранилась. Так как 6<13, записываем 6 на 0-е место. Отсортированная часть массива содержит два элемента (6,13).

2-й шаг. 6 13 8 11 1 5 9 15 7 Для второго элемента 8 подберём место в упорядоченном массиве. 8>6 и 8<13, следовательно его место 1-е.

3-й шаг. 6 8  13  11 1 5 9 15 7 11>8, 11<13, следовательно, его место 2-е.

4-й шаг. 6 8 11 13   1 5 9 15 7 1<6, следовательно, его место 0-е.

5-й шаг. 16 8 11 13     5 9 15 7 1<5, 5<6, следовательно, его место 1-е.

6-й шаг. 1 5 6 8 11 13   9 15 7 8<9, 9<11, следовательно, его место 4-е.

7-й шаг. 1 5 6 8 9 11 13    15 7 Этот элемент массива уже находится на своём месте.

8-й шаг. 1 5 6   8 9 11 13 15 7 6<7, 7<8, следовательно, его место 3-е.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману