Работа с массивами

Пример 8.4. Количество "счастливых" билетов. Билеты для общественного транспорта хранятся в рулонах и идентифицируются номерами от 000000 до 999999. В молодежной среде "счастливым" считался билет, у которого сумма трех первых цифр совпадала с суммой трех последних цифр. Попытаемся оценить количество "счастливых билетов в полном рулоне с целью определения вероятности получить такой билет.

Самый простой способ заключается в организации 6 вложенных друг в друга циклов, где каждый счетчик перебирает цифры от 0 до 9, а во внутреннем цикле сравниваются суммы первых трех и последних трех счетчиков:

#include <iostream.h>
#include <conio.h>
void main()
{ int n=0;
  for(int j1=0; j1<10; j1++)
   for(int j2=0; j2<10; j2++)
    for(int j3=0; j3<10; j3++)
     for(int j4=0; j4<10; j4++)
      for(int j5=0; j5<10; j5++)
       for(int j6=0; j6<10; j6++)
        if(j1+j2+j3==j4+j5+j6) n++;
  cout << n;
  getch();
}

Считает эта программа правильно и довольно быстро (на ПК с частотой 2 ГГц время работы не превышает 1 сек). Но работу этой программы можно ускорить почти в 1000 раз за счет использования массивов. Сумма трех цифр принадлежит диапазону [0,27]. Допустим, что нам удалось подсчитать, сколько раз встретилась каждая сумма – s0 (количество сочетаний, давших сумму 0), s1 (количество сочетаний, давших сумму 1), ... . Тогда количество "счастливых" билетов будет равно (s0)2+(s1)2+ .... Поэтому гораздо более быстрой программой будет следующая:

#include <iostream.h>
#include <conio.h>
void main()
{ int n=0,k,s[28];
  for(k=0; k<28; k++) s[k]=0;
  for(int j1=0; j1<10; j1++)
    for(int j2=0; j2<10; j2++)
      for(int j3=0; j3<10; j3++)
        s[j1+j2+j3]++;
  for(k=0; k<28; k++)
    n += s[k]*s[k];
  cout << n;
  getch();
}

Количество циклов, которое "крутится" в этой программе равно 28+1000+28, тогда как в предыдущей программе тело самого внутреннего цикла повторялось 1000000 раз.

Пример 8.5. Ход конем. Одна из задач, связанных с шахматами заключается в определении минимального количества ходов коня, за которое он может перебраться из стартовой клетки шахматного поля в заданную клетку. Напомним, что конь ходит "буквой Г", совершая за один ход перемещение на 2 клетки по одной координате (вертикали или горизонтали) и на одну клетку по другой координате. Шахматисты пользуются алфавитно-цифровой кодировкой полей шахматной доски, обозначая их по горизонтали буквами (A,B,C,D,E,F,G,H), а по вертикали – цифрами (1,2,3,4,5,6,7,8). Однако для программы удобнее иметь дело только с цифровыми индексами, изменяющимися (с учетом требований языка C) от 0 до 7. Идея определения минимального количества ходов заключается в заполнении клеток шахматного поля числами досягаемости. Сначала мы находимся в стартовой позиции и пытаемся сделать из нее один из 8 возможных ходов (не выходя за пределы шахматной доски). Каждую из достижимых таким образом клеток отметим числом 1. Затем из каждой из них попытаемся сделать тоже один из возможных ходов, не возвращаясь в те клетки, где мы уже побывали. Вновь достижимые клетки пометим числом 2. Таким способом можно заполнить все клетки шахматного поля, включая и ту, в которую мы должны были придти из стартовой позиции. Для того чтобы выделить свободные клетки, еще не помеченные уровнем досягаемости, распишем в начале все клетки числом -1.

Пусть массив a размерности 8x8 моделирует шахматную доску. Распишем элементы этого массива числами -1 (признак того, что все клетки свободны). Затем запросим у пользователя индексы стартовой позиции и занесем в этот элемент массива 0 (из стартовой позиции в нее же можно добраться за 0 ходов). Пусть функция, которая пытается сделать один из 8 возможных ходов, называется newlevel и использует в качестве исходной информации данные, вынесенные в глобальные переменные – матрицу a, уровень досягаемости k и управляющую переменную xod. Ее задачей является поиск всех незанятых клеток, находящихся на расстоянии одного хода от клеток с уровнем досягаемости k и записью в них кода k+1. Значение управляющей переменной xod=1, если хотя бы один такой ход удалось сделать. Если все клетки шахматной доски помечены неотрицательными уровнями досягаемости, т.е. ни одного хода больше сделать нельзя, то значение переменной xod равно 0. В функции newlevel удобно выделить процедуру try_ (подчерк добавлен к имени потому, что слово try является служебным), которая пробует, достижима и свободна ли позиция с индексами ( p,q ), в которой надо разместить очередной уровень досягаемости ( k+1 ).

