Справочник Томас Ниман Thomas Niemann



Скачать 467.32 Kb.
страница8/12
Дата14.06.2013
Размер467.32 Kb.
ТипДокументы
1   ...   4   5   6   7   8   9   10   11   12

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

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



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

typedef int tblIndex; /* type of subscript */
#define compGT(a,b) (a > b)
void insertSort(T *a, tblIndex lb, tblIndex ub) {

T t;

tblIndex i, j;
/**************************

* sort array a[lb..ub] *

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

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

t = a[i];
/* Shift elements down until */

/* insertion point found. */

for (j = i-1; 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 tblIndex; /* type of subscript */
#define compGT(a,b) (a > b)
void shellSort(T *a, tblIndex lb, tblIndex ub) {

tblIndex n, h, i, j;

T t;
/**************************

* sort array a[lb..ub] *

**************************/
/* compute largest increment */

n = ub - lb + 1;

h = 1;

if (n < 14)

h = 1;

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

h = 3280;

else {

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

h /= 3;

h /= 3;

}
while (h > 0) {
/* sort-by-insertion in increments of h */

for (i = lb + h; i <= ub; i++) {

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;

}

}

4.3 Коды для быстрого поиска (функции Quicksort)



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

typedef int tblIndex; /* type of subscript */
#define CompGT(a,b) (a > b)
tblIndex partition(T *a, tblIndex lb, tblIndex ub) {

T t, pivot;

tblIndex i, j, p;
/*******************************

* partition array a[lb..ub] *

*******************************/
/* select pivot and exchange with 1st element */

p = lb + ((ub - lb)>>1);

pivot = a[p];

a[p] = a[lb];
/* sort lb+1..
ub based on pivot */


i = lb+1;

j = ub;

while (1) {

while (i < j && compGT(pivot, a[i])) i++;

while (j >= i && compGT(a[j], pivot)) j--;

if (i >= j) break;

t = a[i];

a[i] = a[j];

a[j] = t;

j--; i++;

}
/* pivot belongs in a[j] */

a[lb] = a[j];

a[j] = pivot;
return j;

}
void quickSort(T *a, tblIndex lb, tblIndex ub) {

tblIndex m;
/**************************

* sort array a[lb..ub] *

**************************/
while (lb < ub) {
/* quickly sort short lists */

if (ub - lb <= 12) {

insertSort(a, lb, ub);

return;

}
/* partition into two segments */

m = partition (a, lb, ub);
/* sort the smallest partition */

/* to minimize stack requirements */

if (m - lb <= ub - m) {

quickSort(a, lb, m - 1);

lb = m + 1;

} else {

quickSort(a, m + 1, ub);

ub = m - 1;

}

}

}

1   ...   4   5   6   7   8   9   10   11   12

Похожие:

Справочник Томас Ниман Thomas Niemann iconБердникова Дарья Владимировна Лингвистические особенности текстов произведений англо-шотландского фольклора Художественный текст, примером которого является баллада “Thomas the Rhymer” «Томас Рифмоплет»
Художественный текст, примером которого является баллада “Thomas the Rhymer” («Томас Рифмоплет»), несет в себе не только смысловое...
Справочник Томас Ниман Thomas Niemann iconДжефферсон томас
Джефферсон, томас (Jefferson, Thomas) (1743–1826), 3-й президент сша, автор Декларации независимости, архитектор, ученый, просветитель....
Справочник Томас Ниман Thomas Niemann iconТомас Роберт Мальтус Thomas Robert Malthus
Опыт о законе народонаселения и его воздействии на будущее улучшение общества с замечаниями о построениях гг. Годвина, Кондорсе и...
Справочник Томас Ниман Thomas Niemann iconТомас нагель что все это значит? Очень краткое введение в философию Thomas Nagel «What Does It All Mean? A very Short Introduction to Philosophy»
Нагель провел в стенах Корпус Кристи Колледжа в Оксфордском университете (Англия), где имел честь слушать лекции Джона Остина и получить...
Справочник Томас Ниман Thomas Niemann iconСправочник сталкера. Азбука выживания «Справочник сталкера. Азбука выживания»
Этот справочник, вы без труда обнаружите на схеме несколько принципиальных ошибок в действиях группы, приведших в конечном счете...
Справочник Томас Ниман Thomas Niemann iconСправочник Москва, 2004 год Организации социальной направленности района «Академический». Справочник
«Академический» юзао г. Москвы. Справочник, в первую очередь, адресован жителям района и округа, которые могут воспользоваться услугами,...
Справочник Томас Ниман Thomas Niemann iconПроект летней полевой игры по мотивам книги Thomas Malory "Le Morte Darthure"
Проект летней полевой игры по мотивам книги Thomas Malory “Le Morte Darthure” и других источников
Справочник Томас Ниман Thomas Niemann iconТомас гоббс гоббс, томас
Якова I, изучал философию в правление Карла I, был знаменит и находился под подозрением при Кромвеле и, наконец, вошел в моду как...
Справочник Томас Ниман Thomas Niemann iconСправочник по языку c я пишу на c с 1989 года. Этот краткий справочник был составлен мною очень давно

Справочник Томас Ниман Thomas Niemann iconСправочник "Тип мед персоналу" Добавлен новый справочник. Так как в справочник "Тип персоналу"
Тип мед персоналу” (это значение влияет на формирование отчетов). Всем должностям не медицинских специальностей присваивается значение...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org