Алгоритм прямого упорядочения (Алгоритм сортировки выбором элемента)

В программе реализован алгоритм прямого упорядочения – каждый элемент a[i], начиная с а[0] и кончая а[n-2], сравнива­ется со всеми последующими, и на место a[i] выбирается мини­мальный. Таким образом, а[0] принимает минимальное зна­чение, а[1] - минимальное из оставшихся и т.д. Недостаток это­го алгоритма состоит в том, что в нем фиксированное число сравнений, не зависимое от исходного расположения значений элементов. Даже для уже упорядоченного массива придется вы­полнить то же самое количество итераций (n-1)*n/2, так как условия окончания циклов не связаны со свойствами, т.е. с раз­мещением элементов массива.

Текст программы:

/* Упорядочение элементов массива */

#include <stdio.h>

main()

{

int n,i,j;

double a[100],b;

while(1)

{

printf("\n Введите количество элементов n=");

scanf("%d",&n);

if (n > 1 && n <= 100) break;

printf("Ошибка! Необходимо 1<n<=100!");

}

printf("\n Введите значения элементов массива:\n");

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

{

printf("a[%d]=", j+1);

scanf<"%lf",&a[j]);

}

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

for(j=i+1; j<n; j++)

if(a[i]>a[j])

{

b=a[i];

a[i]=a[j];

a[j]=b;

}

printf("\nУпорядоченный массив: \n");

for(j=0/ j<n; j++)

printf ("a[%d]=%f\n",j +l,a[j]);

}

Результаты выполнения программы:

Введите количество элементов n= -15

Ошибка! Необходимо 1<n<=100!

Введите количество элементов n=3

Введите значения элементов массива:

а[1] = 88.8

а[2] = -3.3

а[3] = 0.11

Упорядоченный массив:

а[1] = -3.3

а[2] = 0.11

а[3] = 88.8

Обратите внимание, что при заполнении массива и при печа­ти результатов его упорядочения индексация элементов выпол­нена от 1 до n, как это обычно принято в математике. В программе на Си это соответствует изменению индекса от 0 до (n-1).

6.5 Алгоритм попарного сравнения соседних элементов («пузырьковая» сортировка)

Алгоритм попарного сравнения соседних элементов позволя­ет в ряде случаев уменьшить количество итераций при упорядо­чении. В цикле от 0 до n-2 каждый элемент a[i] массива сравнивается с последующим a[i+l] (0<i<n-l). Если a[i]>a[i+l], то значения этих элементов меняются местами. Упорядочение заканчивается, если оказалось, что a[i] не больше a[i+l] для всех i. Пусть k - количество перестановок при очередном просмотре. Тогда упорядочение можно осуществить с помощью такой по­следовательности операторов:

do {

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

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

{

b=a[i];

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

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

}

n--;

} while(k > 0);

Здесь количество повторений внешнего цикла зависит от ис­ходного расположения значений элементов массива. После пер­вого завершения внутреннего цикла элемент а[n-1] становится максимальным. После второго окончания внутреннего цикла на место а[n-2] выбирается максимальный из оставшихся элемен­тов и т.д. Таким образом, после j-ro выполнения внутреннего цикла элементы a[n-j],...,a[n-l] уже упорядочены, и следующий внутренний цикл достаточно выполнить только для 0<i<(n-j-l). Именно поэтому после каждого окончания внутреннего цикла значение n уменьшается на 1.

В случае упорядоченности исходного массива внешний цикл повторяется только один раз, при этом выполняется (n-1) срав­нений, k остается равным 0. Для случая, когда исходный массив упорядочен по убыванию, количество итераций внешнего цикла равно (n-1), а внутренний цикл последовательно выполняется (n-1)*n/2 раз.

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