Описанные выше функции newlevel и try_ могут быть организованы следующим образом:

void try_(int p, int q)
{ if(p>=0  p<8  q>=0  q<8  a[p][q]<0)
    { a[p][q]=k+1; xod=1; }
}
//----------------------------------
void newlevel()
{ char di[8]={-2,-2,-1,-1, 1,1, 2,2};
  char dj[8]={-1, 1,-2, 2,-2,2,-1,1};
  xod=0;
  for(int i=0; i<8; i++)
    for(int j=0; j<8; j++)
      if(a[i][j]==k)
        for(int r=0; r<8; r++)
          try_(i+di[r],j+dj[r]);
  k++;
}
//----------------------------------

Обратите внимание на массивы di и dj. Их одноименные элементы образованы из всевозможных сочетаний $$\pm$$ 1 и $$\pm$$ 2, которые определяют 8 всевозможных направлений для хода конем. Цикл по r перебирает все эти комбинации относительно позиции ( i,j ).

Головная программа, обращающаяся к функции newlevel, может иметь следующий вид:

#include <stdio.h>
#include <conio.h>
char a[8][8],i,j,k=0,xod;
void main()
{ for(i=0;i<8;i++)
    for(j=0; j<8;j++) a[i][j]=-1;
  printf("begin position=");
  scanf("%d %d",i,j);
  a[i][j]=0;
  do newlevel();
  while (xod==1);
  for(i=0;i<8;i++)
    { for(j=0; j<8; j++) printf("%3d",a[i][j]);
      printf("\n");
    }
  getch();
}

Результат работы для начальной позиции (1,1) приведен на рис 8.2.

Пример 8.6. Определение количества разных элементов в целочисленном массиве. Первый вариант программы основан на предварительной сортировке исходного массива. После того как массив отсортирован, следует проанализировать соседние элементы и, как только встречается пара разных чисел, к счетчику надо добавлять 1.

#include <stdio.h>
#include <conio.h>
void sort(int *a,int n)
{ int tmp;
  for(int i=0;i<n-1;i++)
    for(int j=i+1;j<n; j++)
      if(a[j]<a[i])
        {tmp=a[i]; a[i]=a[j]; a[j]=tmp; }
}
int difference(int *a,int n)
{ int i,m=1;
  sort(a,n);	//сортировка исходного массива
  for(i=0; i<n-1; i++)
    if(a[i]!=a[i+1]) m++;
  return m;
}
void main()
{ int a0[5]={0,0,0,0,0};
  int a1[5]={1,1,1,1,1};
  int a2[5]={0,1,1,1,1};
  int a3[5]={0,0,1,1,2};
  int a4[5]={0,1,2,3,4};
  int a5[5]={1,2,3,4,5};
  printf("\na0:%d",difference(a0,5));
  printf("\na1:%d",difference(a1,5));
  printf("\na2:%d",difference(a2,5));
  printf("\na3:%d",difference(a3,5));
  printf("\na4:%d",difference(a4,5));
  printf("\na5:%d",difference(a5,5));
  getch();
}
//=== Результат работы ===
a0:1
a1:1
a2:2
a3:3
a4:5
a5:5

Вариант 2. При первом просмотре определяем, содержится ли в исходном массиве хотя бы один нулевой элемент. Если содержится, то в переменную k0 заносим 1, в противном случае в k0 заносим 0. При втором проходе нулевые элементы исключаем из рассмотрения и сравниваем a[i] c a[j]. В случае равенства в элемент a[i] заносим 0. При третьем проходе подсчитываем ненулевые элементы и добавляем к сумме k0. Мы ограничимся только видоизмененной функцией difference:

int difference(int *a,int n)
{ int i,j,k0=0,m=0;
  for(i=0; i<n; i++)		//первый проход
    if(a[i]==0) { k0=1; break; }	//поиск нулевого элемента
  for(i=0; i<n-1; i++)	//второй проход
    { if(a[i]==0) continue;	//обход нулей
      for(j=i+1; j<n; j++)		//поиск дубликатов
        if(a[i]==a[j])
          { a[i]=0; break; }	//забой дубликата
    }
  for(i=0;i<n;i++)	//подсчет ненулевых элементов
    if(a[i]!=0) m++;
  return m+k0;
}

