Trong việc sắp xếp các giá trị của mảng tăng dần hay giảm dần thì chúng ta có rất nhiều thuật toán và Bucket Sort cũng là một thuật toán sắp xếp như vậy. Trong bài viết này tôi sắp xếp tăng dần bằng thuật toán Bucket Sort.
Data Structure & Algorithm Phạm Hoài Nguyên 2015-12-09 04:31:40

Giới thiệu

Như chúng ta đã biết, có rất nhiều thuật toán sắp xếp và Bucket sort cũng là một trong số đó, tính hữu dụng của thuật toán Bucket sort khi chúng ta cần sắp xếp các dãy số nằm trong một điều kiện nhất định, ví dụ như sắp xếp dãy số  với các phần tử nằm trong khoảng 0.1 đến 1.0 hay là từ 1 đến 100. Trong bài viết này, tôi sử dụng thuật toán Bucket sort sắp xếp mảng tăng dần và sử dụng ngôn ngữ C++ để cài đặt. 

Tiền đề bài viết

Bài viết này nằm trong loạt bài viết về thuật toán sắp xếp của STDIO.

Đối tượng hướng đến

Những ai có kiến thức căn bản về lập trình và muốn tìm hiểu về thuật toán Bucket sort.

Bucket sort

Ý tưởng

Đặt các phần tử của mảng input vào các xô thích hợp, sau khi đặt hết tất cả các phần tử vào trong các xô thì trong mỗi xô chúng ta sắp xếp các phần tử trong xô theo thứ tự. Cuối cùng là liên kết các xô lại trở thành dãy các phần tử đã được sắp xếp theo thứ tự, để hiểu rõ hơn thì các bạn theo dõi ví dụ sau đây.

Bucket_Sort

Độ phức tạp của thuật toán là O(n log n).

Code demo

void bucketSort(float arr[], int n)
{
	//Tạo các Bucket rỗng
	vector<int> b[n];

	//Đặt các phần tử vào các Bucket
	for (int i=0; i<n; i++)
	{
		int bi = n*arr[i]; // Địa chỉ của Bucket
		b[bi].push_back(arr[i]);
	}

	//Sắp xếp trong từng Bucket
	for (int i=0; i<n; i++)
		sort(b[i].begin(), b[i].end());

	//Liên kết tất cả các Bucket lại
	int index = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < b[i].size(); j++)
			arr[index++] = b[i][j];
}