Программирование на языке высокого уровня. Марапулец Ю.В. - 46 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

Особняком стоит
сортировка подсчетом. В ней определяется количество элемен-
тов, больших или меньших данного, определяется его местоположение в выходном мас-
сиве.
Рассмотрим программные решения для вышеперечисленных групп алгоритмов
сортировок более подробно.
Сортировка выбором. Простейший алгоритм сортировки выбором будет выгля-
деть следующим образом:
-
ищется минимальный элемент массива и записывается на первое место. Для этого в
качестве минимального назначается первый элемент, с ним сравнивается второй, ес-
ли второй меньше первого, они меняются местами. Далее второй сравнивается с
третьим и т.д. Функция, осуществляющая поиск минимального элемента приведена
ниже:
void min(int А[], int n)
{
int min=0;//Предположим, что первый элемент минимальный
//Сравним оставшиеся элементы с минимальным
for (int i=1; i<n; i++)
if(A[i]<A[min])
min=i;
}
-
повторяется операция поиска минимального элемента и записи в конец отсортиро-
ванной последовательности, но уже без учета отсортированных элементов.
Исходный текст функции, осуществляющей сортировку выбором, приведен ниже:
void sort_choice(int A[], int n)
{
for ( int i=0; i < n-1; i++)
{
for ( int j=i+1, min=i; j<n; j++)
if (A[j] < A[min])
min=j;
int buf=A[i];
A[i] = A[min];
A[min] = buf;
}
}
Трудоемкость такого алгоритма - K = N*N/2.
Сортировка вставками. Основная идея алгоритма: имеется упорядоченная часть,
в которую очередной элемент помещается так, что упорядоченность сохраняется (вклю-
чение с сохранением порядка). Можно проводить линейный поиск от начала упорядо-
ченной части до первого элемента, больше данного, с конца - до первого элемента,
меньше данного (трудоемкость алгоритма по операциям сравнения - N*N/4); использо-
вать двоичный поиск места в упорядоченной части (трудоемкость алгоритма - N*log(N)).
Сама процедура вставки включает в себя перемещение элементов массива (не учтенное
в приведенной трудоемкости). В следующем примере последовательность действий по
вставке очередного элемента в упорядоченную часть «разложена по полочкам» в виде
последовательности четырех действий, связанных переменными.
46
      Особняком стоит сортировка подсчетом. В ней определяется количество элемен-
тов, больших или меньших данного, определяется его местоположение в выходном мас-
сиве.
      Рассмотрим программные решения для вышеперечисленных групп алгоритмов
сортировок более подробно.

      Сортировка выбором. Простейший алгоритм сортировки выбором будет выгля-
деть следующим образом:
- ищется минимальный элемент массива и записывается на первое место. Для этого в
   качестве минимального назначается первый элемент, с ним сравнивается второй, ес-
   ли второй меньше первого, они меняются местами. Далее второй сравнивается с
   третьим и т.д. Функция, осуществляющая поиск минимального элемента приведена
   ниже:

void min(int А[], int n)
{
       int min=0;//Предположим, что первый элемент минимальный
       //Сравним оставшиеся элементы с минимальным
       for (int i=1; i

Страницы