Вариант 3. Использование логической шкалы для подсчета количества разных элементов в целочисленном массиве с положительными данными. Если массив содержит отрицательные элементы, то при первом проходе можно определить максимальный из них и на эту величину сместить все значения. Идея использования логической шкалы состоит в том, что с каждым двоичным разрядом шкалы можно связать последовательно возрастающие целые числа. Сначала все биты логической шкалы сбрасываются в 0. Затем организуется цикл просмотра всех элементов массива, при котором мы определяем номер разряда в шкале, соответствующий проверяемому значению. Если в соответствующей позиции шкалы находится 0, то такое число встретилось впервые и к счетчику разных чисел надо добавить 1. В противном случае такое число уже попадалось и его надо пропустить.

Обратите внимание на следующие приемы работы со шкалой. Во-первых, под нее надо запросить память (желательно, чистую). Это можно сделать следующим образом. Если длина нашего массива не превышает 32767 элементов, то под логическую шкалу потребуется не более 4096 байт. Запрос памяти под шкалу лучше всего организовать через библиотечную функцию calloc. У нее задается два аргумента – количество элементов данных и число байт, необходимых для хранения каждого элемента:

b=calloc(4096,1);	//запрос чистой памяти

Во вторых, для перевода целого числа N в соответствующий разряд шкалы b удобнее воспользоваться номером байта шкала (переменная byte ) и номером бита (переменная bit ) в этом байте. Кроме этого нам потребуется массив из 8 однобайтовых констант, каждая из которых представляет один бит шкалы:

char mask[8]={128,64,32,16,8,4,2,1};

Для определения номеров байта и бита, соответствующих числу N, достаточно проделать два деления:

byte=N / 8;
  bit =N % 8;

В итоге окончательный вид функции difference таков:

int difference(int *a,int n)
{ int bit,byte,i,m=0;
  char mask[8]={128,64,32,16,8,4,2,1};
  char *b=(char *)calloc(4096,1);	//запрос и очистка памяти
  for(i=0; i<n; i++)
    { byte = a[i] / 8;
      bit = a[i] % 8;
      if((b[byte] mask[bit])==0)	//проверка бита шкалы
        { m++; b[byte] |= mask[bit]; }	//вписывание бита в шкалу
    }
  free(b);      //освобождение памяти
  return m;
}

При окончательной сборке программы надо не забыть подключить заголовочный файл alloc.h, в котором находится прототип функции calloc.

8.3. Программирование задач линейной алгебры

8.3.1. Работа с векторами

Создание программ для обработки одномерных массивов на языках C, C++ особых проблем не вызывает. Чтобы это доказать, продемонстрируем несколько функций, реализующих стандартные операции над векторами.

Пример 8.7. Вычисление нормы вектора.

#include <stdio.h>
#include <math.h>	//здесь находится прототип функции sqrt
#include <conio.h>
double norm(double *a, int n)
{ double s=0;
  for(int i=0; i<n; i++) s += a[i]*a[i];
  return sqrt(s);
}
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
  printf("norm=%f",norm(v1,5));
  getch();
}
//=== Результат работы ===
norm=7.416198

Функцией norm можно воспользоваться и для того, чтобы вычислить "норму" любого фрагмента вектора – достаточно вместо первого аргумента задать адрес начальной компоненты (например, v1[2] ), а в качестве второго аргумента количество обрабатываемых компонент.

Пример 8.8. Нормирование вектора.

#include <iostream.h>
#include <math.h>	//здесь находится прототип функции sqrt
#include <conio.h>
void norm_vec(double *a, int n)
{ double s=0;
  for(int i=0; i<n; i++) s += a[i]*a[i];
  s= sqrt(s);
  for(int i=0; i<n; i++) a[i] /= s;
}
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
  norm_vec(v1,5);
  for(int i=0;i<5;i++)
    cout << v1[i]<< "  ";
  getch();
}
//=== Результат работы ===
0.13484  0.26968  0.40452  0.53936  0.6742

Пример 8.9. Вычисление скалярного произведения двух векторов.

#include <stdio.h>
#include <conio.h>
double scal_prod(double *a, double *b,int n)
{ double s=0;
  for(int i=0; i<n; i++) s += a[i]*b[i];
  return s;
}
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
  printf("scal_prod=%f",scal_prod(v1,v1,5));
  getch();
}
//=== Результат работы ===
scal_prod=55.000000

