Использование рекурсивных вызовов в программах на языке Си. Лясин Д.Н - 9 стр.

UptoLike

ВУЗ: 

ВПИ ВолгГТУ | Волжский

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

Рубрика: 

9
40 10 30 20 60 50 80
Когда левая отметка зайдет за правую, останавливаем движение.
40 10 30 20 60 50 80
Меняем число над правой отметкой (из двух отмеченных оно
теперь левее!) местами с разделителем
20 10 30 40 60 50 80
и разделение массива закончено
Теперь аналогичную процедуру необходимо проделать над левой и
правой половинками массива, при условии, что они имеют длину более
одного элемента. Таким образом, базой рекурсии для рассмотренного
алгоритма будет подмассив размером 1 или 0 элементов, который,
очевидно, не требует сортировки. Шаг рекурсии – сортировка левого и
правого подмассивов после операции разделения исходного массива.
Программная реализация алгоритма сортировки по Хоару
представлена в листинге 1.
Листинг 1. Сортировка массива методом быстрой обменной
сортировки.
#include<iostream.h>
#include <stdlib.h>
#include<conio.h>
int m[10]={96,95,93,45,96,17,64,78,21,19};
/*
sorting – функция разделения массива. Прнимает параметры left
и right – границы подмассива для разделения. Через параметр
middle возвращает вызвавшей функции место разделтеля по итогам
разделения
*/
sorting(int left,int right,int& middle)
{
int sep=left,t, RightBorder=right;
while(left<=right)
{
while(m[left]<=m[sep]&&left<=RightBorder) left++;
while(m[right]>=m[sep]&&right>sep) right--;
if (left<right)
{t=m[left];
m[left]=m[right];
m[right]=t;
}
}
t=m[sep];
m[sep]=m[right];
m[right]=t;
middle=right;
}
/*hoer – функция сортировки массива m по возрастанию методом
Хоара. 
      40 10 30 20 60 50 80
     Когда левая отметка зайдет за правую, останавливаем движение.
      40 10 30 20 60 50 80
     Меняем число над правой отметкой (из двух отмеченных оно
теперь левее!) местами с разделителем
       20 10 30 40 60 50 80
       и разделение массива закончено
     Теперь аналогичную процедуру необходимо проделать над левой и
правой половинками массива, при условии, что они имеют длину более
одного элемента. Таким образом, базой рекурсии для рассмотренного
алгоритма будет подмассив размером 1 или 0 элементов, который,
очевидно, не требует сортировки. Шаг рекурсии – сортировка левого и
правого подмассивов после операции разделения исходного массива.
     Программная реализация алгоритма сортировки по Хоару
представлена в листинге 1.
     Листинг 1. Сортировка массива методом быстрой обменной
     сортировки.
#include
#include 
#include
int m[10]={96,95,93,45,96,17,64,78,21,19};
/*
sorting – функция разделения массива. Прнимает параметры left
и right – границы подмассива для разделения. Через параметр
middle возвращает вызвавшей функции место разделтеля по итогам
разделения
*/
sorting(int left,int right,int& middle)
{
  int sep=left,t, RightBorder=right;
  while(left<=right)
   {
        while(m[left]<=m[sep]&&left<=RightBorder) left++;
        while(m[right]>=m[sep]&&right>sep) right--;
        if (left

Страницы