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

Алгоритм сортировки выбором по возрастанию (для сортировки по убыванию надо поменять в блок-схеме знак «>» на знак «<») приведен в виде блок-схемы на рис. 10. Идея алгоритма заключается в следующем. В массиве состоящем из n элементов ищем самый большой элемент и меняем его местами с последним элементом. Повторяем алгоритм поиска максимального элемента, но последний (n-1)-й элемент не рассматривается, так как он уже занял свою позицию. Найденный максимальный элемент меняем местами с (n-2)-м элементом. Описанную выше операцию поиска проводим n-1 раз, до полного упорядочивания элементов в массиве.

Рисунок 10: Алгоритм сортировки выбором

Реализация алгоритма упорядочивания на С++

int main()

{

float b,max,a[20];

int i,j,n,k,nom;

cout<<"n=";

cin>>n;

cout<<"Massiv a\n";

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

cin>>a[i];

k=n;

for(j=0;j<=k-2;j++)

{

max=a[0];nom=0;

for(i=1;i<k;i++)

if (a[i]>max)

{

max=a[i];

nom=i;

}

b=a[k-1];

a[k-1]=a[nom];

a[nom]=b;

k--;

}

cout<<"Massiv a\n";

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

cout<<"a("<<i<<")="<<a[i]<<"\t";

cout<<endl;

return 0;

}

Сортировка методом пузырька. Сортировка пузырьковым методом является наиболее известной. Ее популярность объясняется запоминающимся названием, которое происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень, и простотой алгоритма. Сортировка методом «пузырька» использует метод обменной сортировки и основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Рассмотрим алгоритм пузырьковой сортировки более подробно.

Сравним нулевой элемент массива с первым, если нулевой окажется больше первого, то поменяем их местами. Те же действия выполним для первого и второго, второго и третьего, i- го и (i+1)-го, предпоследнего и последнего элементов. В результате этих действий самый большой элемент станет на последнее (n-1)-е место. Теперь повторим данный алгоритм сначала, но последний (n-1)-й элемент, рассматривать не будем, так как он уже занял свое место. После проведения данной операции самый большой элемент оставшегося массива станет на (n- 2)-е место. Так повторяем до тех пор, пока не упорядочим весь массив. Блок - схема сортировки элементов массива по возрастанию (для сортировки по убыванию надо поменять в блок-схеме знак «>» на знак «<») представлена на рис. 11.

Рисунок 11: Упорядочивание массива по возрастанию

методом пузырька

int main()

{

float b,max,a[20];

int i,j,n,k,nom;

cout<<"n=";

cin>>n;

cout<<"Massiv a\n";

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

cin>>a[i];

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

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

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

{

b=a[i];

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

a[i+1]=b;

}

cout<<"Massiv a\n";

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

cout<<"a("<<i<<")="<<a[i]<<"\t";

cout<<endl;

return 0;

}