Пример 8.10. Сумма векторов.

#include <stdio.h>
#include <conio.h>
void sum_vec(double *a,double *b,double *c,int n)
{ for(int i=0; i<n; i++) c[i]=a[i]+b[i]; }
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
  double v2[5]={1.,0.,1.,0.,1.};
  double v3[5];
  sum_vec(v1,v2,v3,5);
  for(int i=0;i<5;i++)
    printf("%3.0f",v3[i]);
  getch();
}
//=== Результат работы ===
  2  2  4  4  6

8.3.2.Работа с матрицами

Работу с двумерными массивами можно организовать двумя способами. Во-первых, операции над элементами двумерных массивов можно свести к операциям над одномерными массивами, используя приведенные индексы. Во-вторых, можно воспользоваться указателями на строки матрицы (как известно, имя массива одновременно является указателем на ее первую строку). Мы приведем примеры программ, демонстрирующие оба подхода.

Пример 8.11. Формирование единичной матрицы с приведенными индексами.

#include <stdio.h>
#include <math.h>
#include <conio.h>
void eye(int *a, int n)
{ int i,j;
  for(i=0; i<n; i++)
    for(j=0; j<n;j++)
      { if(i==j) a[i*n+j]=1;
        else a[i*n+j]=0;
      }  
}
void main()
{ int i,j,v[5][5];
  eye((int*)v,5);
  for(i=0;i<5;i++)
    { for(j=0;j<5;j++)
        printf("%3d",v[i][j]);
      printf("\n");
    }
  getch();
}
//=== Результат работы

Обратите внимание на то, что при обращении к функции eye указатель v приводится к типу ( int * ). После этого указатель будет "смотреть" на элементы массива, а не на его строки.

Пример 8.12. Сложение квадратных матриц. Поскольку в операции сложения участвуют n2 одноименных компонент матриц-слагаемых, то матрицы можно рассматривать как длинные вектора и производить сложение как с векторами:

#include <stdio.h>
#include <math.h>
#include <conio.h>
void add_mat(int *a,int *b,int *c,int n)
{ int i;
  for(i=0; i<n*n; i++)
    c[i]=a[i]+b[i];
}
void main()
{ int i,j,v3[3][3];
  int v1[3][3]={{1,2,3},{4,5,6},{7,8,9}};
  int v2[3][3]={{0,0,1},{0,0,2},{0,0,3}};
  add_mat((int*)v1,(int*)v2,(int*)v3,3);
  for(i=0;i<3;i++)
    { for(j=0;j<3;j++)
        printf("%3d",v3[i][j]);
      printf("\n");
    }
  getch();
}
//=== Результат работы ===

Пример 8.13.Умножение квадратных матриц с использованием приведенных индексов.

#include <stdio.h>
#include <conio.h>
void mult_mat(int *a,int *b,int *c,int n)
{ int i,j,k,s;
  for(i=0; i<n; i++)
    for(j=0; j<n;j++)
      { s=0;
        for(k=0;k<n;k++)
          s += a[i*n+k]*b[k*n+j];	//s=s+ai,k*bk,j
        c[i*n+j]=s;				//ci,j=s
      }
}
void main()
{ int i,j,v3[2][2];
  int v1[2][2]={{1,2},{3,4}};
  int v2[2][2]={{5,6},{7,8}};
  mult_mat((int*)v1,(int*)v2,(int*)v3,2);
  for(i=0;i<2;i++)
    { for(j=0;j<2;j++)
        printf("%4d",v3[i][j]);
      printf("\n");
    }
  getch();
}
//=== Результат работы ===

Пример 8.14. Транспонирование матрицы с использованием массива указателей на строки.

#include <stdio.h>
#include <conio.h>
void transp(int *p[],int n)
{ int tmp,i,j;
  for(i=0; i<n-1; i++)
    for(j=i+1; j<n; j++)
      { tmp=p[i][j]; p[i][j]=p[j][i]; p[j][i]=tmp; }
}
void main()
{ int v[4][4]={{ 1, 2, 3, 4},
               { 5, 6, 7, 8},
               { 9,10,11,12},
               {13,14,15,16}};
//массив указателей на строки
  int *p[4]={(int *)v[0],(int *)v[1],(int *)v[2],(int *)v[3]};
  transp(p,4);
  for(int i=0; i<4; i++)
    { for(int j=0;j<4;j++)
        printf("%3d",v[i][j]);
      printf("\n");
    }
  getch();
}
//=== Результат работы ===

