Методы сортировки массивов
Одномерные массивы
Остановка программы с помощью оператора exit
Если необходимости остановить программу, то можно воспользоваться функцией exit(), прототип которой определен в заголовочном файле STDLIB.H.
Выполнение оператора exit(0); немедленно завершает программу, закрывает все открытые файлы и выполняет некоторые другие завершающие действия. Значение в круглых скобках возвращается DOS (или другой программе, вызывающей данную). Возвращаемое значение можно анализировать и с его помощью управлять ходом вызывающей программы, в частности командного файла.
Лекция №7. МАССИВЫ
Массивы являются наиболее используемыми структурами данных, представляющими собой совокупности элементов одного и того же типа, проиндексированных неотрицательными целыми числами.
Наиболее часто в программах применяются одномерные массивы (векторы) и двумерные массивы (матрицы), но язык С позволяет объявлять и многомерные массивы.
Одномерный массив или вектор представляет собой несколько однотипных переменных, совместно использующих одно имя (имя массива), при этом доступ к каждому элементу осуществляется по его порядковому номеру (индексу).
Объявить вектор можно следующим образом:
тип_элементов имя_массива [число_элементов];
При этом число элементов должно быть задано явно, так как компилятор резервирует место под массив в момент компиляции и изменить его потом уже невозможно. Допустимо лишь частичное использование занятого под массив адресного пространства.
Например: inti_arr[10]; charliter[80]; doubled_mas[100];
При объявлении массивов необходимо помнить, что индекс первого элемента всегда равен нулю. Допустимыми считаются значения индексов, находящиеся в диапазоне от 0 до число_элементов - 1.
Обращение к элементу массива, индекс которого не является допустимым, приводит к возникновению ошибок, вызванных обращением к области памяти, не принадлежащей массиву.
Доступ к элементам вектора удобнее всего осуществлять, пользуясь циклом for.
Можно организовать ввод массива случайным образом в нужном диапазоне значений. Для этого используют генератор случайных чисел.
Пример. Ввод элементов вектора случайным образом и вывод его на экран.
randomize();//инициализация генератора случайных чисел
for(int i=l;i<M;i++)
{x[i]=random(100);
printf("%4d",x[i]);}
Здесь будет сформирован массив, состоящий из M элементов и содержащий целые значения в диапазоне от 0 до 99.
Сортировка простым выбором
Это - самый простой из алгоритмов сортировки. В сортируемом массиве находится самый маленький элемент и обменивается местами с элементом в начале массива. Далее оставшаяся часть массива рассматривается как самостоятельный массив. В нем, в свою очередь, производится поиск наименьшего элемента, который меняется местами с первым элементом этого укороченного массива. Такие действия повторяются до тех пор, пока массив не укоротится до одного элемента.
Пример. Пусть дан массив 142, 23, 97, 19, 2, 4. Отсортируем его.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
{ const int N = 6;
intmas[N];
int i,j, i_min,j_min, min;
randomize();
clrscr();
for (i = 0; i<N; i++)
{ mas[i]=random(100)-50;
printf("%4d",mas[i]);}
printf("\n");
for (i=0; i<N; i++)
{ min = mas[i]; i_min = i;
for (j = i+1; j<N; j++) //перебор в уменьшенном массиве
if(mas[j] < min) {min = mas[j]; j_min=j;}
mas[j_min] = mas[i]; mas[i] = min; }
for (i = 0; i<N; i++)
printf("%4d",mas[i]);
printf("\n");}
Метод пузырьковой сортировки
Под пузырьковой сортировкой понимают целый класс алгоритмов сортировки. В своем простейшем варианте пузырьковая сортировка выполняется крайне медленно, поэтому обычно применяют пузырьковую сортировку с элементами оптимизации. Однако все алгоритмы пузырьковой сортировки имеют общую особенность - обмен элементов массива производится между двумя соседними элементами массива.
Пример. Отсортируем данный массив 142, 23, 97, 19, 2, 4 пузырьковым методом.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
{ const int N=6; int mas[N]; int i, j, wrk;
randomize(); clrscr();
for (i=0; i<N; i++)
{ mas[i]=random(100)-50;
printf("%4d", mas[i]);}
printf("\n");
for(i=0; i<N-l; i++)
for(j=0; j<N-l; j++)
if(mas[j]< mas[j+1])
{ wrk=mas[j];
mas[j]=mas[j+l];
mas[j+1]=wrk;}
for (i=0; i<N; i++)
printf("%4d", mas[i]);
printf("\n");}
Можно уменьшить количество проходов сортировки, выполняя их не (N - 1)2 раз, а пока массив не будет отсортирован. Определить этот факт очень просто: если массив уже отсортирован, то в процессе прохода в нем не происходит никаких перестановок. Перед началом просмотра нужно установить признак (флаг) отсутствия перестановок. В случае, если производится хотя бы одна перестановка, флаг изменяет свое значение. Если к моменту завершения прохода значение флага осталось первоначальным, значит, массив отсортирован и дальнейшие проходы не нужны.
Если объединить метод оптимизации с проверкой признака завершения сортировки, получим алгоритм, называемый обменной сортировкой с признаком завершения.
Пример. Обменная сортировка массива 142, 23, 97, 19, 2, 4 с признаком завершения
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
{ const int N = 6;
int mas[N]; int j, wrk, flag, k;
randomize();
clrscr();
for (j=0; j<N; j++)
{ mas[j]=random(100)-50;
printf("%4d", mas[i]); }
printf("\n");
k=1 ; flag=1 ; // оператор нужен для входа в цикл
while (flag != 0)
{ flag = 0;
for (j=0;j<N-k; j++)
if(mas[t]<mas[j+l])
{ flag++; wrk=mas[j];
mas[j]=mas[j+1]; mas[j+1]=wrk;}
k++;}
for (j=0; j<N; j++)
printf("%4d", mas[j]);
printf("\n");}