Сортировка методом прямого включения.

Пузырьковая сортировка.

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

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

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

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

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

Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с I = 2, из исходной последовательности извлекается I-й элемент и вставляется на нужное место готовой последовательности, затем I увеличивается на 1 и т.д.

В процессе поиска нужного места осуществляются пересылки элементов больше выбранного на одну позицию вправо, т.е. выбранный элемент сравнивают с очередным элементом отсортированной части, начиная с J = I – 1. Если выбранный элемент больше a[I], то его включают в отсортированную часть, в противном случае a[J] сдвигают на одну позицию, а выбранный элемент сравнивают со следующим элементом отсортированной последовательности. Процесс поиска подходящего места заканчивается при двух различных условиях:

1) если найден элемент a[J] > a[I];

2) достигнут левый конец готовой последовательности.

Пример 44. Сортировка методом вставки.

int i,j,x;

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

{

x=a[i]; //запомнили элемент, который будем вставлять

j=i-1;

while(x<a[j]&&j>=0) //поиск подходящего места

{

a[j+1]=a[j]; //сдвиг вправо

j--;

}

a[j+1]=x; //вставка элемента

}

Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т.д.

Пример 45. Сортировка методом выбора.

int i,min,n_min,j;

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

{

min=a[i]; n_min=i; //поиск минимального

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

if(a[j]<min) {min=a[j]; n_min=j;}

a[n_min]=a[i]; //обмен

a[i]=min;

}

Сравниваются и меняются местами пары элементов, начиная с последнего. В результате самый маленький элемент массива оказывается самым левым элементом массива. Процесс повторяется с оставшимися элементами массива.

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

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

for(int j=n-1;j>=i;j--)

if(a[j]<a[j-1])

{

int r=a[j];

a[j]=a[j-1];

a[j-1]=r;

}

Методы сортировки массивов:

Реализация:

int arr [] = {8,7,0,5,4,3,2,1};

const int N = 8;

//Вывод массива

cout<< "Массив:\n";

for (int i=0; i < N; i++)

cout<< arr [i]<< " ";

cout<<"\n";

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

for (int i=N-1; i > 0; --i)

for (int j=0; j < i; ++j)

if (arr [j] > arr [j+1])

{

int tmp = arr [j];

arr [j] = arr [j+1];

arr [j+1] = tmp;

}

cout<< "\nОтсортированный массив:\n"; //Вывод массива

for (int i=0; i < N; i++)

cout<< arr [i]<< " ";

int arr [] = {8,7,6,0,4,3,2,1};

const int N = 8;

//Вывод массива

cout<< "Массив:\n";

for (int i=0; i < N; i++)

cout<< arr [i]<< " ";

cout<<"\n";

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

for (int i=1; i< N; i++)

{

int tmp = arr [i];

int j;

for (j=i - 1; j >=0 && arr [j] > tmp; j--)

arr [j + 1] = arr [j];

arr [j + 1] = tmp;

}

cout<< "\nОтсортированный массив:\n"; //Вывод массива

for (int i=0; i < N; i++)

cout<< arr [i]<< " ";

3. Сортировка методом прямого выбора.