Массив указателей p на строки двумерного массива v может быть сформирован и другими способами:

int *p[4]={(int *)v,(int *)(v+1),(int *)(v+2),(int *)(v+3)};
  int *p[4]={v[0],v[1],v[2],v[3]};
  int *p[4]={*v,*(v+1),*(v+2),*(v+3)};

Очевидно, что указатель p[0] "смотрит" на элемент v[0][0]. Поэтому указатель p[0][1]=p[0]+1 "смотрит" на элемент v[0][1], указатель p[0][2] – на элемент v[0][2] и т.д. Можно было бы видоизменить заголовок функции transp следующим образом:

void transp(int **p,int n)

Все эти модификации ничего не меняют в алгоритмах работы программ.

8.4. Поиск

Задача поиска формулируется следующим образом: задан массив a, содержащий n однотипных элементов (чисел, строк, записей и т.п.). Нужно установить, содержится ли в этом массиве заданный объект q. При положительном ответе следует дополнительно сообщить порядковый номер (индекс j ), найденного объекта ( a[j]=q ).

8.4.1. Последовательный поиск

Классический алгоритм последовательно поиска в неупорядоченном массиве состоит из четырех следующих шагов:

В книге Д.Кнута "Искусство программирования" имеется упоминание об усовершенствовании приведенного выше алгоритма. В цикле этого алгоритма содержится два сравнения. Чтобы исключить одно из них (условие окончания цикла) к массиву a добавляют еще один элемент, равный q. Тогда необходимость в проверке j<n+1 отпадает. Перед выдачей результата надо убедиться в том, что найденный индекс не равен n+1. Но такая проверка выполняется всего один раз. При программировании на языке ассемблера не требуется добавлять a[n+1]. Проще организовать поиск в обратном порядке – с последнего элемента массива. Для этого в языке ассемблера используется команда LOOP, совмещающая изменение счетчика цикла ( j-- ) и возврат в начало цикла при $$j\ne 0$$.

Трудоемкость классического последовательного поиска можно оценить только в среднем. В лучшем случае первое же сравнение может дать ответ ( q=a[1] ). В худшем случае придется перебрать все n элементов. В среднем на поиск будет затрачено n/2 сравнений.

Функция ssearch, реализующая последовательный поиск, устроена довольно просто:

int ssearch(int q, int *a, int n)
{ register int j;
  for(j=0; j<n;j++) 
    if(q==a[j]) return j;
  return -1;
}

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

8.4.2. Двоичный поиск

Двоичный поиск можно применить только в том случае, если исходный массив упорядочен, например, по возрастанию величин объектов. Тривиальные случаи типа q<a[1] или q>a[n] не рассматриваются, хотя ничего не стоит подключить к поиску и такие проверки. Идея двоичного поиска заключается в уменьшении вдвое зоны поиска на каждом шаге (отсюда и второе название метода – деление пополам). Сначала искомый объект q сравнивается со средним элементом массива. В зависимости от результата сравнения на следующий шаг остается первая или вторая половина массива. Оставшаяся половина вновь делится на 2, и так продолжается до тех пор, пока зона поиска не сузится до двух элементов. В этом случае либо объект q совпадает с одним из этих элементов, либо продолжает сохраняться строгое неравенство с обеими границами.

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

int bsearch(int q, int *a, int n)
{ register int left=0,right=n-1,mid;
  if(q<a[0] || q>a[n-1]) return -1;
  for(;left<=right;)
    { mid=(left+right)/2;
      if(q<a[mid]) right=mid-1;
      else if(q>a[mid]) left=mid+1;
      else return mid;
    }
  return -1;
}

Максимальное количество шагов, которое требуется для двоичного поиска, оценивается ближайшим целым к log2n. Для массива в 1000 элементов прямой поиск в среднем затрачивает 500 шагов, тогда как двоичный поиск ограничивается 10 шагами.

В реальных задачах типа поиска в телефонном справочнике к массиву данных можно добавить несколько отсортированных массивов-указателей – по фамилиям, по телефонам, по адресам. Сам массив исходных данных при этом не сортируется.

8.5. Сортировка массивов.

Сортировка числовых и нечисловых данных – одна из важнейших процедур обработки информации, т.к. она существенно ускоряет последующий поиск тех или иных объектов. О том, какое внимание уделяется различным алгоритмам сортировки, свидетельствует специальный том Д.Кнута "Искусство программирования для ЭВМ: Сортировка и поиск" объемом порядка 840 стр. Надо отметить, что оценка трудоемкости различных методов сортировки представляет собой довольно сложную математическую задачу. Те оценки, которые приведены ниже, заимствованы из литературных источников.

