Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Đỗ Ngọc Như Loan

ư

ỗ

ọ GV: Đ  Ng c Nh  Loan

ả

ậ i thu t tìm

ị Đ nh nghĩa gi ki mế



ộ ố ượ ng (a1, a2, ...., an) và

ộ ố ượ Input: m t dãy n đ i t m t đ i t ng k

 Output: là m t giá tr  logic true n u có k trong

ế ộ

ế ặ ị dãy ho c false n u ng ượ ạ i c l

 Dùng m ng ho c DSLK đ  bi u di n dãy đ i  ố

ể ể ễ ả ặ

ngượ t

 Ph n này dùng m ng m t chi u (các đ i  ố

ề ả ộ

ầ ố ượ ng là s ) t

ộ

ị ầ ủ ứ ầ ử ầ ử ố ủ ướ c v  trí c a ph n t ệ

ặ ế ư

ạ file TIMKIEM.INP có d ng:

Bài toán Yêu  c u:ầ  Cho  dãy  s   nguyên  a  ch a  các  s   đôi  ố ị m t khác nhau. Quy   đ u tiên  ị ấ là  0.  Tìm  v   trí  xu t  hi n  c a  ph n  t   có  giá  tr   k  ầ ử trong  dãy  a  ho c  đ a  ra  ­1  n u  không  có  ph n  t   ằ nào b ng k.  ừ ữ ệ D  li u vào t ầ ứ

ố ­ Dòng đ u là s  nguyên n và k ồ ­ Dòng th  hai g m n s

ủ ế ạ ị

ố ả K t  qu   ra  file  TIMKIEM.OUT  có  d ng:  v   trí  c a  k  trong dãy s .ố Ví d :ụ TIMKIEM.INP 6 8 9 2 8 3 1 4

TIMKIEM.OUT

2

ầ ự

ưở

ế Tìm ki m tu n t (Linear search) Ý t

ng:

ị  đ u m ng, k t h p so sánh giá tr

ả ớ

ị

ế ợ ể  c a m ng v i k đ  xác đ nh có hay

ầ ự ừ ầ  t ả ầ ử ủ ầ ử

ệ Duy t tu n t các ph n t không ph n t

k

k = 8

9 2 8 3 1 4

i = 0

9 2 8 3 1 4

i = 1

9 2 8 3 1 4

i = 2

Đã tìm  cượ đ

Output

2

bool Search(int A[MAX], int n, int k)

ả ố //m ng có n s  nguyên

