Виды методов сортировки. Сортировка вставкой

При работе с данными часто используются методы сортировки. Данные могут располагаться в оперативной памяти или на сменных носителях. При сортировке выдвигаются требования минимального использования дополнительной памяти. Т.е. не допустимость применения дополнительных массивов. Для оценки быстродействия алгоритмов сортировки используют показатели: количество сравнений и количество присваиваний.

Сортировка вставкой: массив разделяется на две части отсортированную и не отсортированную, элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, что бы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один 1 элемент, а в качестве не отсортированной части все остальные элементы. Таким образом, алгоритм будет состоять из m-1 прохода, где m — размерность массива.

Каждый проход будет включать 4 действия:

1) Взятие очередного i-го не отсортированного элемента и сохранение его в дополнительную переменную.

2) Поиск позиции j в отсортированной части, в которой присутствие взятого элемента не нарушит упорядоченности элемента.

3) Сдвиг элементов массива от i-1 до j-1 вправо, что бы освободить названную позицию в ставке.

4) Вставка взятого элемента в найденную позицию j.

 

Виды методов сортировки. Сортировка выбором

При работе с данными часто используются методы сортировки. Данные могут располагаться в оперативной памяти или на сменных носителях. При сортировке выдвигаются требования минимального использования дополнительной памяти. Т.е. не допустимость применения дополнительных массивов. Для оценки быстродействия алгоритмов сортировки используют показатели: количество сравнений и количество присваиваний.

Сортировка выбором:

1) Находим в массиве элемент с минимальным значением на интервале от 1 до последнего и меняем его местами с первым элементом.

2) Ищем минимальный элемент на интервале от 2 до последнего и меняем его со 2 позицией.

 

Виды методов сортировки. Сортировка обменом

При работе с данными часто используются методы сортировки. Данные могут располагаться в оперативной памяти или на сменных носителях. При сортировке выдвигаются требования минимального использования дополнительной памяти. Т.е. не допустимость применения дополнительных массивов. Для оценки быстродействия алгоритмов сортировки используют показатели: количество сравнений и количество присваиваний.

Сортировка обменом: метод пузырька

Слева на право поочередно сравниваются два соседних элемента и если из взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Берутся два следующих и так до конца массива. После первого прохода на последнем месте будет состоять максимальный элемент, поэтому 2 проход можно выполнять до m-1. Следующий проход выполняется до последнего элемента.

 

Методы функции

Методы (подпрограммы) процедуры и функции позволяют решать задачу повторного использования программного кода. Разработанные или имеющиеся подпрограммы дают возможность существенно расширить возможности языка программирования. Важным шагом в автоматизации программирования является появление библиотек подпрограмм. Подпрограммы C# включены в классы и называются методами класса. На платформе.Net стандартной библиотекой является FCL.

Отличие функции: 1) функция должна возвращать хотя бы одно значение, 2) функция может быть вызвана в выражениях.

Если метод является функцией, то в блоке должен быть хотя бы один оператор return возвращающий значение функции в форме:

return (выражение);

static int fmax(int a, int b)

{

if (a > b)

return (a);

else

return (b);

}

static int fmin(int a, int b)

{

return (a < b? a: b);

}

Методы процедуры

Методы (подпрограммы) процедуры и функции позволяют решать задачу повторного использования программного кода. Разработанные или имеющиеся подпрограммы дают возможность существенно расширить возможности языка программирования. Важным шагом в автоматизации программирования является появление библиотек подпрограмм. Подпрограммы C# включены в классы и называются методами класса. На платформе.Net стандартной библиотекой является FCL.

Отличие процедуры: 1) может не возвращать значения, 2) вызывается как отдельный оператор.

static void test()

{

Console.WriteLine("Test\n");

}

static int fmax(int a, int b)

{

if (a > b)

return (a);

else

return (b);

}

static void pow_matr(int st, params int[] m)

{

foreach (int i in m)

Console.Write("\t" + Math.Pow(Convert.ToDouble(i), Convert.ToDouble(st)));

}