Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Các giải thuật Tìm kiếm & sắp xếp - Đỗ Ngọc Như Loan

Các giải thuật 
Tìm kiếm & Sắp xếp 
GV: Đỗ Ngọc Như Loan 
Định nghĩa giải thuật tìm kiếm 
Input : một dãy n đối tượng (a 1 , a 2 , ...., a n ) và 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ược lại 
Dùng mảng hoặc DSLK để biểu diễn dãy đối tượng 
Phần này dùng mảng một chiều (các đối tượng là số) 
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 ước vị trí của phần tử đầ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ừ 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 
9 2 8 3 1 4 
TIMKIEM.OUT 
2 
Tìm kiếm tuần tự (Linear search) 
Ý tưởng: 
Duyệt tuần tự từ đầu mảng, kết hợp so sánh giá trị các phần tử của mảng với k để xác định có hay không phần tử k 
9 
2 
8 
3 
1 
4 
k = 8 
i = 0 
9 
2 
8 
3 
1 
4 
i = 1 
9 
2 
8 
3 
1 
4 
i = 2 
2 
Output 
Đã tìm được 
bool Search(int A[MAX], int n, int k) 
// mảng có n số nguyên 
{ 
	for (int i=0; i<n; 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 một khác nhau đã sắp xếp tăng dần. Quy ước vị trí của phần tử đầ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ừ 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 một khác nhau đã sắp xếp tăng dần . Quy ước vị trí của phần tử đầ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ừ 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ưởng: Tìm k tại điểm giữa của mảng, nếu 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 ) 
1 
2 
3 
4 
8 
9 
k = 8 
left = 0, right = 5, mid = 2 
1 
2 
3 
4 
8 
9 
4 
Output 
left = 3, right = 5, mid = 4 
Đã tìm được 
1 
2 
3 
4 
7 
9 
10 
12 
k = 3 
left = 0, right = 2, mid = 1 
2 
Output 
1 
2 
3 
4 
7 
9 
10 
12 
left = 0, right = 7, mid = 3 
1 
2 
3 
4 
7 
9 
10 
12 
left = 2, right = 2, mid = 2 
Đã tìm được 
Begin 
End 
mid = (left + right)/2 
Nhập dãy số, k 
a[mid]= k 
Xuất ra mid 
NO 
YES 
a[mid]> k 
right = mid-1 
left = 0, right = n – 1 
YES 
NO 
left = mid+1 
left<=right 
NO 
YES 
Xuất ra -1 
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(log 2 n) 
Trung bình: T(n) = O(log 2 n) 
ĐỊNH NGHĨA GIẢI THUẬT SẮP XẾP 
Input : một dãy n số (a1, a2, ...., an) 
Output : một hoán vị của input ( a’ 1 , a’ 2 , ...., a’ n ) sao cho 
a’ 1 a’ 2 .... a’ n 
Dùng mảng hoặc DSLK để biểu diễn dãy số 
Phần này dùng mảng 
Các giải thuật sắp xếp 
Insertion Sort, Selection Sort, Bubble Sort 
Quick Sort, Heap Sort, Merge Sort 
Counting Sort, Bucket Sort 
Bài Toán 
Yêu cầu: Cho dãy số nguyên gồm n phần tử. Hãy sắp 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ử nhỏ nhất trong A[in] và hoán vị cho phần tử đầu tiên A[i] 
Bắt đầu với i=1 và lặp lại cho đến khi i=n-1 
3 
5 
2 
1 
7 
1 
5 
2 
3 
7 
1 
2 
5 
3 
7 
1 
2 
3 
5 
7 
1 
2 
3 
5 
7 
i = 2 
i = 1 
i = 4 
i = 3 
k = 4 
k = 3 
k = 4 
k = 4 
void SelectionSort(int A[], int n) 
{ 
	for(int i=0;i<n-1;i++) 
	{ 
	int min=i ; 
	for(int j=i+1; j<n;j++) 
	if(A[j ]< A[min]) 
	 	min=j ; 
	Swap(A[i ], A[min]); 
	}	 
} 
void SelectionSort(int A[], int n) 
{ 
	for(int i=0;i<n-1;i++) 
	{ 
	int min=i ; 
	for(int j=i+1; j<n;j++) 
	if(A[j ]< A[min]) 
	 	min=j ; 
	Swap(A[i ], A[min]); 
	}	 
} 
ĐỘ PHỨC TẠP: O(n 2 ) 
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 được sắp 
Mỗi bước lấy phần tử A[j] (j=i+1,) trong mảng A[j.. n] chưa được sắp tìm và chèn vào vị trí thích hợp trong A[1 ..i ] 
Vị trí nào là thích hợp? 
3 
2 
7 
4 
5 
2 
3 
7 
4 
5 
2 
3 
7 
4 
5 
2 
3 
4 
7 
5 
2 
3 
4 
5 
7 
j = 3 
j = 2 
j = 5 
j = 4 
i = 2 
i = 0 
i = 3 
i = 2 
2 
6 
5 
10 
8 
9 
1 
3 
6 
2 
5 
10 
8 
9 
1 
3 
2 
5 
6 
10 
8 
9 
1 
3 
2 
5 
6 
10 
8 
9 
1 
3 
2 
5 
6 
8 
10 
9 
1 
3 
j = 3 
i = 1 
j = 2 
i = 0 
j = 5 
i = 3 
j = 4 
i = 3 
j = 6 
i = 4 
1 
2 
5 
6 
8 
9 
10 
3 
2 
5 
6 
8 
9 
10 
1 
3 
1 
2 
3 
5 
6 
8 
9 
10 
j = 7 
i = 0 
j = 8 
i = 2 
void InsertionSort(int A[], int n) 
{ 
	for(int j=1;j<n;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 , nên t j =1 với mọi j =2, 3,..., n 
T(n ) = c 1 n + c 2 ( n-1)+ c 4 ( n-1)+ c 5 ( n-1) + c 8 ( n-1 ) = (c 1 + c 2 + c 4 + c 5 + c 8 )n - (c 2 + c 4 + c 5 + c 8 )=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 , nên t j =j với mọi j =2, 3,..., n 
T(n ) = c 1 n + c 2 ( n-1)+ c 4 ( n-1)+c 5 ((n(n+1)/2-1) + 
c 6 ((n(n-1)/2) + c 7 ((n(n-1)/2) + c 8 ( n-1 ) = ( c 5 +c 6 +c 7 )n 2 /2 + (c 1 +c 2 +c 4 +c 5 /2 - c 6 /2 -c 7 /2+c 8 )n -( c 2 + c 4 + c 5 +c 8 )=O(n 2 ) 
Độ 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 t j =j/2 với mọi j =2, 3,..., n 
T(n ) = c 1 n + c 2 ( n-1)+ c 4 ( n-1)+c 5 ((n(n+1)/2-1)/2 + c 6 ((n(n-1)/2)/2 + c 7 ((n(n-1)/2)/2 + c 8 ( n-1 ) =( c 5 +c 6 +c 7 )n 2 /4 + (c 1 +c 2 +c 4 +c 5 /4 - c 6 /4 - c 7 /4+c 8 )n - ( c 2 + c 4 + c 5 /2 +c 8 )=O(n 2 ) 
Độ phức tạp 
Tốt nhất T(n)= O(n) 
Trung bình T(n)= O(n 2 ) 
Xấu nhất T(n )= O(n 2 ) 
Nổi bọt (bubble sort) 
Duyệt từ trái sang phải trong dãy A[1..i-1], nếu A[j ]>A[j+1] thì hoán vị hai phần tử 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] 
5 
7 
4 
1 
5 
7 
4 
1 
5 
4 
7 
1 
5 
4 
1 
7 
i = 4 
i = 4 
i = 4 
j = 2 
j = 1 
j = 3 
5 
4 
1 
7 
4 
5 
1 
7 
4 
1 
5 
7 
i = 3 
i = 3 
j = 2 
j = 1 
4 
1 
5 
7 
1 
4 
5 
7 
i = 2 
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]); 
	} 
} 
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(n 2 ) 
Yêu cầu: Cho dãy số nguyên chứa các số đôi một khác nhau. Quy ước vị trí của phần tử đầu tiên là 0. Tìm vị trí xuất hiện 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 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 
BÀI TẬP 
Yêu cầu: Cho dãy số nguyên chứa các số đôi một khác nhau đã được sắp xếp tăng dần . Quy ước vị trí của phần tử đầu tiên là 0. Tìm vị trí xuất hiện 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 
Yêu cầu: Cho dãy số nguyên gồm n phần tử. Hãy 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. 
Ví dụ: 
SAPXEP1A.INP 
5 
3 5 2 1 7 
SAPXEP1A.OUT 
1 2 3 5 7 
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 
Luyện tập 
Viết các bước sắp xếp nếu áp dụng thuật toán Selection Sort cho dãy số sau: 
 4 9 2 3 7 5 
Ví dụ: 
for j ← 1 to n - 1         smallest ← j         for i ← j + 1 to n                  if A[ i ] < A[ smallest ]                          smallest ← i         Swap A[ j ] ↔ A[ smallest ] 
Thuật toán sắp xếp nào? 
for i ←  n - 1 to 2         for j  ← 1 to i - 1                   if A[ j ] > A[ j + 1 ]                          Swap A[ j ] ↔ A[j + 1] 
Thuật toán sắp xếp nào? 
for j ←  2 to n           key ← A[ j ] 
 i ← j - 1           while i > 0 and A[ i ] > key 
	 A [ i + 1 ] ← A[ i ] 
	 i ← i - 1                    A [ 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 con A[p.. q-1] và A[q+1..r] có các phần tử tương ứng nhỏ hơn hoặc bằng A[q ] và lớn hơn A[q] 
Conquer : Sắp xếp hai mảng con A[p..q-1] và A[q+1.. r] bằng lời gọi đệ qui 
3 
5 
2 
1 
7 
Chốt 
i 
j 
3 
5 
2 
1 
7 
i 
j 
3 
5 
2 
1 
7 
i 
j 
1 
5 
2 
3 
7 
i 
j 
1 
5 
2 
3 
7 
i 
j 
1 
5 
2 
3 
7 
i 
j 
1 
2 
5 
3 
7 
i 
j 
1 
2 
5 
3 
7 
i 
j 
5 
3 
7 
i 
j 
2 
Bên trái 
5 
3 
7 
i 
j 
3 
5 
7 
j 
i 
3 
5 
7 
i 
j 
Bên phải 
1 
i 
j 
2 
1 
j 
i 
1 
2 
3 
5 
7 
1 
3 
5 
7 
7 
5 
7 
5 
2 
3 
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) i++; 
	while (A[j]>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(nlog 2 n) 
Trung bình T(n)= O(nlog 2 n) 
Xấu nhất T(n )= O(n 2 ) 
Sắp xếp trộn (Mergesort) 
Được thiết kế dựa trên kỹ thuật chia để trị (divide-andconquer): 
Divide : Phân hoạch A[p..r] thành hai mảng con A[p..q] và A[q+1 ..r] với q= 
Conquer : Sắp xếp hai mảng con A[p..q] và A[q+1..r] bằng lời gọi đệ qui và kết hợp chúng để để tạo thành mảng được sắp 
// Thủ tục trộn gọi đệ quyvoid MergeSort(int X[], int L, int R){   int M;   if (L<R){      M=int((L+R)/2);      MergeSort(X,L,M);      MergeSort(X,M+1,R );       Merge(X,L,M+1,R);   }} 
// Thủ tục trộn hai đoạn đã sắp xếp trong một dãyvoid Merge(int a[], int k1, int k2, int k3){   int i,j,k,t;   int temp[ 40000 ];      i=k1; j=k2; k=k 1 ;    while ( ( i<k2) && (j<=k3 ) )    {      if (a[i]<=a[j]){          temp[k ]=a[i];         i=i+1;      }      else{         temp[k]=a[j];         j=j+1;      }  
      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];} 
ĐỘ PHỨC TẠP: O(nlog 2 n) 
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ự, mỗi nút tương ứng với một phần tử của mảng , gốc ứng với phần tử đầu tiên của mảng 
Cây cân bằng và được lấp đầy trên tất cả các mức, ngoại trừ mức thấp nhất được lấp đầy từ bên trái sang (có thể chưa lấp đầy) 
Ví dụ với dãy số: 
	 	5, 25, 15, 8, 7, 28 
Ta có thể xây dựng heap như sau: 
heapsort 
Một MaxHeap là một Heap mà giá trị của mỗi nút lớn hơn hoặc bằng) giá trị các nút con 
Gọi i là chỉ số thứ tự của một nút (của mảng), thì chỉ số các nút cha, con trái và con phải là: 
	 PARENT(i ) = 
	 LEFT_CHILD(i ) = 2i 
	 RIGHT_CHILD(i )= 2i+ 1 
Ví dụ MaxHeap: 
 1 2 3 4 5 6 7 8 
heapsort 
Giải thuật HeapSort biến đổi mảng về 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ại các bước trên cho đến khi Heap chỉ 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 tại i thành một MaxHeap (gốc tại i) 
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 
MaxHeapify(A[1..n], i) 
	l ← 2*i; r ← 2*i+1 
	if lA[i] largest ← l 
	else largest ← i 
	if rA[largest] largest ← r 
	if largest i 
	Exchange(A[i ], A[largest]) 
	MaxHeapify(A , largest) 
buildmaxheap 
Các nút có chỉ số +1, +2 , ..., n trong A[1.. n] là các lá của cây, mỗi nút như vậy là một MaxHeap 
BuildMaxHeap áp dụng MaxHeapify cho các nút con khác lá của cây từ dưới lên gốc bắt đầu từ nút 
Kết quả là một MaxHeap tương ứng với A[1..n] 
buildmaxheap 
BuildMaxHeap(A[1..n]) 
	 for i ← n/2 downto 1 
	 do MaxHeapify(A, i) 
Độ phức tạp 
Kích thước đầu vào là n (số phần tử của mảng) 
Gọi chiều cao của cây là h, do cây cân bằng nên h = 
Thời gian chạy của MaxHeapify là O(log 2 n ) 
Thời gian chạy của Buil d MaxHeap tối đa là O(nlog 2 n) 
T hời gian chạy của HeapSort l à T(n)=O(nlog 2 n ) 
Yêu cầu: Cho dãy số nguyên gồm n phần tử. Hãy 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 < 4 0000) 
+ Dòng 2 chứa dãy số nguyên gồm n chữ số 
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. 
Ví dụ: 
SAPXEP2A.INP 
5 
3 5 2 1 7 
SAPXEP2A.OUT 
1 2 3 5 7 
Giải bài toán này bằng 2 thuật toán sắp xếp: Quick Sort, Merge Sort và Heap Sort 
Yêu cầu: Cho dãy số nguyên gồm n số đôi một khác nhau và số nguyên dương k (k < n ). Hãy tìm giá trị nhỏ thứ k trong dãy. 
Input: Dữ liệu vào từ file GIATRI.INP gồm 2 dòng: 
+ Dòng 1: Gồm 2 số nguyên dương n và k (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 chứa giá trị nhỏ thứ k của dãy số 
Ví dụ: 
GIATRI . INP 
5 3 
5 7 1 3 4 
GIATRI.OUT 
4 
Yêu cầu: Cho dãy số nguyên gồm n phần tử (n<2000). Hãy đếm số lượng giá trị khác nhau trong dãy 
Ví dụ: 
DEMSO1.INP 
8 
6 7 1 7 4 6 6 8 
DEMSO1.OUT 
5 
Bài toán: 
Cho dãy số nguyên gồm n phần tử (n <= 1000000) . Với mọi phần tử k trong dãy, 0 <= k < 100 . H ãy sắp xếp dãy số theo thứ tự tăng dần. 
Sắp xếp bằng đếm (Counting SORT) 
T huật toán này được áp dụng trong trường hợp đặc biệt, khi mà tất cả các giá trị trong mảng đều là số nguyên và thuộc khoảng [0 .. k ] đã biết. 
Ý tưởng : Xét trong khoảng [0 .. k ] , đếm xem trong mảng có bao nhiêu giá trị 0 (giả sử là a), bao nhiêu giá trị 1 (giả sử là b), , bao nhiêu giá trị k (giả sử là z ) , sau đó xếp lại mảng bằng cách đặt a phần tử 0 ở đầu, tiếp theo đặt b phần tử 1 tiếp theo, , và đặt z phần tử k ở cuối cùng . 
1 
2 
3 
5 
7 
0 
1 
2 
3 
4 
5 
6 
7 
8 
... 
100 
0 
0 
0 
0 
0 
0 
0 
0 
0 
... 
0 
3 
5 
2 
1 
7 
0 
1 
2 
3 
4 
5 
6 
7 
8 
... 
100 
0 
1 
1 
1 
0 
1 
0 
1 
0 
... 
0 
0 
1 
2 
3 
4 
5 
6 
7 
8 
... 
100 
0 
0 
0 
0 
0 
0 
0 
0 
0 
... 
0 
2 
5 
2 
1 
5 
3 
2 
1 
2 
2 
2 
3 
5 
5 
0 
1 
2 
3 
4 
5 
6 
7 
8 
... 
100 
0 
1 
3 
1 
0 
2 
0 
0 
0 
... 
0 
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í được sắp chính xác của nó trong mảng B căn cứ vào số phần tử nhỏ hơn hoặc bằng A[j] trong C[A[j]] 
Giảm C[A[j]] đi 1 trong dòng 10 để các phần tử còn lại bằng A[j] sẽ được đặt chính xác 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]; 
i nt 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ử trong mỗi lô và nối các lô để có mảng đượ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ó thứ tự nhờ giải thuật chèn trực tiếp 
- Ngược lại, gọi các lô tương ứng của A[i] và A[j] là B[i’ ] và B[j ’ ], nếu i’ < j’ thì lô B[i’ ] được nối trướ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? 
Yêu cầu: Cho dãy số nguyên gồm n số đôi một khác nhau (n<=1000 ) . Hãy tìm tổng 3 giá trị nhỏ nhất trong dãy. 
Input: Dữ liệu vào từ file GIATRI 2 .INP gồm 2 dòng: 
+ Dòng 1: Chứa số nguyên n 
+ Dòng 2 chứa dãy số nguyên n phần tử 
Output: Xuất ra file GIATRI 2 .OUT , gồm 1 dòng chứa tổng 3 giá trị nhỏ nhất dãy số 
Ví dụ: 
GIATRI 2. INP 
5 
5 7 1 3 4 
GIATRI 2 .OUT 
8 
Yêu cầu: Cho dãy số nguyên gồm n (n < 10 6 ) 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