Мы рассмотрим несколько разных алгоритмов сортировки – от самых простых и самых медленных до одного из наиболее эффективных.

8.5.1. Сортировка методом пузырька

Идея метода состоит в сравнении двух соседних элементов, в результате чего меньшее число (более легкий "пузырек") перемещается на одну позицию влево. Обычно просмотр организуют с конца, и после первого прохода самое маленькое число перемещается на первое место. Затем все повторяется от конца массива до второго элемента и т.д. Известен и другой вариант пузырьковой сортировки, в котором также сравнивают два соседних элемента, и если хотя бы одна из смежных пар была переставлена, то просмотр начинают с самого начала.

Функция bubble, реализующая первый алгоритм пузырьковой сортировки приведена ниже:

void bubble(int *x, int n)
{ register int i,j;
  int tmp;
  for(i=1;i<n;i++)
    for(j=n-1;j>=i; j--)
      if(x[j-1]>x[j])
        { tmp=x[j-1]; x[j-1]=x[j]; x[j]=tmp; }
}

Более известный алгоритм пузырьковой сортировки реализован в функции bubble1. В ней использована флажковая переменная q, которая принимает ненулевое значение в случае перестановки какой-либо смежной пары:

void bubble1(int *x, int n)
{ register int i,j;
  int tmp,q;
m: q=0;
  for(i=1;i<n-1;i++)
    if(x[i]>x[i+1])
      { tmp=x[i]; x[i]=x[i+1]; x[i+1]=tmp; q=1;}
  if(q) goto m;
}

Пузырьковая сортировка неплохо работает, когда в исходных данных многие элементы уже упорядочены. Если исходный массив уже отсортирован, то работа функции ограничивается первым проходом. В худшем случае (массив упорядочен по убыванию) количество сравнений составляет n*(n-1)/2, а количество перестановок достигает 3*n*(n-1)/2. Среднее количество перестановок равно 3*n*(n-1)/4.

8.5.2. Сортировка методом отбора

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

void select(int *x, int n)
{ register int i,j,k;
  int q,tmp;
  for(i=0; i<n-1;i++)
    { q=0; k=i; tmp=x[i];
      for(j=i+1; j<n; j++)
        { if(x[j]<tmp)
            { k=j; tmp=x[j]; q=1; }
        }
      if(q) { x[k]=x[i]; x[i]=tmp; }
    }
}

Оценка трудоемкости метода отбора:

8.5.3. Сортировка методом вставки

Идея метода: последовательное пополнение ранее упорядоченных элементов. На первом шаге сортируются два первых элемента. Затем на свое место среди них вставляется третий элемент. К трем упорядоченным добавляется четвертый, который занимает свое место в четверке и т.д. Примерно так игроки упорядочивают свои карты при сдаче их по одной. Функция insert, реализующая описанную процедуру, приведена ниже:

void insert(int *x, int n)
{ register int i,j;
  int tmp;
  for(i=1;i<n;i++)
    { tmp=x[i];
      for(j=i-1;j>=0  tmp<x[j]; j--)
        x[j+1]=x[j];
      x[j+1]=tmp;
    }
}

Трудоемкость метода: количество сравнений зависит от исходной упорядоченности массива. Если массив уже отсортирован, то все равно потребуется 2*(n-1) сравнение. Если массив упорядочен по убыванию, то число сравнений возрастает до n*(n+1)/2.

8.5.4. Сортировка методом Шелла

В 1959 году сотрудник фирмы IBM D.L. Shell предложил оригинальный алгоритм сортировки. По его предложению сначала сортируются элементы, отстоящие друг от друга на 3 позиции, затем – на две позиции и, наконец, сортируются смежные элементы. В дальнейшем экспериментальным путем были найдены более удачные расстояния между сортируемыми элементами: 9 $$\to$$ 5 $$\to$$ 3 $$\to$$ 2 $$\to$$ 1. Среднее время работы усовершенствованного алгоритма Шелла порядка n1.2. Это существенно лучше, чем характерная для трех предыдущих методов величина порядка n2.

void shell(int *x, int n)
{ register int i,j,gap,k;
  int xx;
  char a[5]={9,5,3,2,1};
  for(k=0;k<5;k++)
    { gap=a[k];
      for(i=gap;i<n;i++)
        { xx=x[i];
          for(j=i-gap; xx<x[j]  j>=0; j=j-gap)
            x[j+gap]=x[j];
          x[j+gap]=xx;
        }
     }
}

