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

Сортировка массивов.

Сортировка данных является одной из важных задач в обработке массивов. Банк сортирует чеки по номеру счёта, телефонные компании сортируют свои списки по фамилиям, каждая организация должна сортировать довольно значительные объёмы данных. Для сортировки данных существует большое число алгоритмов, одним из самых простейших является пузырьковая сортировка, к достоинством, которого можно отнести легкость написания, проверки и отладки. А к недостаткам низкую производительность. Нижеприведённая программа сортирует значения массива из 10 элементов в возрастающем порядке методом пузырьковой сортировки. Наименьшее значение постепенно продвигается к началу массива, подобно пузырьку воздуха в воде, а наибольшее значение продвигается к концу массива. При каждом проходе сравниваются пара следующих друг за другом элементов. Если пара расположена в возрастающем порядке или элементы одинаковы, то мы оставляем значения без перемещения. Если пара расположена в убывающем порядке, значения в массиве меняются местами. При первом проходе наибольшее значение опустится на место нижнего элемента. Для сортировки массивов из 10 элементов нужно только 9 проходов. Сортировка выполняется с помощью цикла for. Если необходима перестановка, она выполняется тремя присваиваниями:

temp=ara[ctr1];

ara[ctr1]=ara[ctr2];

ara[ctr2]=temp;

где дополнительная переменная temp временно хранит одно из двух переставляемых значений.

Главное достоинство состоит в простоте программирования. Однако пузырьковая сортировка выполняется медленно, особенно для больших массивов.

Пример1 Отсортировать одномерный массив по возрастанию.

#include<iostream.h>

#define M 10

void main()

{

int ara[M];

int ctr,ctr1, ctr2,temp;

cout<<"введите элементы массива ";

for(ctr=0; ctr<M; ctr++)

Блок-схема алгоритма решения задачи бинарного поиска.

Начало

Инициализация

переменных

m=(l+f)/2

да нет

m==q?

нет да

ara[m]==p?

break

нет да

P>ara[m]? k=p

l=m-1 f=m+1

q=m

while (k==0)? да

нет

if(k==0)?

номер элемента 0

конец

cin>>ara[ctr];

cout<<"вывод неотсортированного массива ";

for(ctr=0; ctr<M; ctr++)

cout<< ara[ctr]<<" ";

for (ctr1=0; ctr1<(M-1); ctr1++) //сортировка массива

{

for(ctr2=(ctr1+1); ctr2<M; ctr2++)

{

if(ara[ctr1]>ara[ctr2])

//переставить местами

{

temp=ara[ctr1];

ara[ctr1]=ara[ctr2];

ara[ctr2]=temp;//всплывание наименьшего значения

}

}

cout<<"вывод после 1 шага массива ";

for (ctr=0; ctr<M; ctr++)

{

cout<<ara[ctr]<<" ";

}

break;

}

cout<<"вывод отсортированного массива ";

for (ctr=0; ctr<M; ctr++)

{

cout<<ara[ctr]<<" ";

}

}

Дата добавления: 2014-01-20