{

for (int i=0; i

if(A[i] == k)

return true;

return false;

}

ấ ấ ố ấ

Ộ Ứ Ạ Đ  PH C T P  T t nh t: T(n) = O(1)  X u nh t: T(n) = O(n)  Trung bình: T(n) = O(n)

ứ ố

ộ ủ ầ ị

ấ ư ặ

ị ầ ử

Bài toán Yêu  c u:ầ  Cho  dãy  s   nguyên  a  ch a  các  s   đôi  ố ị ướ ế ắ c v  trí  m t khác nhau đã s p x p tăng d n. Quy  ủ ệ ầ ử ầ  đ u tiên là 0. Tìm v  trí xu t hi n c a  c a ph n t ế ầ ử ph n t  có giá tr  k trong dãy a ho c đ a ra ­1 n u  không có ph n t

ằ  nào b ng k.

ữ ệ ừ ạ D  li u vào t file TIMKIEM.INP có d ng:

ầ ố ­ Dòng đ u là s  nguyên n và k

ứ ồ ố ­ Dòng th  hai g m n s

ế ủ ạ ị

ả K t qu  ra file TIMKIEM.OUT có d ng: v  trí c a k  trong dãy s .ố

Ví d :ụ

TIMKIEM.INP

6 8

1 2 3 4 8 9

TIMKIEM.OUT

4

ộ ố ắ

ầ ử ầ

ặ

ị ầ ử ủ ế

Bài toán Yêu  c u:ầ  Cho  dãy  s   nguyên  a  ch a  các  s   đôi  ứ ố ầ . Quy  ị ướ ế c v   m t khác nhau  đã s p x p tăng d n ệ ấ ị ủ   đ u  tiên  là  0.  Tìm  v   trí  xu t  hi n  trí  c a  ph n  t ư ầ ử c a ph n t  có giá tr  k trong dãy a ho c đ a ra ­1  n u không có ph n t

ằ  nào b ng k.

ữ ệ ừ ạ D  li u vào t file TIMKIEM.INP có d ng:

ầ ố ­ Dòng đ u là s  nguyên n và k

ứ ồ ố ­ Dòng th  hai g m n s

ế ủ ạ ị

ả K t qu  ra file TIMKIEM.OUT có d ng: v  trí c a k  trong dãy s .ố

Ví d :ụ

TIMKIEM.INP

6 8

1 2 3 4 8 9

TIMKIEM.OUT

4

ị

ế Tìm ki m nh  phân (binary search)

ụ ườ ợ ượ ế ắ Áp d ng trong tr ng h p dãy đã đ c s p x p

ưở ạ ữ ể ế ả Tìm k t ủ i đi m gi a c a m ng, n u Ý t ng:

ư ả ấ ặ ch a tìm th y thì thì tìm bên trái ho c bên ph i

ữ ủ ể ả ớ ị (nh  phân) c a m ng (so v i đi m gi a)

k = 8

1 2 3 4 8 9

left = 0, right = 5, mid = 2

1 2 3 4 8 9

left = 3, right = 5, mid = 4

Đã tìm  cượ đ

Output

4

k = 3

1 2 3 4 7 9 10 12

left = 0, right = 7, mid = 3

1 2 3 4 7 9 10 12

left = 0, right = 2, mid = 1

1 2 3 4 7 9 10 12

left = 2, right = 2, mid = 2

Output

Đã tìm  cượ đ

2

Begin

ậ

ố Nh p dãy s ,  k

left = 0, right = n – 1

left<=right

NO

YES

mid = (left + right)/2

ấ Xu t ra  ­1

YES

NO

a[mid]= k

NO

YES

a[mid]> k

ấ Xu t ra  mid

left = mid+1

right = mid­1

End

bool BinarySearch(int A[MAX], int n, int k) {

int i=0, j=n­1, m; while(i<=j) {

m=(i+j)/2; if(k==A[m]) return true; else if(k>A[m]) i=m+1; else j=m­1;

} return false;

}

Ộ Ứ Ạ Đ  PH C T P

 T t nh t: T(n) = O(1)

ấ ố

 X u nh t: T(n) = O(log2n)

 Trung bình: T(n) = O(log2n)

ấ ấ

Ả

Ắ

Ậ I THU T S P

Ị Đ NH NGHĨA GI X PẾ

ả

ế

Các gi

ậ ắ i thu t s p x p



 Quick Sort, Heap Sort, Merge Sort

 Counting Sort, Bucket Sort

Insertion Sort, Selection Sort, Bubble Sort

Bài Toán

ầ ử

ồ

ắ

. Hãy s p

ầ

ố Yêu c u: ầ Cho dãy s  nguyên g m n ph n t ứ ự ố ế x p dãy s  theo th  t

tăng d n.

ữ ệ

ừ

ồ

D  li u vào t

file SAPXEP.INP g m 2 dòng:

ố

ươ

ứ + Dòng 1 ch a s  nguyên d

ng n (n < 1000)

ữ ố

ứ

ồ

ố + Dòng 2 ch a dãy s  nguyên g m n ch  s

ả

ế

ứ

ồ

ấ ượ

ế

ắ

ầ

K t  qu   xu t  ra  file  SAPXEP.OUT,  g m  1  dòng  ch a  ố dãy s  đã đ

c s p x p tăng d n.

Ví d :ụ

SAPXEP.INP

5

3 5 2 1 7

SAPXEP.OUT

1 2 3 5 7

ự

ọ

ế

Ch n tr c ti p (selection sort)

ọ ấ

 Ch n ph n t ỏ ầ ử ầ ử ầ v  cho ph n t

ị nh  nh t trong A[i…n] và hoán   đ u tiên A[i]

 B t đ u v i i=1 và l p l ớ

ắ ầ ặ ạ ế i cho đ n khi i=n­1

i = 1

k = 4

3 5 2 1 7

i = 2

k = 3

1 5 2 3 7

k = 4

1 2 5 3 7

i = 3

i = 4

k = 4

1 2 3 5 7

1 2 3 5 7

void SelectionSort(int A[], int n) {

for(int i=0;i

int min=i; for(int j=i+1; j

min=j;

Swap(A[i], A[min]);

}

}

void SelectionSort(int A[], int n) {

for(int i=0;i

int min=i; for(int j=i+1; j

min=j;

Swap(A[i], A[min]);

}

}

Ộ Ứ Ạ

Đ  PH C T P: O(n2)

ự

ế

Chèn tr c ti p (insertion sort)

 Chia m ng A[1..n] thành 2 ph n: Đ c s p và

ượ ắ ầ

ả ượ ư ch a đ ắ c s p

 Kh i đ u m ng A[1..i] v i i = 1 đ

 M i b ỗ ướ ấ ả

ở ầ ả ớ ượ ắ c s p

ầ ử ượ ư A[j] (j=i+1,…) trong  c s p tìm và chèn vào

ợ

ị

V  trí nào là thích h p?

ị c l y ph n t ắ m ng A[j..n] ch a đ ợ v  trí thích h p trong A[1..i]

i = 0

j = 2

3 2 7 4 5

i = 2

j = 3

2 3 7 4 5

i = 2

j = 4

2 3 7 4 5

i = 3

j = 5

2 3 4 7 5

2 3 4 5 7

6 2 5 10 8 9 1 3

j = 2 i = 0

2 6 5 10 8 9 1 3

j = 3 i = 1

2 5 6 10 8 9 1 3

j = 4 i = 3

2 5 6 10 8 9 1 3

j = 5 i = 3

2 5 6 8 10 9 1 3

j = 6 i = 4

2 5 6 8 9 10 1 3

j = 7 i = 0

1 2 5 6 8 9 10 3

j = 8 i = 2

1 2 3 5 6 8 9 10

void InsertionSort(int A[], int n) {

for(int j=1;j

int key=A[j]; int i=j­1; while(i>=0 && A[i]>key) {

A[i+1]=A[i]; i=i­1;

} A[i+1]=key;

}

}

ứ ạ

ộ

Đ  ph c t p

ườ ợ ố Tr ng h p t ấ t nh t:

Khi A[i] <= A[i+1], i = 1,.., n­1

 Khi i kh i đ u là j ­1 thì A[i] <= key v i m i i < j,

ớ ọ

 T(n) = c1n + c2( n­1)+ c4( n­1)+ c5( n­1) + c8( n­

ở ầ ớ ọ nên tj =1 v i m i j =2, 3,..., n

1) = (c1+ c2+ c4+ c5+ c8)n ­ (c2+ c4+ c5 +  c8)=O(n)

ứ ạ

ộ

Đ  ph c t p

ườ ợ Tr ấ   ấ ng h p x u nh t:

Khi A[i]> A[i+1], i = 1,.., n­1

 Khi i kh i đ u là j ­1 thì A[i] > key v i m i i < j,

ớ ọ

 T(n) = c1n + c2( n­1)+ c4( n­1)+c5((n(n+1)/2­1) +

ở ầ ớ ọ nên tj =j v i m i j =2, 3,..., n

c6((n(n­1)/2) + c7((n(n­1)/2) + c8( n­1) =  (c5+c6+c7)n2/2 + (c1+c2+c4 +c5/2 ­ c6/2  ­c7/2+c8)n ­(c2 + c4 + c5+c8)=O(n2)

ứ ạ

ộ

Đ  ph c t p

ườ ợ Tr ng h p trung bình:

ộ ị ấ ớ

ể Có m t v  trí i =1,…, j­1 đ  chèn A[j] v i xác su t  1/j

ở ầ ố ầ

 Khi i kh i đ u là j ­1 thì s  l n so sánh trung bình  ớ ệ x y ra quan h  A[i] > key là j/2, nên tj =j/2 v i  m i j =2, 3,..., n

 T(n) = c1n + c2( n­1)+ c4( n­1)+c5((n(n+1)/2­1)/2

ả ọ

+ c6((n(n­1)/2)/2 + c7((n(n­1)/2)/2 + c8( n­1)  =(c5+c6+c7)n2/4 + (c1+c2+c4 +c5/4 ­ c6/4  ­c7/4+c8)n ­ (c2 + c4 + c5/2 +c8)=O(n2)

ứ ạ

ộ

Đ  ph c t p

 T t nh t T(n)= O(n)

 Trung bình T(n)= O(n2)

ấ ố

 X u nh t T(n)= O(n2)

ấ ấ

ổ ọ

N i b t (bubble sort)

 Duy t t ế

ệ ừ ả

ầ ử n u A[j]>A[j+1] thì hoán v  hai ph n t trái sang ph i trong dãy A[1..i­1],  ị  này

 Quá trình b t đ u v i i=n, gi m cho đ n khi  ớ

ắ ầ ế ả

i=2

 K t qu  m i b

ả ỗ ướ ặ ấ ẽ ớ c l p là A[i] s  l n nh t trong

ế A[1..i]

j = 1

i = 4

5 7 4 1

j = 2

i = 4

5 7 4 1

j = 3

i = 4

5 4 7 1

5 4 1 7

j = 1

i = 3

5 4 1 7

j = 2

i = 3

4 5 1 7

4 1 5 7

j = 1

i = 2

4 1 5 7

1 4 5 7

void BubbleSort(int A[], unsigned n)

{

for(int i=n­1;i>=1;i­­)

{

for(int j=0; j<=i­1; j++)

if(A[j]>A[j+1])

Swap(A[j], A[j+1]);

}

}

void BubbleSort(int A[], unsigned n)

{

for(int i=n­1;i>=1;i­­)

{

for(int j=0; j<=i­1; j++)

If(A[j]>A[j+1])

Swap(A[j], A[j+1]);

}

Ộ Ứ Ạ

Đ  PH C T P: O(n2)

}

BÀI T PẬ

ố ộ

ủ c v  trí c a ph n t ầ ử ướ ệ ấ ị

ố ị ủ ế ầ ử ư ằ ặ

ứ Yêu c u:ầ  Cho dãy s  nguyên ch a các s  đôi m t  ầ ử ầ  đ u tiên là 0.  khác nhau. Quy  ị   có  giá  tr   X  trong  Tìm  v   trí  xu t  hi n  c a  ph n  t dãy ho c đ a ra ­1 n u không có ph n t  nào b ng  X.

ữ ệ ừ ạ D  li u vào t file TIMKIEM1.INP có d ng:

ầ ố ­ Dòng đ u là s  nguyên N và X

ứ ố ồ ­ Dòng th  hai g m N s  nguyên

ế ủ ạ ị

ả K t qu  ra file TIMKIEM1.OUT có d ng: v  trí c a X  trong dãy s .ố

Ví d :ụ

TIMKIEM1.INP

6 8

9 2 8 3 1 4

TIMKIEM1.OUT

2

ố ứ

ượ ế ắ c s p x p tăng d n

ấ

ố ầ . Quy  ị ặ ư

ộ Yêu c u:ầ  Cho dãy s  nguyên ch a các s  đôi m t  c ướ khác nhau đã đ ệ ầ ử ầ ủ ị  đ u tiên là 0. Tìm v  trí xu t hi n  v  trí c a ph n t ủ ầ ử c a ph n t  có giá tr  X trong dãy ho c đ a ra ­1  ế n u không có ph n t ị ằ ầ ử  nào b ng X.

ữ ệ ừ ạ D  li u vào t file TIMKIEM2.INP có d ng:

ầ ố ­ Dòng đ u là s  nguyên N và X

ứ ố ồ ­ Dòng th  hai g m N s  nguyên

ế ủ ạ ị

ả K t qu  ra file TIMKIEM2.OUT có d ng: v  trí c a  X trong dãy s .ố

Ví d :ụ

TIMKIEM2.INP

6 8

1 2 3 4 8 9

TIMKIEM2.OUT

4

ầ ử ồ . Hãy

ứ ự ế ầ ố Yêu c u:ầ  Cho dãy s  nguyên g m n ph n t ố ắ s p x p dãy s  theo th  t tăng d n.

ữ ệ ừ ồ D  li u vào t file SAPXEP1A.INP g m 2 dòng:

ố ươ ứ + Dòng 1 ch a s  nguyên d ng n (n < 1000)

ữ ố ứ ồ ố + Dòng 2 ch a dãy s  nguyên g m n ch  s

ả ồ

ả

ằ

ậ

ế

ắ

ượ ế ứ ấ ố ế ắ ầ K t  qu   xu t  ra  file  SAPXEP1A.OUT,  g m  1  dòng  ch a dãy s  đã đ c s p x p tăng d n.

Gi i bài toán này b ng 3 thu t  toán  s p  x p:  Insertion  Sort,  Selection Sort và Bubble Sort

Ví d :ụ

SAPXEP1A.INP

5

3 5 2 1 7

SAPXEP1A.OUT

1 2 3 5 7

ệ ậ

Luy n t p

ế ướ ế ụ ậ t các b c s p x p n u áp d ng thu t toán

ế ố ắ Vi Selection Sort cho dãy s  sau:

4   9   2   3   7   5

Ví d :ụ

←

1 to n ­ 1

←

↔

for j   j←          smallest           for i   j + 1 to n                   if A[ i ] < A[ smallest ]                           smallest           Swap A[ j ]

i←  A[ smallest ]

ế

ậ

ắ Thu t toán s p x p nào?

n ­ 1 to 2 ←

1 to i ­ 1

← for i           for j                    if A[ j ] > A[ j + 1 ] ↔                          Swap A[ j ]

A[j + 1]

ế

ậ

ắ Thu t toán s p x p nào?

2 to n  ←

← for j           key

A[ j ]

j ­ 1←

i           while i > 0 and A[ i ] > key

←

A[ i + 1 ]

A[ i ]

←

i

A[ i + 1 ]  ậ

ế

i ­ 1            key← ắ Thu t toán s p x p nào?

ế

ắ

S p x p nhanh (quicksort)

 Đ c thi ượ

ế ế ự ậ ỹ ể ị t k  d a trên k  thu t chia đ  tr

(divide and conquer):

 Divide: Phân ho ch A[p..r] thành hai m ng

ạ

ỏ ơ ằ ả ầ ử   ớ ặ ng  ng nh  h n ho c b ng A[q] và l n

con A[p..q­1] và A[q+1..r] có các ph n t ươ ứ t ơ h n A[q]

ắ ả

 Conquer: S p x p hai m ng con A[p..q­1] và  ế ờ ọ ệ i g i đ  qui

ằ A[q+1..r] b ng l

Ch tố 3 5 2 1 7

1 5 2 3 7

i

i j 3 5 2 1 7

j 1 5 2 3 7

j

i

j

i 3 5 2 1 7

1 2 5 3 7

j

i

i

1 5 2 3 7

j 1 2 5 3 7

j

i

j

i

Bên trái

Bên ph iả 5 3 7

1

2

j

i

j i 5 3 7

21

j

i

j

i

3 5 7

j i 3 5 7

i

j

5

7

3

5

7

1

2

3 5 7

1 2 3 5 7

void QuickSort(int A[], int left, int right) {

int i = left, j = right; int x = A[(left + right)/2]; while  (i<=j) {

while (A[i]x) j­­; if(i<=j) {

Swap(A[i],A[j]); i++; j­­;

}

} if (left < j)

QuickSort(A, left,j);

if (I < right)

QuickSort(A, i,right);

}

ứ ạ

ộ

Đ  ph c t p

Partition có T(n)=O(n)

 T t nh t T(n)= O(nlog2n)

 Trung bình T(n)= O(nlog2n)

ấ ố

 X u nh t T(n)= O(n2)

ấ ấ

ộ

ế

ắ

S p x p tr n (Mergesort)

ủ ụ ọ ệ

ộ // Th  t c tr n g i đ  quy void MergeSort(int X[], int L, int R) {    int M;    if (L

ắ

ạ

ế

k=k+1;    }   if (i>=k2)         for(t=j;t<=k3;t++)          temp[k+t­j]=a[t];    else       for(t=i;t<=k2;t++)          temp[k+t­i]=a[t];        for(k=k1;k<=k3;k++)          a[k]=temp[k]; }

ủ ụ ộ // Th  t c tr n hai đo n đã s p x p  ộ trong m t dãy void Merge(int a[], int k1, int k2, int k3) {    int i,j,k,t;    int temp[40000];      i=k1; j=k2; k=k1;    while ((i

Ộ Ứ Ạ Đ  PH C T P:  O(nlog2n)

ế

ắ

ố S p x p vun đ ng (Heapsort)

ể ễ ả ộ ộ

ấ ộ ị Cho m t m ng A, m t Heap bi u di n A là m t  cây nh  phân có các tính ch t sau:

 Cây có th  t

ứ ự ỗ ng  ng v i m t

, m i nút t ả ứ ớ ươ ố ứ  c a m ng, g c  ng v i ph n t ộ ớ ầ ử ầ  đ u

 Cây cân b ng và đ ằ ạ ừ ứ

ầ ử ủ ph n t ả ủ tiên c a m ng

ấ ả t c  các  ầ c l p đ y  ầ ầ ượ ấ c l p đ y trên t ấ ượ ấ ứ ấ ể  bên trái sang (có th  ch a l p đ y) m c, ngo i tr  m c th p nh t đ ư ấ ừ t

ụ ớ

ố

Ví d  v i dãy s :

5, 25, 15, 8, 7, 28

ự

ư

ể

Ta có th  xây d ng heap nh  sau:

heapsort

ụ

Ví d  MaxHeap:

1       2       3       4       5       6       7       8

heapsort

ả ậ ế ả ổ ề i thu t HeapSort bi n đ i m ng v

ể ắ ư ế Gi MaxHeap đ  s p x p nh  sau:

 Bi n đ i Heap (m ng) v  m t MaxHeap ả

ề ộ ế ổ

 Hoán đ i giá tr  A[1] v i A[n]

ớ ổ ị

ạ ỏ

 Lo i nút n ra kh i Heap và chuy n Heap A[1.. (n­1)] thành m t MaxHeap (ít h n m t ph n  t )ử

ể ơ ầ ộ ộ

 L p l

ặ ạ ế ỉ c trên cho đ n khi Heap ch

ướ i các b ầ ử ộ còn m t ph n t

Ví dụ

Xem video

https://www.youtube.com/watch?v=­A3AFoS_NDI

heapsort

ủ ụ ầ ả ỗ ợ ậ C n hai th  t c (gi i thu t) h  tr  cho HeapSort:

 MaxHeapify(A[1..n], i), bi n đ i cây con có g c

ế ố

ộ ổ ố ạ i i thành m t MaxHeap (g c t i i) ạ t

 BuildMaxHeap(A[1..n]), bi n đ i m ng (Heap)

ế ả ổ

thành MaxHeap

HeapSort(A[1..n], int n)

BuildMaxHeap(A, n)

for i n ← downto 2 do

Exchange(A[1], A[i])

MaxHeapify(A, 1)

MaxHeapify

 Đ u vào là m t m ng (heap) A và ch  s  i

ỉ ố ầ ả ộ

trong m ngả

 Các cây nh  phân đ

ị ị c đ nh g c t ố ạ i

ỏ ơ ư ể

ủ ượ LEFT_CHILD(i) và RIGHT_CHILD(i) là các  MaxHeap nh ng A[i] có th  nh  h n các con  c a nó

 MaxHeapify đ y giá tr  A[i] xu ng sao cho cây  ị

ố

ị ẩ ố ạ con đ nh g c t ộ i A[i] là m t MaxHeap

MaxHeapify

buildmaxheap

buildmaxheap

BuildMaxHeap(A[1..n])

← n/2 for i downto 1

do MaxHeapify(A, i)

ứ ạ

ộ

Đ  ph c t p

ầ ử .  Hãy

ứ ự ồ ầ ế ố Yêu  c u:ầ  Cho  dãy  s   nguyên  g m  n  ph n  t ố ắ s p x p dãy s  theo th  t tăng d n.

ữ ệ ừ ồ D  li u vào t file SAPXEP2A.INP g m 2 dòng:

ố ươ ứ + Dòng 1 ch a s  nguyên d ng n (n < 40000)

ữ ố ứ ồ ố + Dòng 2 ch a dãy s  nguyên g m n ch  s

ồ

ả

ằ

ế

ắ

i  bài  toán  này  b ng  2  thu t

ế ứ ấ ố ượ ắ ầ ả K t  qu   xu t  ra  file  SAPXEP2A.OUT,  g m  1  dòng  ế ch a dãy s  đã đ c s p x p tăng d n.

ậ Gi toán  s p  x p:  Quick  Sort,  Merge Sort và Heap Sort

Ví d :ụ

SAPXEP2A.INP

5

3 5 2 1 7

SAPXEP2A.OUT

1 2 3 5 7

ố

ộ

ồ n s  đôi  ươ

k (k < n).

ng

ố ố ỏ ứ

ị

Yêu c u:ầ  Cho dãy s  nguyên g m  m t khác nhau và s  nguyên d Hãy tìm giá tr  nh  th  k trong dãy.

ừ

ồ

file GIATRI.INP g m 2

ữ ệ Input: D  li u vào t dòng:

ồ

ố

ươ

ng

n và k

+ Dòng 1: G m 2 s  nguyên d (n<=1000)

ứ

ố

+ Dòng 2 ch a dãy s  nguyên

n ph n tầ ử

ấ

ồ

ứ

Output: Xu t ra file GIATRI.OUT , g m 1 dòng  ố ủ ỏ ứ k c a dãy s ị ch a giá tr  nh  th

Ví d :ụ

GIATRI.INP

5 3

5 7 1 3 4

GIATRI.OUT

4

ố ố ượ

ầ ử ồ n ph n t   ng giá tr  khác nhau

Yêu c u:ầ  Cho dãy s  nguyên g m  ị ế (n<2000). Hãy đ m s  l trong dãy

Ví d :ụ

DEMSO1.INP

8

6 7 1 7 4 6 6 8

DEMSO1.OUT

5

Bài toán:

ố

ầ ử

ồ n ph n t

(n <= 1000000).

. Hãy

k trong dãy, 0 <= k < 100

ứ ự

ầ

Cho dãy s  nguyên g m  ọ ầ ử ớ V i m i ph n t ố ế ắ s p x p dãy s  theo th  t

tăng d n.

ằ

ắ

ế

ượ ườ

ế S p x p b ng đ m  (Counting SORT)  Thu t toán này đ ặ

c áp d ng trong tr ị ụ ấ ả ệ ng  t c  các giá tr  trong t, khi mà t

ợ ả ề ả ộ ố

ậ h p đ c bi m ng đ u là s  nguyên và thu c kho ng  [0..k] đã bi t.ế

 Ý t

ả ưở

ị ng: ả

ả ử

ả

ế ạ  đ u, ti p  ặ

ặ ầ ử ở ế  Xét trong kho ng [0..k], đ m xem  ả ử  s  là  trong m ng có bao nhiêu giá tr  0 (gi ị  s  là b), …, bao  a), bao nhiêu giá tr  1 (gi ả ử ị i   s  là z), sau đó x p l nhiêu giá tr  k (gi ế ầ ử ở ầ ặ ằ  0  m ng b ng cách đ t a ph n t ầ ử theo đ t b ph n t  1 ti p theo, …, và đ t z  ố  k  ph n t ế  cu i cùng.

3 5 2 1 7

0

1

2

3

4

5

6

7

8 ... 100

0

0

0

0

0

0

0

0

0 ...

0

0

1

2

3

4

5

6

7

8 ... 100

0

1

1

1

0

1

0

1

0 ...

0

1 2 3 5 7

2 5 2 1 5 3 2

0

1

2

3

4

5

6

7

8 ... 100

0

0

0

0

0

0

0

0

0 ...

0

0

1

2

3

4

5

6

7

8 ... 100

0

1

3

1

0

2

0

0

0 ...

0

1 2 2 2 3 5 5

 Dòng 1­2 kh i t o các C[i] = 0 ở ạ

 Dòng 3­4 xác đ nh s  ph n t

ầ ử ố ị ị có giá tr  là i =

A[j] trong A

 Dòng 6­7 xác đ nh s  ph n t

ố ị

ặ ằ ơ ỏ ầ ử  trong A nh   ủ ổ h n ho c b ng i, đó là t ng c a C[i] và C[i­1]

 Dòng 9­10 đ t A[j] vào trong v  trí đ

ị

ầ ử ỏ ơ ặ ằ ố ặ ả ủ  nh  h n ho c b ng A[j] trong

ắ ượ c s p  ứ chính xác c a nó trong m ng B căn c  vào  s  ph n t C[A[j]]

 Gi m C[A[j]] đi 1 trong dòng 10 đ  các ph n

ể

ạ ằ ẽ ượ ặ ầ c đ t chính xác

ả  còn l ả ử t i b ng A[j] s  đ ầ ặ vào m ng B l n l p sau

int c[k+1];  int b[n];

for (int i = 0; i <= k; i++)

ệ ấ ả

c[i] = 0; ủ ố ầ ế //đ m s  l n xu t hi n c a a[i] trong kho ng [0..k] for (i = 0; i < n; i++)

c[a[i]]++;  ị ố ủ ạ ỗ

//tính v  trí cu i c a m i đo n con for (i = 1; i <= k; i++)  c[i] += c[i­1];

for (int j = n­1; j >= 0; j­­) {

b[c[a[j]]] = a[j]; c[a[j]]­­;

}

int c[k+1];  int b[n]; int h = 0;

for (int i = 0; i <= k; i++)

c[i] = 0;

ế ệ ấ ả

ủ ố ầ //đ m s  l n xu t hi n c a a[i] trong kho ng [0..k] for (i = 0; i < n; i++)

c[a[i]]++;

for (i = 0; i <= k; i++)

for (j = 1; j <= c[i]; j++) {

b[h] = i; h++;

}

ứ ạ

ộ

Đ  ph c t p

 Chi phí cho l nh 1­2 là O(k) ệ

 Chi phí cho l nh 3­4 là O(n) ệ

 Chi phí cho 6­7 là O(k)

 Chi phí cho 9­11 là O(n)

 Vì v y t ng chi phí th i gian là O(k + n)

ậ ổ ờ

 N u k = O(n) thì t ng chi phí là O(n) ổ

ế

ế

ắ

S p x p theo lô (bucket sort)

 S p x p theo lô (Bucket sort) gi ố

s  input là

ỏ ơ ế ả ắ ộ ả ử m t m ng n s  không âm nh  h n 1

 Ý t

ưở ủ ng c a Bucketsort

ả

ủ ố ả ­ Phân b  m ng input vào n kho ng con (lô)  ả c a kho ng [0, 1)

ỗ ố

ắ ể ế ­ S p x p các ph n t ả lô đ  có m ng đ ầ ử  trong m i lô và n i các  ắ ượ c s p

ế

ắ

S p x p theo lô (bucket sort)

 Xét hai ph n t

ầ ử A[i] và A[j]

ờ ả ộ ế ự ậ ế ơ ­ N u A[i] và A[j] cùng r i vào m t lô, chúng có  ứ ự i thu t chèn tr c ti p th  t nh  gi

ọ ươ ứ ượ ạ c l

ủ ng  ng c a A[i] và  ượ c

ố ướ ­ Ng A[j] là B[i’ ] và B[j’ ], n u i’ < j’ thì lô B[i’ ] đ n i tr i, g i các lô t ế c lô B[j’ ] và khi đó A[i] <= A[j]

Ộ Ứ Ạ Đ  PH C T P

 Do phân b  ng u nhiên n ph n t ẫ

ố vào n

ả ầ ầ ử ỗ

ế ậ ờ kho ng con nên trung bình m i lô có 1 ph n  ử t ắ , vì v y th i gian s p x p chèn là O(1)

 T  đó, chi phí toàn b  c a gi

ộ ủ ừ ả ậ i thu t là O(n)

Sort(A,p,r)

if p < r then

←

q

Partition(A,p,r);

Sort(A, p,q­1);

Sort(A, q+1,r);

ế

ậ

ắ Thu t toán s p x p nào?

Sort(A,p,r)

if p < r then

←

q

(p + r)/2

Sort(A,p,q)

Sort(A,q+1,r)

Merge(A,p,q,r)

ế

ậ

ắ Thu t toán s p x p nào?

Sort(A[1..n])

BuildMaxHeap(A)

←

For i

n downto 2

do Swap(A[1], A[i])

MaxHeapify(A, 1)

ế

ậ

ắ Thu t toán s p x p nào?

ố

ố

ồ n s  đôi

ổ

(n<=1000). Hãy tìm t ng 3 giá

ộ ị

ỏ

Yêu c u:ầ  Cho dãy s  nguyên g m  m t khác nhau  ấ tr  nh  nh t trong dãy.

ừ

ồ

file GIATRI2.INP g m 2

ữ ệ Input: D  li u vào t dòng:

ố

n

ứ + Dòng 1: Ch a s  nguyên

ứ

ố

+ Dòng 2 ch a dãy s  nguyên

n ph n tầ ử

ấ

ồ

ứ ổ

ấ

ỏ

, g m 1 dòng  Output: Xu t ra file GIATRI2.OUT ố ị ch a t ng 3 giá tr  nh  nh t dãy s

Ví d :ụ

GIATRI2.INP

5

5 7 1 3 4

GIATRI2.OUT

8

ố

ố ầ ặ

ệ

ấ

ấ

ị

ồ n (n < 106)  Yêu c u:ầ  Cho dãy s  nguyên g m  ố s  nguyên k (0 < k < 1000). Hãy tính s  l n l p  ề ủ c a giá tr  xu t hi n nhi u nh t.

Ví d :ụ

DEMSO3.INP

8

6 7 1 7 4 6 6 8

DEMSO3.OUT

3

ố ố ầ ặ

ồ ủ

ệ

ấ

ử Yêu  c u:ầ  Cho  dãy  s   nguyên  g m  ầ n  ph n  t   ấ ị (n<10000).  Hãy  tính  s   l n  l p  c a  giá  tr   xu t  ề hi n nhi u nh t.

Ví d :ụ

DEMSO2.INP

8

6 7 1 7 4 6 6 8

DEMSO2.OUT

3