8.5.5.Быстрая сортировка

Известный математик C.A.R. Hoare в 1962 году опубликовал алгоритм быстрой сортировки, за которым закрепилось название quicksort. Основная идея быстрой сортировки напоминает метод поиска делением пополам. Сначала выбирается средний элемент в сортируемом массиве. Все, что больше этого элемента переносится в правую часть массива, а все, что меньше – в левую. После первого шага средний элемент оказывается на своем месте. Затем аналогичная процедура повторяется для каждой половины массива. На каждом последующем шаге размер обрабатываемого фрагмента массива уменьшается вдвое. Количество операций, которое требуется для реализации этой процедуры, оценивается константой n*log2n. Это еще быстрее, чем сортировка Шелла. В отличие от предыдущих функций быстрая сортировка оформлена из двух функций – quick, которая допускает принятое в других функциях обращение, и рекурсивной процедуры qs:

void quick(int *x, int n)
{ qs(x,0,n-1); }
//----------------------------------
void qs(int *x,int left,int right)
{ register int i,j;
  int xx,tmp;
  i=left; j=right;
  xx=x[(left+right)/2];
  do { while(x[i]<xx  i<right)i++;
       while(xx<x[j]  j>left) j--;
       if(i<=j)
         { tmp=x[i]; x[i]=x[j];
           x[j]=tmp; i++; j--;
         }
      }
   while(i<=j);
   if(left<j) qs(x,left,j);
   if(i<right)qs(x,i,right);
}

Головная программа, предназначенная для тестирования и хронометража функций сортировки, приведена ниже. Заложенная в ней константа MAX для целей отладки принимает значение 20. Для хронометража методов сортировки ее надо увеличить до 100000 (BCB массивы такого размера допускает).

#include <iostream.h>
#include <conio.h>
#include <dos.h>
#define MAX 20
void bubble(int *x,int n);
void select(int *x,int n);
void insert(int *x,int n);
void shell(int *x,int n);
void quick(int *x,int n);
void qs(int *x,int left,int right);
void main()
{ int num[MAX],i;
  int t1,t2;
/* при отладке включить этот фрагмент
  cout << "Before sort:\n";
  for(i=0; i<MAX; i++)
    { num[i]=random(MAX);
      cout << num[i] << " ";
    }
  cout << endl;
*/
  t1=GetTickCount();
//  bubble(num,MAX);
//  select(num,MAX);
//  insert(num,MAX);
//  shell(num,MAX);
  quick(num,MAX);
  t2=GetTickCount();
  cout << t2-t1;
/* при отладке включить этот фрагмент
  cout << "After sort:" << endl;
  for(i=0; i<MAX; i++)
    cout << num[i] << " ";
  cout << endl;
*/
  cout << "end";
  getch();
}
//Методы сортировки

В таблице 8.1 приведены данные работы каждой функции сортировки на массиве длиной в 100000 элементов на компьютере типа Pentium 4 (частота 2 ГГц). Сортируемый массив заполнялся случайными числами (для каждой функции набор исходных данных был одинаков).

8.6. Слияние отсортированных массивов

Довольно много методов сортировки построено на сортировке фрагментов массивов с последующим объединением (слиянием) двух или более фрагментов в общий массив. Ниже приведена одна из реализаций объединения двух отсортированных массивов a и b, содержащих, соответственно, по ka и kb упорядоченных по возрастанию целых чисел. Чего-то особенного в алгоритме слияния нет – надо поочередно просматривать претендентов из обоих массивов и вставлять нужный из них в результирующий массив. Единственное, за чем приходится следить – не исчерпался ли тот или иной поставщик данных. Несмотря на использование в функции merge трех операторов goto, приведенный вариант представляет собой наиболее эффективную программу слияния.

#include <stdio.h>
#include <conio.h>
void merge(int *a,int ka,int *b, int kb, int *c)
{ int ja=0,jb=0,jc;
  for(jc=0; jc<ka+kb; jc++)
    { if(ja==ka) goto mb;
      if(jb==kb) goto ma;
      if(a[ja]<b[jb]) goto ma;
mb:   c[jc]=b[jb]; jb++; continue;
ma:   c[jc]=a[ja]; ja++;
    }
}
#define na 3
#define nb 4
void main()
{ int j,a[na]={0,2,4},b[nb]={1,3,5,7};
  int c[na+nb];
  for(j=0; j<na; j++) printf("%4d",a[j]);
  printf("\n");
  for(j=0; j<nb; j++) printf("%4d",b[j]);
  printf("\n");
  merge(a,na,b,nb,c);
  for(j=0; j<na+nb; j++) printf("%4d",c[j]);
  getch();
}
//=== Результат работы ===
   0   2   4
   1   3   5   7
   0   1   2   3   4   5   7

