Таблица 0.4: Среднее время поиска (мсек)

4. Тексты программ

4.1 Коды для сортировки вставками

typedef int T;/* type of item to be sorted */

typedef int tbllndex; /* type of subscript */

#define compGT(a,b) (a > b)

void insertSort(T *a, tblIndex lb, tblIndex ub) {

tblIndex i, j;

/**************************

* sort array a[lb..ub] * **************************/

for (i = lb + 1; i <= ub;{

t = a[i];

/* Shift elements down until */ /* insertion point found.*/

for (j =j >= lb && compGT(a[j], t); j--)

a[j+1] = a[j];

/* insert */

a[j+1] = t;

4.2 Коды для сортировки Шелла

typedef int T;/* type of item to be sorted */

typedef int tbllndex; /* type of subscript */

#define compGT(a,b) (a > b)

void shellSort(T *a, tbllndex lb, tbllndex ub) { tbllndex n, h, i, j;

/**************************

* sort array a[lb..ub] * **************************/

/* compute largest increment */ n = ub - lb + 1; h = 1; if (n < 14) h = 1;

else if (sizeof(tbllndex) == 2 && n > 29524)

h = 3280; else {

while (h < n) h = 3*h + 1;

while(h> 0) {

/* sort-by-insertion in increments of h */ for (i = lb + h; i <= ub;{

t = a[i];

for (j = i-h; j >= lb && compGT(a[j], t); j -= h)

a[j+h] = a[j]; a[j+h] = t;

/* compute next increment */

h /= 3;