Сортировка с помощью включения

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

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

- если найден элемент a[j]>a[i];

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

 

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;//вставка элемента

}

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

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

		мин

 

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;

}

 

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

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

			42

 

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;}

}

 

ПРИМЕР

//2. Дан одномерный массив, состоящий из N целочисленных элементов.

//2.1.Заполнить массив случайными числами.

//2.2.Найти минимальный элемент.

//2.3.Вычислить сумму элементов массива.

//2.4.Вывести положительные элементы на экран.

//2.5.Отсортировать массив по убыванию и вывести на экран

#include <iostream>

#include <time.h>

 

using namespace std;

int main()

{

setlocale(LC_ALL, "Russian");

const int MAX_SIZE = 100;

int mas[MAX_SIZE];

//1. формирование массива с помощью датчика случайных чисел

int n, m, k, g, i, j, x;

cout << "\nВведите размер массива < " << MAX_SIZE << ": ";

cin >> n;

srand((unsigned)time(NULL)); //Запуск генератора случайных чисел

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

mas[i] = rand() % 100 - 50;

 

//Печать полученного массива

cout << "1. Печать массива:\n";

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

cout << " " << mas[i];

 

//2. поиск минимального элемента

k = 0;

int iMin = mas[0];

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

if (iMin > mas[i])

iMin = mas[i];

k++;

}

cout << "\n\n2.Минимальный элемент равен " << iMin << endl;

 

//3.Вычислить сумму элементов массива.

int S = 0;

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

S += mas[i];

cout << "\n3.Сумма эл-ов масива = " << S << endl;

 

//4.Вывести положительные элементы на экран.

cout << "\n4. Список положительных элементов: ";

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

if (mas[i] > 0)

cout << mas[i] << "; ";

 

//5.Отсортировать массив по убыванию и вывести на экран

cout << "\n\n5.Сортировка массива по убыванию (сортировка с помощью включения):";

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

{

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

j = i - 1;

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

{

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

j--;

}

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

}

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

cout << " " << mas[i];

cout << endl;

system("pause");

return 0;

}

 

Лабораторная работа № 6. Массивы

Цель и порядок работы

Цель работы – получение практических навыков алгоритмизации и программирования вычислительных процессов с использованием массивов.

 

Порядок выполнения работы:

- ознакомиться с описанием лабораторной работы;

- получить задание у преподавателя, согласно своему варианту;

- написать программу и отладить ее на ЭВМ;

- оформить отчет.

 

Контрольные вопросы

1. Как определить массив?

2. Как проинициализировать массив?

3. Какие варианты объявления с инициализацией вы знаете?

4. Как обратиться к элементу массива?

5. Как объявить многомерный массив?

6. Как проинициализировать многомерный массив?

7. Как определить размер одномерного массива, зная его имя?

Задание

1. Написать программу в соответствии с вариантом задания

2. Отладить и протестировать программу.

3. Написать программу в соответствии с вариантом.

4. Отладить и протестировать программу.

5. Оформить отчёт.

 

Варианты заданий