第六章
Sorting
Sorting
and searching are among the most common ingredients of programing
system.
The
concept of an ordered set of elements is one that has considerable
impact on our daily lives. Consider, for example, the process of
finding a telephone number in a telephone directory. This process
called a search.
O
notation
To
be precise, given two functions f(n) and g(n), we say that f(n) is on
the order of g(n) or that f(n) is O(g(n)) if there exist positive
integers a and b such that f(n)<=a(g(n) for all n>=b
If
f(n) is O(g(n)), “eventually”(that is ,for n>=b) f(n) becomes
permanently smaller or equal to some multiple of g(n).
best
case
worst
case
average
case
buble
sort O(n^2)
P341
void
buble(int x[], int n)
{
int
hold, j, pass;
int
switched=TRUE;
for(pass=0;pass<n-1&&switched
== TRUE;pass++)
{
switched=FALSE;
for(j=0;j<n-pass-1;j++)
{
if(x[j]>x[j+1])
{
hold=x[j];
x[j]=x[j+1];
x[j+1]=hold
}
}
}
}
quick
sort O(nlogn)
P345
void
partition (int x[],int lb,int ub,int *pj)
{
int
a, down, temp, up;
a=x[lb]
/*a is the element whose final position is sought*/
up=ub;
down=lb;
while(down<up)
{
while(x[down]<=a
&& down < ub)
down++;
/*move up the array*/
while(x[up]>a)
up--
/*move down the array*/
if(down<up)
{
temp=x[down];
x[down]=x[up]
x[up]=temp;
}/*end
if*/
}//end
while
x[lb]=x[up];
x[up]=a;
*pj=up;
}
down-> up
25 57 48 37
12 92 86 33
down
比a大停下來
25 57 48 37
12 92 86 33
down up
25 57 48 37
12 92 86 33
down up
25 57 48 37
12 92 86 33
down
up
25 57 48 37
12 92 86 33
down up比a小停下來
25 57 48 37
12 92 86 33
down up
25 12 48 37
57 92 86 33***
down up
25 12 48 37
57 92 86 33
down,up
25 12 48 37
57 92 86 33
up down
25 12 48 37
57 92 86 33
up
down
12 25
48 37 57 92 86 33***
#define
MAXSTACK …
void
quicksort(int x[], int n)
{
int
i, j;
struct
bndtype{
int
lb;
int
ub;
}
newbnds;
/*stack
is used by the pop, push and empty functions.
struct
{
int
top;
struct
bndtype bounds[MAXSTACK];
}
stack;
stack.top=-1
newbnds.lb=0;
newbnds.up=n-1;
push(&stack,
&newbnds);
/*repeat
as long as there are any unsorted subarray on the stack*/
while(!empty(&stack)
{
popsub(&stack,&newbnds);
while(newbnds.ub>newbnds.lb)
{
/*process
next subarray*/
partition(x,newbnds.lb,newbnds.ub,&j);
/*stack
the larger subarray*/
if(j-newbnds.lb>newbnds.ub-j)
{
/*stack
lower array*/
i=newbnds.ub
newbnds.ub=j-1;
push(&stack,&newbnds)
/*process
upper subarray
newbnds.lb=j+1;
newbnds.ub=i;
}
else
{
/*stack
upper subarray
i=newbnds.lb;
newbnd.lb=j+1;
push(&stack,&newbnds);
/*process
lower subarray*/
newbnds.lb=i;
newbnds.up=j-1;
}
}
}
}
}
6.3
Selection and Tree Sorting
A
selection sort is one in which successive elements are selected in
order and place into proper sorted positions.
P352
O(n^2)
void
selectsort(int x[], int n)
{
int
i, indx, j, large;
for(i=n-1;i>0;i--)
{
/*place
the largest number of x[0] through */
/*x[i]
into larg and its index into indx */
large
= x[0];
indx=0;
for(j=1;j<=i;j++)
{
if(x[j]>large)
{
large=x[j];
indx=j;
}
x[indx]=x[i];
x[i]=large;
}
}
Binary
tree sort
worst
case O(n^2)
average
O(nlogn)
/*
establish the first element as root*/
tree=
maketree(x[0]);
/*
repeat for each successive element*/
for(i=1;i<n;i++)
{
y=x[i];
q=tree;
p=q;
/*travel
down the tree until a leaf is reached*/
while
(p!=null)
{
q=p;
if(y<info(p))
p=left(p);
else
p=right(p);
}
if(y<info(q))
setleft(q,y);
else
setright(q,y);
}
/*tree
is built, traverse it in inorder*/
intrav(tree)
Heap
sort
O(nlogn)
25
57 48 37 12 92 86 33
void
heapsort(int x[], int n)
{
int
i, elt, s, f, ivalue;
/*
preprocessing phase; create initial heap*/
for(i=1;i<n;i++)
{
elt
=x[i];
/*pqinsert(x,i,elt);*/
s=i;
f=
(s-1)/2;
while(s>0
&& x[f]<elt)
{
x[s]=x[f];
s=f;
f=(s-1)/2;
}
x[s]
=elt
}
/*
selection phase; repeatedly remove x[0] ,insert it*/
/*
in its proper position and adjust the heap*/
for(i=n-1;i>0;i--)
{
/*pqmaxdelete(x,i+1)*/
ivalue=x[i];
x[i]=x[0];
f=0;
/*s=largeson(0,i-1)*/
if(i==1)
s=-1;
else
s=1;
if(i>2
&& x[2]>x[1])
s=2;
while(s>=0
&& ivalue < x[s])
{
x[f]=x[s];
f=s;
/*s=largeson(f,i-1)*/
s=2*f+1;
if(s+1<=i-1
&& x[s] < x[s+1])
{
s=
s+1
}
if(s>i-1)
x=-1;
}
x[f]=ivalue;
}
}
6.4
Insertion Sort
O(n^2)
void
insertsort(int x[], int n)
{
int
i, k, y;
for(k=1;k<n;k++)
{
/*insert
x[k] into the sorted file*/
y=x[k];
/*move
down 1 position all elements greater than y*/
for(i=k-1;i>=0&&y<x[i];i--)
x[i+1]=x[i]
x[i+1]=y;
}
}
shell
sort
O(n(logn)^2)
void
shellsort(int x[],int n, int incrmnts[], int numinc)
{
for(incr=0;
incr < numinc; incr++)
{
span=incrmnts[incr];
for(j=span;j<n;j++)
{
y=x[j];
for(k=j-span;k>=0&&y<x[k];k-=span)
{
x[k+span]=x[k]
}
x[k+span]=y
}
}
}
#define
NUMELTS …
void
mergesort(int x[],int n)
{
int
aux[NUMELTS], i, j, k, l1,l2, size, u1, u2;
size=1;
/* Merge files of size 1*/
while(size
< n)
{
l1=0;
k=0;
while(l1+size<n)
{
l2=l1+size;
u1
= l2-1;
u2
= (l2+size-1<n)? l2+size-1:n-1;
for(
i=l1,j=l2;i<=u1&&j<=u2;k++)
{
if(x[i]<=x[j])
aux[k]=x[i++];
else
aux[k]=x[k++]
}
}
for(;i<=u1;k++)
aux[k]=x[i++];
for(;j<=u2;k++)
aux[k]=x[j++];
l1=u2+1;
for(i=l1;k<n;i++)
aux[k++]=x[i];
for(i=0;i<n;i++)
x[i]=aux[i];
size*=2;
}
}
[25] [57] [48] [37] [12] [92] [86] [33]
[25 57] [37 48] [12 92] [33 86]
[25 37 48 57] [12 33 86 92]
[12 25 33 37 48 57 86 92]
Radix
sort
for(k=least
significant digit;k<=most significant digit;k++)
{
for(i=0;i<n;i++)
{
y=x[i];
j=kth
digit of y
place
y at rear of queue[j]
}
}
for(qu=0;qu<10;qu++)
{
place
elements of queue[qu] in the next sequential position of x;
}
#define
NUMELTS ...
void
radixsort(int x[],int n)
{
int
front[10],rear[10];
struct
{
int
info;
int
next;
}
node[NUMELTS];
int
exp,first,i,j,k,p,q,y;
for(i=0;i<n-1;i++)
{
node[i].info=x[i];
node[i].next=i+1;
}
node[n-1].info=x[n-1];
node[n-1].next=-1;
first=0;
for(k=1;k<5;k++)
{
for(i=0;i<10;i++)
{
rear[i]=-1;
front[i]=-1
}
while(first!=-1)
{
p=first;
first=node[first].next;
y=node[p].info;
exp=(power(10,k-1);
j=(y/exp)%10
q=rear[j];
if(q==-1)
{
front[j]=p
else
{
node[q].next=p;
}第六章
Sorting
Sorting
and searching are among the most common ingredients of programing
system.
The
concept of an ordered set of elements is one that has considerable
impact on our daily lives. Consider, for example, the process of
finding a telephone number in a telephone directory. This process
called a search.
O
notation
To
be precise, given two functions f(n) and g(n), we say that f(n) is on
the order of g(n) or that f(n) is O(g(n)) if there exist positive
integers a and b such that f(n)<=a(g(n) for all n>=b
If
f(n) is O(g(n)), “eventually”(that is ,for n>=b) f(n) becomes
permanently smaller or equal to some multiple of g(n).
best
case
worst
case
average
case
buble
sort O(n^2)
P341
void
buble(int x[], int n)
{
int
hold, j, pass;
int
switched=TRUE;
for(pass=0;pass<n-1&&switched
== TRUE;pass++)
{
switched=FALSE;
for(j=0;j<n-pass-1;j++)
{
if(x[j]>x[j+1])
{
hold=x[j];
x[j]=x[j+1];
x[j+1]=hold
}
}
}
}
quick
sort O(nlogn)
P345
void
partition (int x[],int lb,int ub,int *pj)
{
int
a, down, temp, up;
a=x[lb]
/*a is the element whose final position is sought*/
up=ub;
down=lb;
while(down<up)
{
while(x[down]<=a
&& down < ub)
down++;
/*move up the array*/
while(x[up]>a)
up--
/*move down the array*/
if(down<up)
{
temp=x[down];
x[down]=x[up]
x[up]=temp;
}/*end
if*/
}//end
while
x[lb]=x[up];
x[up]=a;
*pj=up;
}
down-> up
25 57 48 37
12 92 86 33
down
比a大停下來
25 57 48 37
12 92 86 33
down up
25 57 48 37
12 92 86 33
down up
25 57 48 37
12 92 86 33
down
up
25 57 48 37
12 92 86 33
down up比a小停下來
25 57 48 37
12 92 86 33
down up
25 12 48 37
57 92 86 33***
down up
25 12 48 37
57 92 86 33
down,up
25 12 48 37
57 92 86 33
up down
25 12 48 37
57 92 86 33
up
down
12 25
48 37 57 92 86 33***
#define
MAXSTACK …
void
quicksort(int x[], int n)
{
int
i, j;
struct
bndtype{
int
lb;
int
ub;
}
newbnds;
/*stack
is used by the pop, push and empty functions.
struct
{
int
top;
struct
bndtype bounds[MAXSTACK];
}
stack;
stack.top=-1
newbnds.lb=0;
newbnds.up=n-1;
push(&stack,
&newbnds);
/*repeat
as long as there are any unsorted subarray on the stack*/
while(!empty(&stack)
{
popsub(&stack,&newbnds);
while(newbnds.ub>newbnds.lb)
{
/*process
next subarray*/
partition(x,newbnds.lb,newbnds.ub,&j);
/*stack
the larger subarray*/
if(j-newbnds.lb>newbnds.ub-j)
{
/*stack
lower array*/
i=newbnds.ub
newbnds.ub=j-1;
push(&stack,&newbnds)
/*process
upper subarray
newbnds.lb=j+1;
newbnds.ub=i;
}
else
{
/*stack
upper subarray
i=newbnds.lb;
newbnd.lb=j+1;
push(&stack,&newbnds);
/*process
lower subarray*/
newbnds.lb=i;
newbnds.up=j-1;
}
}
}
}
}
6.3
Selection and Tree Sorting
A
selection sort is one in which successive elements are selected in
order and place into proper sorted positions.
P352
O(n^2)
void
selectsort(int x[], int n)
{
int
i, indx, j, large;
for(i=n-1;i>0;i--)
{
/*place
the largest number of x[0] through */
/*x[i]
into larg and its index into indx */
large
= x[0];
indx=0;
for(j=1;j<=i;j++)
{
if(x[j]>large)
{
large=x[j];
indx=j;
}
x[indx]=x[i];
x[i]=large;
}
}
Binary
tree sort
worst
case O(n^2)
average
O(nlogn)
/*
establish the first element as root*/
tree=
maketree(x[0]);
/*
repeat for each successive element*/
for(i=1;i<n;i++)
{
y=x[i];
q=tree;
p=q;
/*travel
down the tree until a leaf is reached*/
while
(p!=null)
{
q=p;
if(y<info(p))
p=left(p);
else
p=right(p);
}
if(y<info(q))
setleft(q,y);
else
setright(q,y);
}
/*tree
is built, traverse it in inorder*/
intrav(tree)
Heap
sort
O(nlogn)
25
57 48 37 12 92 86 33
void
heapsort(int x[], int n)
{
int
i, elt, s, f, ivalue;
/*
preprocessing phase; create initial heap*/
for(i=1;i<n;i++)
{
elt
=x[i];
/*pqinsert(x,i,elt);*/
s=i;
f=
(s-1)/2;
while(s>0
&& x[f]<elt)
{
x[s]=x[f];
s=f;
f=(s-1)/2;
}
x[s]
=elt
}
/*
selection phase; repeatedly remove x[0] ,insert it*/
/*
in its proper position and adjust the heap*/
for(i=n-1;i>0;i--)
{
/*pqmaxdelete(x,i+1)*/
ivalue=x[i];
x[i]=x[0];
f=0;
/*s=largeson(0,i-1)*/
if(i==1)
s=-1;
else
s=1;
if(i>2
&& x[2]>x[1])
s=2;
while(s>=0
&& ivalue < x[s])
{
x[f]=x[s];
f=s;
/*s=largeson(f,i-1)*/
s=2*f+1;
if(s+1<=i-1
&& x[s] < x[s+1])
{
s=
s+1
}
if(s>i-1)
x=-1;
}
x[f]=ivalue;
}
}
6.4
Insertion Sort
O(n^2)
void
insertsort(int x[], int n)
{
int
i, k, y;
for(k=1;k<n;k++)
{
/*insert
x[k] into the sorted file*/
y=x[k];
/*move
down 1 position all elements greater than y*/
for(i=k-1;i>=0&&y<x[i];i--)
x[i+1]=x[i]
x[i+1]=y;
}
}
shell
sort
O(n(logn)^2)
void
shellsort(int x[],int n, int incrmnts[], int numinc)
{
for(incr=0;
incr < numinc; incr++)
{
span=incrmnts[incr];
for(j=span;j<n;j++)
{
y=x[j];
for(k=j-span;k>=0&&y<x[k];k-=span)
{
x[k+span]=x[k]
}
x[k+span]=y
}
}
}
#define
NUMELTS …
void
mergesort(int x[],int n)
{
int
aux[NUMELTS], i, j, k, l1,l2, size, u1, u2;
size=1;
/* Merge files of size 1*/
while(size
< n)
{
l1=0;
k=0;
while(l1+size<n)
{
l2=l1+size;
u1
= l2-1;
u2
= (l2+size-1<n)? l2+size-1:n-1;
for(
i=l1,j=l2;i<=u1&&j<=u2;k++)
{
if(x[i]<=x[j])
aux[k]=x[i++];
else
aux[k]=x[k++]
}
}
for(;i<=u1;k++)
aux[k]=x[i++];
for(;j<=u2;k++)
aux[k]=x[j++];
l1=u2+1;
for(i=l1;k<n;i++)
aux[k++]=x[i];
for(i=0;i<n;i++)
x[i]=aux[i];
size*=2;
}
}
[25] [57] [48] [37] [12] [92] [86] [33]
[25 57] [37 48] [12 92] [33 86]
[25 37 48 57] [12 33 86 92]
[12 25 33 37 48 57 86 92]
Radix
sort
for(k=least
significant digit;k<=most significant digit;k++)
{
for(i=0;i<n;i++)
{
y=x[i];
j=kth
digit of y
place
y at rear of queue[j]
}
}
for(qu=0;qu<10;qu++)
{
place
elements of queue[qu] in the next sequential position of x;
}
#define
NUMELTS ...
void
radixsort(int x[],int n)
{
int
front[10],rear[10];
struct
{
int
info;
int
next;
}
node[NUMELTS];
int
exp,first,i,j,k,p,q,y;
for(i=0;i<n-1;i++)
{
node[i].info=x[i];
node[i].next=i+1;
}
node[n-1].info=x[n-1];
node[n-1].next=-1;
first=0;
for(k=1;k<5;k++)
{
for(i=0;i<10;i++)
{
rear[i]=-1;
front[i]=-1
}
while(first!=-1)
{
p=first;
first=node[first].next;
y=node[p].info;
exp=(power(10,k-1);
j=(y/exp)%10
q=rear[j];
if(q==-1)
{
front[j]=p
else
{
node[q].next=p;
}
for(j=0;j<10&&front[j]==-1;j++)
;
first=front[j];
}
for(j=0;j<10&&front[j]==-1;j++)
;
first=front[j];
while(j<=9)
{
for(i=j+1;i<10&&front[i]==-1;i++)
;
if(i<=9)
{
p=i;
node[rear[j]].next=front[j];
}
j=i;
}
node[rear[p]].next=-1;
}
for(i=0;i<n;i++)
{
x[i]=node[first].info;
first=node[first].next
}
}
for(j=0;j<10&&front[j]==-1;j++)
;
first=front[j];
}
for(j=0;j<10&&front[j]==-1;j++)
;
first=front[j];
while(j<=9)
{
for(i=j+1;i<10&&front[i]==-1;i++)
;
if(i<=9)
{
p=i;
node[rear[j]].next=front[j];
}
j=i;
}
node[rear[p]].next=-1;
}
for(i=0;i<n;i++)
{
x[i]=node[first].info;
first=node[first].next
}
}
沒有留言:
張貼留言