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

Одномерные массивы

Остановка программы с помощью оператора 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)² раз, а пока массив не будет отсортирован. Определить этот факт очень просто: если массив уже отсортирован, то в процессе прохода в нем не происходит никаких перестановок. Перед началом просмотра нужно установить признак (флаг) отсутствия перестановок. В случае, если производится хотя бы одна перестановка, флаг изменяет свое значение. Если к моменту завершения прохода значение флага осталось первоначальным, значит, массив отсортирован и дальнейшие проходы не нужны.

Если объединить метод оптимизации с проверкой признака завершения сортировки, получим алгоритм, называемый обменной сортировкой с признаком завершения.

Пример. Обменная сортировка массива 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");}

Дата добавления: 2014-11-16