, . , . , . O (n 1.25), O (n 1.5). . [1998] [Knuth].
. 2.2(a) . 1, 3 5 , 1. , . , 2. 2 + 2 + 1 = 5 .
. 2.2(b) . , 2. 3 1: 2, 3 1 2, 2. 5 2: 2, 5, 2. .. 2, 1, .. . 1 + 1 + 1 = 3 . , , 1, .
. 2-2.
. , , . 1. , . , . [Knuth] h N:
h 1 = 1, h s+1 = 3 h s + 1,... h t, h t+2 >= N.
h:
h1 = 1
h2 = (3 x 1) + 1 = 4
h3 = (3 x 4) + 1 = 13
h4 = (3 x 13) + 1 = 40
h5 = (3 x 40) + 1 = 121
100, s, h s >= 100. , s = 5. . , : 13-4-1. , , : h
h s-1 = [ h s / 3].
typedef T compGT , , . - h.
//
typedef int T; /* , */
typedef int tblIndex; /* */
#define compGT(a,b) (a > b)
void shellSort(T *a, tblIndex lb, tblIndex ub) {
tblIndex n, h, i, j;
T t;
/*********************************
* a[lb..ub] *
*********************************/
/* */
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) {
/* 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;
}
/* */
h /= 3;
}
}
, . - , .. , - QuickSort -.
O (n lg n) O (n 2) . , , . . , , .. . [1990] [Cormen].
, . Partition (. 2.3) . , , , , - .
int function Partition (Array A, int Lb, int Ub); begin A [ Lb ]... A [ Ub ]; A [ Lb ]... A [ Ub ] : <= >= ; end; procedure QuickSort (Array A, int Lb, int Ub); begin if Lb < Ub then M = Partition (A, Lb, Ub); QuickSort (A, Lb, M - 1); QuickSort (A, M + 1, Ub); end; |
. 2.3.
. 2.4(a) (pivot) 3. . i , , j , . - . . 2.4(b). QuickSort , , . 2.4(c).
2-4. Quicksort
. , , .. . , . , Partition n , O (n lg n).
Partition (A [ Lb ]). , . , , , . , . Partition : , , Ub - Lb . , QuickSort 1. n , O (n 2). - . .
|
|
typedef T compGT , , .
typedef int T; /* , */
typedef int tblIndex; /* */
#define ompGT(a,b) (a > b)
tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
T t, pivot;
tblIndex i, j, p;
/**********************************
* a[lb..ub] *
**********************************/
/* */
p = lb + ((ub - lb)>>1);
pivot = a[p];
a[p] = a[lb];
/* lb+1..ub */
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++;
}
/* a[j] */
a[lb] = a[j];
a[j] = pivot;
return j;
}
void quickSort(T *a, tblIndex lb, tblIndex ub) {
tblIndex m;
/**********************************
* a[lb..ub] *
**********************************/
while (lb < ub) {
/* */
if (ub - lb <= 12) {
insertSort(a, lb, ub);
return;
}
/* */
m = partition (a, lb, ub);
/* */
/* */
if (m - lb <= ub - m) {
quickSort(a, lb, m - 1);
lb = m + 1;
} else {
quickSort(a, m + 1, ub);
ub = m - 1;
}
}
}
:
partition , . , . , partition .
insertSort. - " " . , 12 , . - .
, . - . QuickSort . 2.3.
. , .
qsort QuickSort. .
//
#include <limits.h>
#define MAXSTACK (sizeof(size_t) * CHAR_BIT)
static void exchange(void *a, void *b, size_t size) {
size_t i;
/*************
* a,b *
*************/
for (i = sizeof(int); i <= size; i += sizeof(int)) {
int t = *((int *)a);
*(((int *)a)++) = *((int *)b);
*(((int *)b)++) = t;
}
for (i = i - sizeof(int) + 1; i <= size; i++) {
char t = *((char *)a);
|
|
*(((char *)a)++) = *((char *)b);
*(((char *)b)++) = t;
}
}
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *)) {
void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
int sp;
unsigned int offset;
lbStack[0] = (char *)base;
ubStack[0] = (char *)base + (nmemb-1)*size;
for (sp = 0; sp >= 0; sp--) {
char *lb, *ub, *m;
char *P, *i, *j;
lb = lbStack[sp];
ub = ubStack[sp];
while (lb < ub) {
/* 1- */
offset = (ub - lb) >> 1;
P = lb + offset - offset % size;
exchange (lb, P, size);
/* */
i = lb + size;
j = ub;
while (1) {
while (i < j && compar(lb, i) > 0) i += size;
while (j >= i && compar(j, lb) > 0) j -= size;
if (i >= j) break;
exchange (i, j, size);
j -= size;
i += size;
}
/* A[j] */
exchange (lb, j, size);
m = j;
/* , */
*/
if (m - lb <= ub - m) {
if (m + size < ub) {
lbStack[sp] = m + size;
ubStack[sp++] = ub;
}
ub = m - size;
} else {
if (m - size > lb) {
lbStack[sp] = lb;
ubStack[sp++] = m - size;
}
lb = m + size;
}
}
}
}
2.1 , .
2.1.
- | (s) | |||||
1,630 | ||||||
4,096 | 34,183 | 20,016 | 1,908 | |||
65,536 | 658,003 | 460,737 | 2,436 | |||
<DIV ALIGN=right></DIV>
: , . , :
. , . - , .
. . . . , , .
. , , (. 1.1). 2.2 . , , 2.3.
. , , 2.2. .
2.2.
- | . | |||||||
O (n 2) | O (n 2) | |||||||
O (n 1.25) | O (n 1.5) | |||||||
O (n lg n) | O (n 2) | |||||||
2.3.
- | quicksort | ||
39 s | 45 s | 51 s | |
4,969 s | 1,230 s | 911 s | |
4,096 | 1.315 sec | .033 sec | .020 sec |
65,536 | 416.437 sec | 1.254 sec | .461 sec |
|
|
<DIV ALIGN=right></DIV>
. Pascal. , .
.
" " .. 1959 . 8 .
1 2 3 4 1 2 3 4
4-: 44 55 12 42 94 18 06 67
1 2 1 2 1 2 1 2
: 44 18 06 42 94 55 12 67
1 1 1 1 1 1 1 1
1-: 06 18 12 42 44 55 94 67
: 06 12 18 42 44 55 67 94
, . 4-. . , , . 2-. 1-. , , , , . , . , , , i- , 2i-. , , 1, . , , . , . t h[1],h[2],...,h[t] :
h[t] = 1 h[i+1] < h[i]
h- , , , . , h- , . A[0], h[1] , , :
A: array [-h[1].. n] of item;
, ShellSort t=4.
procedure ShellSort;
const t=4;
var i,j,k,s: index; x: item; m: 1..t;
h: array[1..t] of integer;
begin h[1]:=9; h[2]:= 5; h[3]:=3; h[4]:=1;
for m:=1 to t do
begin k:=h[m]; s:=-k; { }
for i:= k+1 to n do
begin x:=A[i]; j:=i-k;
if s=0 then s:=-k; s:=s+1; A[s]:=x;
while (x.key < A[j].key) do
begin A[j+k]:=A[j]; j:=j-k;
end;
A[j+k]:=x;
end;
end;
end;
. , i - , , . : x1:x2,x3:x4,,xn-1:xn, (.., ) .. n=8 :
94
55 94
55 42 94 67
44 55 12 42 94 18 06 67
, n-1 ; , ( ) : , . , -¥ .
|
|
procedure turnir_sort;
Const MAX_VALUE=-32767;
Type
index1 = 1.. 2*n-1;
item1 = record
key: integer; { }
adres: index; { }
end;
var i,j,j1:index1;
B:array [index1] of item1;
begin
for i:=n to 2*n-1 do
begin
B[i].key:=A[i-n+1].key;
B[i].adres:=i;
end;
i:=2*n-1;j:=1;
repeat { }
if B[i].key>B[i-1].key then j:=i else j:=i-1;
B[j div 2].key:=B[j].key;
B[j div 2].adres:=B[j].adres;
i:=i-2;
until(i<3);
A[1].key:=B[1].key;
j1:=2;
repeat { }
if ((B[1].adres mod 2)=0) then i:=B[1].adres+1
else i:=B[1].adres;
B[B[1].adres].key:=MAX_VALUE;
repeat
if B[i].key>B[i-1].key then j:=i else j:=i-1;
B[j div 2].key:=B[j].key;
B[j div 2].adres:=B[j].adres;
i:=i div 2;
if ((i mod 2)=0) then i:=i+1;
until(i<3);
A[j1].key:=B[1].key;
j1:=j1+1;
until(j1>n);
end;
, . - h, h h-1 ; , h .(. .)
94
67 18
44 55 12 06
, : i- 2 i 2 i +1. , , , :
I: 1 2 3 4 5 6 7 8
xi: 94 67 18 44 55 12 06 42
, , , , . n- , n-1 . , , , :
x1,,xn,
x1 xi
For i:=n downto 2 do
x1,,xi-1
.
, ? . , ; , . , RESTORE(j,k) xj,xj+1,,xk , , :
procedure RESTORE(j,k)
xm xj
if xj ¹ then xm xj
if xm>xj then
RESTORE(m,k)
, .
procedure RESTORE(var f,l:index);
var j,m:index; x:item;
begin
j:=f;
while(j<=(l div 2)) do
begin
if (2*j<l) and (A[2*j].key<A[2*j+1].key) then m:=2*j+1 else m:=2*j;
if (A[m].key>A[j].key) then
begin
x:=A[m]; A[m]:=A[j]; A[j]:=x;
j:=m;
end
else j:=l;
end;
end;
, () (xi, i =ë0.5nû+1,,n) RESTORE(i,n) i =ë0.5nû, ë0.5nû-1,,1 . , , . for ; for .
procedure piramid_sort;
var i,nn,o,o1:index; x:item;
begin
nn:=n; o:=1;
for i:=(nn div 2) downto 1 do RESTORE(i,nn);
for i:=nn downto 2 do
begin
x:=A[1];
A[1]:=A[i];
A[i]:=x;
o1:=i-1;
RESTORE(o,o1);
end;
end;
. , . . , . , n , . , n/2 , . , , , .
: - ( ), , , A[i] > , , A[i]<. " ", - . : , - . (. ). > < , - < >. .
procedure partition;
var w,x: item;
begin i:=1; j:=n;
" ;"
repeat
while (A[i].key < x.key) do i:=i+1;
while (x.key < A[j].key) do j:=j-1;
if (i<=j) then
begin w:=A[i]; A[i]:=A[j]; A[j]:=w;
i:=i+1; j:=j-1;
end;
until (i>j);
end;
, , , 42, 44 55 12 |42| 94 06 18 67 , , ,
18 06 12 |42| 94 55 44 67
i=5 j=3. A[1],...,A[i-1] =42, A[j+1],...,A[n] . , :
A[k].key <= x.key k=1,..., i-1,
A[k].key >= x.key k=j+1,..., n
,
A[k].key = x.key k=j+1,..., i-1
. , n , n/2 . , ,
while (A[i].key < x.key) do i:=i+1;
while (x.key < A[j].key) do j:=j-1;
, , . , , , . , .
, , . : , , .., . .
procedure QuickSort;
procedure sort (l,r: index);
var i,j: index; w,x: item;
begin i:=l; j:=r;
x:= A[(l+r) div 2];
repeat
while (A[i].key < x.key) do i:=i+1;
while (x.key < A[j].key) do j:=j-1;
if (i<=j) then
begin w:=A[i]; A[i]:=A[j]; A[j]:= w;
i:=i+1; j:=j-1;
end;
until (i>j);
if (l<j) then sort(l,j);
if (i<r) then sort(i,r)
end;
begin sort(1,n);
end; { QuickSort }
sort . - . . . , , .
- , . , , . , , . , ; . , , . , - , stack, s, . m .
procedure QuickSort1;
const m = 12;
var i,j,l,r: index;
x,w: item;
s: 0..m;
stack: array[1..m] of
record l,r: index end;
begin s:= 1; stack[1].l:=1; stack[1].r:=n;
repeat { }
l:=stack[s].l; r:=stack[s].r; s:=s-1;
repeat { A[l]... A[r] }
i:=l; j:=r; x:=A[(l+r) div2];
repeat
while (A[i].key < x.key) do i:=i+1;
while (x.key < A[j].key) do j:=j-1;
if (i<=j) then
begin w:=A[i]; A[i]:=A[j]; A[j]:=w;
i:= i+1; j:=j-1;
end;
until (i>j);
if (i<r) then
begin { }
s:=s+1; stack[s].l:=i; stack[s].r:=r;
end;
r:=j;
until (l>=r);
until (s=0);
end; { QuickSort1 }
- , , . - -. , - , ; , [1, N ], N - ( -). - . , . , (skip lists) - .
-
- -. O (1), - O (n). [1990] [Cormen] [1998] [Knuth]. , . , [Aho]. , [Aho] [Knuth], . , ?
- - , -. , . 3.1 hashTable - 8 . , . - 8 . 0 7 hashTable 0 7, .
. 3.1. -
, . , . . , 11, 11 8 3. , 11 , hashTable[3]. , . , , .
- , , -. . , -, ; .
- , . - . , , - . , -. . , unsigned char 8 , unsigned short int - 16, unsigned long int - 32.
( hashTableSize - ). . hashValue, 0 (hashTableSize - 1), -. :
typedef int HashIndexType;
HashIndexType Hash(int Key) {
return Key % HashTableSize;
}
hashTableSize. , , hashTableSize , - , - . , - , . , , hashTableSize, , Key . , hashTableSize , .
( hashTableSize 2 n). key , . (sqrt (5) - 1)/2 = 0.6180339887499. , , . 28, 158. 8- 158, 16- . 25 5 , . :
/* 8-bit index */
typedef unsigned char HashIndexType;
static const HashIndexType K = 158;
/* 16-bit index */
typedef unsigned short int HashIndexType;
static const HashIndexType K = 40503;
/* 32-bit index */
typedef unsigned long int HashIndexType;
static const HashIndexType K = 2654435769;
/* w=bitwidth(HashIndexType), size of table=2**m */
static const int S = w - m;
HashIndexType HashValue = (HashIndexType)(K * Key) S;
, , hashTableSize 1024 (210). 16- S 16 - 10 = 6. :
typedef unsigned short int HashIndexType;
HashIndexType Hash(int Key) {
static const HashIndexType K = 40503;
static const int S = 6;
return (HashIndexType)(K * Key) S;
}
( 256). 256. hashValue 0 255.
typedef unsigned char HashIndexType;
HashIndexType Hash(char *str) {
HashIndexType h = 0;
while (*str) h += *str++;
return h;
}
( 256). , ( XY YX). , , , " ". , .
typedef unsigned char HashIndexType;
unsigned char Rand8[256];
HashIndexType Hash(char *str) {
unsigned char h = 0;
while (*str) h = Rand8[h ^ *str++];
return h;
}
Rand8 - 256 . . ; (Pearson [1990]).
( <= 65536). , - 65536. , 1. 8- 16-.
typedef unsigned short int HashIndexType;
unsigned char Rand8[256];
HashIndexType Hash(char *str) {
HashIndexType h;
unsigned char h1, h2;
if (*str == 0) return 0;
h1 = *str; h2 = *str + 1;
str++;
while (*str) {
h1 = Rand8[h1 ^ *str];
h2 = Rand8[h2 ^ *str];
str++;
}
/* h is in range 0..65535 */
h = ((HashIndexType)h1 << 8)|(HashIndexType)h2;
/* use division method to scale */
Return h % HashTableSize
}
- , . 3.1, , . - . , , , , . n. 1, n. 2 , n /100 . , . 3.1, .
3.1. (s) hashTableSize. 4096 .
typedef T compGT , , . hashTableSize hashTable. - hash . insertNode . deleteNode , . findNode .
// -
typedef int T; /* type of item to be sorted */
#define compEQ(a,b) (a == b)
typedef struct Node_ {
struct Node_ *next; /* next node */
T data; /* data stored in node */
} Node;
typedef int hashTableIndex;
Node **hashTable;
int hashTableSize;
hashTableIndex hash(T data) {
/***********************************
* hash function applied to data *
***********************************/
return (data % hashTableSize);
}
Node *insertNode(T data) {
Node *p, *p0;
hashTableIndex bucket;
/************************************************
* allocate node for data and insert in table *
************************************************/
/* insert node at beginning of list */
bucket = hash(data);
if ((p = malloc(sizeof(Node))) == 0) {
fprintf (stderr, "out of memory (insertNode)\n");
exit(1);
}
p0 = hashTable[bucket];
hashTable[bucket] = p;
p->next = p0;
p->data = data;
return p;
}
void deleteNode(T data) {
Node *p0, *p;
hashTableIndex bucket;
/********************************************
* delete node containing data from table *
********************************************/
/* find node */
p0 = 0;
bucket = hash(data);
p = hashTable[bucket];
while (p &&!compEQ(p->data, data)) {
p0 = p;
p = p->next;
}
if (!p) return;
/* p designates node to delete, remove it from list */
if (p0)
/* not first node, p0 points to previous node */
p0->next = p->next;
else
/* first node on chain */
hashTable[bucket] = p->next;
free (p);
}
Node *findNode (T data) {
Node *p;
/*******************************
* find node containing data *
*******************************/
p = hashTable[hash(data)];
while (p &&!compEQ(p->data, data))
p = p->next;
return p;
}
1 . , , . , , . - "" . O (lg n). - . - O (n). [1990] [Cormen].
- , . . 3.2. , k , , , : , , , k, , , - . , , , . . 3.2 20, - 4, 16, 37 43. - . 2.
. 3.2.
- , . , 16, , 16 < 20, . , 16 > 7, . - , 16.
. . , , . . 3.3 , . , , , , , .
. 3.3.
, , . 18 . 3.2 . 16, . 18 16, 18 16 (. 3.4).
, . , . . : "" , .
- . , . 3.4 20, 37. , . 3.5. . 20, . , , 20. , ( 38), ( 37); , , .
. 3.4. 18
. 3.5. 20
typedef T compGT , , . Node left, right , parent . data. , root, , , NULL. insertNode , .. . deleteNode, , (.. ), , . findNode , .
//
typedef int T; /* type of item to be sorted */
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
typedef struct Node_ {
struct Node_ *left; /* left child */
struct Node_ *right; /* right child */
struct Node_ *parent; /* parent */
T data; /* data stored in node */
} Node;
Node *root = NULL; /* root of binary tree */
Node *insertNode(T data) {
Node *x, *current, *parent;
/***********************************************
* allocate node for data and insert in tree *
***********************************************/
/* find x's parent */
current = root;
parent = 0;
while (current) {
if (compEQ(data, current->data)) return (current);
parent = current;
current = compLT(data, current->data)?
current->left: current->right;
}
/* setup new node */
if ((x = malloc (sizeof(*x))) == 0) {
fprintf (stderr, "insufficient memory (insertNode)\n");
exit(1);
}
x->data = data;
x->parent = parent;
x->left = NULL;
x->right = NULL;
/* insert x in tree */
if(parent)
if(compLT(x->data, parent->data))
parent->left = x;
else
parent->right = x;
else
root = x;
return(x);
}
void deleteNode(Node *z) {
Node *x, *y;
/*****************************
* delete node z from tree *
*****************************/
/* y will be removed from the parent chain */
if (!z || z == NULL) return;
/* find tree successor */
if (z->left == NULL || z->right == NULL)
y = z;
else {
y = z->right;
while (y->left!= NULL) y = y->left;
}
/* x is y's only child */
if (y->left!= NULL)
x = y->left;
else
x = y->right;
/* remove y from the parent chain */
if (x) x->parent = y->parent;
if (y->parent)
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
else
root = x;
/* y is the node we're removing */
/* z is the data we're removing */
/* if z and y are not the same, replace z with y. */
if (y!= z) {
y->left = z->left;
if (y->left) y->left->parent = y;
y->right = z->right;
if (y->right) y->right->parent = y;
y->parent = z->parent;
if (z->parent)
if (z == z->parent->left)
z->parent->left = y;
else
z->parent->right = y;
else
root = y;
free (z);
} else {
free (y);
}
}
Node *findNode(T data) {
/*******************************
* find node containing data *
*******************************/
Node *current = root;
while(current!= NULL)
if(compEQ(data, current->data))
return (current);
else
current = compLT(data, current->data)?
current->left: current->right;
return(0);
}
<DIV ALIGN=right></DIV>
-
, ,