8.7. Динамические массивы.

К динамическим массивам относятся массивы, память под которые выделяется работающей программе по запросам, предусмотренным программистом. Не следует путать их с локальными массивами функций, память под которые автоматически выделяется при обращении к функции и также автоматически возвращается при выходе из функции. Память, выделенная под динамические массивы, освобождается в результате вызова специальных процедур, которые должны быть предусмотрены в тексте программы.

Пусть q – указатель на одномерный массив с элементами типа type_q. Тогда запрос на выделение памяти без ее предварительной очистки выполняется с помощью функции malloc:

q=(type_q *)malloc(n_byte);

Приведение к типу данных потребовалось потому, что функция malloc возвращает указатель типа void. Аргументом функции malloc является запрашиваемое количество байт. Необходимо иметь в виду, что данные типа int в 16-битной системе программирования (например, BC 3.1 под управлением MS-DOS) занимают по 2 байта, а в 32-битной среде типа BCB – по 4 байта.

Аналогичный запрос на выделении памяти с ее предварительной очисткой выполняется с помощью функции calloc:

q=(type_q *)calloc(n_el,sizeof(type_q));

В отличие от предыдущей функции здесь уже два аргумента – количество элементов массива ( n_el ) и длина каждого элемента в байтах sizeof(type_q).

Прототипы обеих функций находятся в заголовочных файлах alloc.h и stdlib.h. Если по каким-то причинам память выделить не удалось, каждая из функций возвращает нулевой указатель ( q==NULL ).

После выделения блока памяти по malloc или calloc его можно перераспределить, изменив ранее объявленную длину:

q=(type_q *)realloc(q,new_len);

Если новая длина больше предыдущей, то содержимое массива q копируется в начало нового блока памяти. Если новая длина меньше предыдущей, то в новом блоке сохраняются значения только начала старого массива. Если new_len=0, то это эквивалентно освобождению занимаемого блока памяти.

После того, как массив q будет использован и больше не понадобится, выделенную память надо возвратить с помощью функции free:

free(q);

Освобождение памяти не сбрасывает указатель q, поэтому с целью предупреждения возможных ошибок в дальнейшем его следует обнулить (операционная система Windows блокирует запись по нулевому адресу):

q=NULL;    //или q=0;

Некоторое представление о работе описанных функций дает следующий пример:

#include <alloc.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
void main()
{ int j,*p,s;
  char *str="abcdefghijk",*s1;
  p=(int *)malloc(4000);        //запрос "грязной" памяти
  for(s=0,j=0; j<1000; j++) s += p[j];
  printf("s=%d",s);             //улика - память "грязная"
  for(j=0; j<1000; j++) p[j]=j; //роспись выделенной памяти
  printf("\np[500]=%d",p[500]); //выборочная проверка
  free(p);                      //освобождение памяти
  p=(int *)calloc(1000,sizeof(int)); //запрос чистой памяти
  for(s=0,j=0; j<1000; j++) s += p[j];
  printf("\ns=%d",s);           //алиби - память чистая
  free(p);                      //освобождение памяти
  s1=(char *)calloc(20,1);      //запрос памяти под строку
  strcpy(s1,str);               //копирование данных
  printf("\ns1=%s",s1);         //вывод старой строки
  s1=(char*)realloc(s1,8);      //перераспределение памяти
  s1[5]=0x0;                    //признак конца новой строки
  printf("\ns1=%s",s1);         //вывод новой строки
  getch();
}
//=== Результат работы ===
s=-2138551277
p[500]=500
s=0
s1=abcdefghijk
s1=abcde

В языке C++ появились дополнительные средства для запроса и освобождения памяти:

q = new type_q;		//запрос памяти под скалярную переменную
  q = new type_q[n_el];	//запрос памяти под массив из n_el элементов
  delete q;			//освобождение памяти из-под скаляра
  delete []q;			//освобождение памяти из-под массива

Динамическое выделение памяти под скалярную переменную можно совместить с ее инициализацией:

int v=new int(5);	//после выделения памяти v=5

Память, выделяемую с помощью оператора new под динамические массивы, таким образом инициализировать нельзя.