Сортировка массива
На этом уроке мы напишем программу на си для сортировки массива. Программа задает случайным образом массив и сортирует массив и выводит на экран отсортированный массив Проиллюстрируем метод сортировки на конкретном примере. Допустим,задан массив <5,10,13,1,45,76>. Нам нужноотсортировать его от большего к меньшему. Так чтобы в конце был массив <76,45,13,10,5,1>.Найдем максимальный элемент это будет 76, поставим его на первое место, получим <76, 10,13,1,45,5>.Теперь рассмотрим массив уже без первого члена <10,13,1,45,5>найдем в нем максимальный элемент и поставим его на первое место, получим <45, 13,1,10,5>.Так
далее всегда будем искать максимальный элемент в оставшемся массиве и будем ставить его вверх.
При написании программы будут полезен урок Массивы в Си.
Напишем процедуру вывода массива. Чтобы передать в Си массив в процедуру в качестве параметра нужно указать тип и массив с пустыми скобками название процедуры (тип массива имя массива[])
// процедура вывода массива на экран
void vivod(int B[])
<
int i;
printf(" ");
// пробегаемся по всем элементам массива
for (i=0; i<num;i++)
<
printf ("%d ", B[i]);
>
>
Задаём случайным образом массив в Си
//задаем элементы массива случайным образом
for (i=0; i<num; i++)
<
a[i]=rand()%range+1;
>
Для каждого места в массиве определяем максимальный элемент в оставшемся массиве и ставим его на это место.
В переменной i будет сохраняться текущая позиция массива, в переменной k будет храниться номер макисмального элемента в оставшемся массиве
// пробегаемся по всем элементам массива
for (i=0; i<num;i++)
<
max=a[i];
k=i;
// ищем максимум в оставшееся массиве
for (j=i+1; j<num; j++)
<
// если элемент больше то изменяем максимум на него
if (a[j]>max)
<
k=j;
max=a[j]; >
>
// ставим максимальный элемент наверх
c=a[i];
a[i]=a[k];
a[k]=c;
>
Пример решения:
//сортировка массива
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int num=10;// количество элементов в массиве
int range=20; // диапазон случайных значений элементов массива
// процедура вывода массива на экран
void vivod(int B[])
<
int a[20];// объявление целочисленного массива a из 10 элементов
int i, j;// переменная для работы с массивом в цикле
int k; // номер максимального элемента в оставшемся массиве
int c;
int max;// максимум в оставшемся массиве
//задаем элементы массива случайным образом
for (i=0; i<num; i++)
<
a[i]=rand()%range+1;
>
// вывод получившегося массива
vivod(a);
getch();
// пробегаемся по всем элементам массива
for (i=0; i<num;i++)
<
max=a[i];
k=i;
// ищем максимум в оставшемся массиве
for (j=i+1; j<num; j++)
<
// если элемент больше то изменяем максимум на него
if (a[j]>max)
<
k=j;
max=a[j];
>
>
// ставим максимальный элемент наверх
c=a[i];
a[i]=a[k];
a[k]=c;
>
printf("отсортированный ");
vivod(a);
getch();
>
На заметку:
1. В процедуру как параметр можно передать целый массив для этого достаточно указать тип имя и [] при этом исходный массив меняться не будет. Например void vivod (int B[]. При вызове данной процедуры достаточно
подставить имя массива, которое будет передано в процедуру. Например vivod(a).
2.Чтобы поменять местами элементы массива необходимо использовать переменную такого же типа. Например нужно поменять местами a[i] и a[j].
с=a[i];
a[i]=a[j];
a[j]=c;
Задания для самостоятельной работы:
1 Отсортировать массив по возрастанию. Вначале самый маленький, в конце самый большой.
Напишите программу которая сортирует массив по убыванию
Дан массив чисел размерностью 10 элементов. Написать функцию, которая сортирует массив по возрастанию или по убыванию, в зависимости от третьего параметра функции. Если он равен 1, сортировка идет по убыванию, если 0, то по возрастанию. Первые 2 параметра функции — это массив и его размер, третий параметр по умолчанию равен 1.
template <typename T1, typename T2> void sort(T1 ar, T2 SIZE, T2 par);
int par=0;
cout<<"Добро пожаловать в программу упорядочивания массива. Выберите как будет упорядочен массив (1 — по возрастанию, 2 — по убыванию): ";
cout<<endl<<endl<<endl;
const int SIZE = 10;
int ar[SIZE];
template <typename T1, typename T2> void sort(T1 ar, T2 SIZE, T2 par)<
int tmp;
int j;
if(par==1)<
for(int i = 0; i<SIZE; i++)<
if(par==2)<
for(int i = 0; i<SIZE; i++)<
Дан массив случайных чисел в диапазоне от -20 до +20. Необходимо найти позиции крайних отрицательных элементов (самого левого отрицательного элемента и самого правого отрицательного элемента) и отсортировать элементы, находящиеся между ними.
Решение (левое и правое крайнее отрицательное число подсвечиваю красным цветом, в связи с этим функция сразу выкрикивает отсортированный массив. Для простоты):
HANDLE h = GetStdHandle(STD_OUTPUT_HANDLE);
template <typename T1, typename T2> void sort(T1 ar, T2 SIZE);
void main() <
SetConsoleTextAttribute(h,15);
setlocale(0,"");
srand(time(0));
cout<<endl<<endl<<endl;
const int SIZE = 10;
int ar[SIZE];
template <typename T1, typename T2> void sort(T1 ar, T2 SIZE)<
//найдем отрицательные элементы.
int nizotr=-1, verhotr;
//исп. метод шейкера.
int tmp, nizpodsv=nizotr, verhpodsv=verhotr;
//движение вниз
for(int i = verhotr-1; i>nizotr+1; i—) <
if(ar[i]<ar[i-1]) <
tmp=ar[i];
ar[i]=ar[i-1];
ar[i-1]=tmp;
>
>
nizotr+=1;
>while(nizotr<verhotr);
Задание №3: Дан массив из 20 целых чисел со значениями от 1 до 20.
написать функцию, разбрасывающую элементы массива произвольным образом;
создать случайное число из того же диапазона и найти позицию этого случайного числа в массиве;
отсортировать элементы массива, находящиеся слева от найденной позиции по убыванию, а элементы массива, находящиеся справа от найденной позиции по возрастанию.
Решение (хоть я и юзал шаблоны, но со всеми типами данных функции работать не буду, т.к. ещё не изучали указатели).
HANDLE h = GetStdHandle(STD_OUTPUT_HANDLE);
template <typename T1, typename T2> void Razbros (T1 ar, T2 SIZE);
template <typename T1, typename T2> void Sort (T1 ar, T2 SIZE, T2 j);
void main()
< SetConsoleTextAttribute(h,15);
srand(time(0));
//создадим одномерный массив чисел от 1 до 20
setlocale(0,"");
const int SIZE = 20;
int ar[SIZE];
cout<<"Массив до разброса значений: "<<endl;
Razbros (ar, SIZE);
//создадим случайное число из того же диапазона и найдем позиции вхождения этого числа.
int dig = rand()%20+1;
cout<<endl<<"Случайное значение — "<<dig<<"! Оно встретилось в массиве в позиции — ";
//нужна функция сортировки. Типа двойной пузырьковой сортировки.
Sort(ar,SIZE,j);
cout<<endl<<endl<<"Массив после сортировки (слева от красного числа — по убыванию, справа — по возрастанию): "<<endl;
template <typename T1, typename T2> void Razbros (T1 ar, T2 SIZE)<
for(int i = 0; i<SIZE; i++) <
int j = rand()%20;
tmp = ar[i];
ar[i]=ar[j];
ar[j]=tmp;
>
template <typename T1, typename T2> void Sort (T1 ar, T2 SIZE, T2 j) <
//две пузырьковых сортировки.
T2 tmp;
Напишите программу которая сортирует массив по убыванию
Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую по убыванию.Массив заполнен случайными числа от 0 до 500длинна массива 100 элементов.Массив одномерный Примечание: Элементы с первой половины массива не должны попадать во вторую половину.
———- Добавлено в 19:57 ———- Предыдущее сообщение было написано в 18:52 ———-
program n32;
var x,i:integer;
a:array [1..100] of integer;
begin
for i:=1 to 100 do a[i]:= random (500);
for i:=1 to 100 do
writeln (‘a[,i,]=’,a[i]);
begin
for i:=1 to 50 do
if a[i]>a[i+1] then
x:=a[i];
a[i]:=a[i+1];
a[i+1]:=x;
end;
for i:=1 to 50 do
Write ( a [ i ],’ ‘);
end.
program n32;
var y,x,j,imin,imax,i:integer;
a:array [1..100] of integer;
begin
for i:=1 to 100 do a[i]:= random (500);
for i:=1 to 100 do
write (‘a[, ,]=’,a[i]);
for i:=1 to 49 do
begin
imax:=i;
for j:=i+1 to 50 do
if a[j]>a[imax] then imax:=j;
x:=a[i];
a[i]:=a[imax];
a[imax]:=x;
end;
for i:=51 to 99 do
begin
imin:=i;
for j:=i+1 to 100 do
if a[j]<a[imin] then imin:=j;
y:=a[i];
a[i]:=a[imin];
a[imin]:=y;
end;
for i:=1 to 100 do writeln(‘a[,массив ,]=’,a[i]);
end.
Прогу написал, вроде бы работает.Только вот хочу добавить эстетики..как мне вывести пронумерованный массив?