Sắp xếp

---

Tác giả : Dương Nguyên Khánh

tags:Algorithm,Sort

Mở đầu

Chỉ là sắp xếp

Khái niệm

Sắp xếp theo thứ tự =))

Các loại sắp xếp

Sắp xếp nổi bọt (Bubble Sort)

Ý tưởng

Xét lần lượt các cặp 2 phần tử liên tiếp. 
Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước,ta đổi chỗ 2 phần tử. 
Nói cách khác, phần tử nhỏ nhất sẽ nổi lên trên.

Minh hoạ

Cài đặt

void sort(int a[],int n) //n là số phần tử của mảng a
for (int i = 0; i < n; i++)
	for (int j = 0; j < n - 1; j++)
		if (a[j] > a[j+1]) {
			swap(a[j], a[j+1]);
		}

Nhận xét : Dễ viết nhưng không tối ưu khiến tốn thời gian xử lí

Sắp xếp chèn (Insertion Sort)

Ý tưởng

Ý tưởng chính của thuật toán là ta sẽ sắp xếp lần lượt từng đoạn gồm 1 phần tử 
đầu tiên, 2 phần tử đầu tiên, …, N phần tử.
Giả sử ta đã sắp xếp xong i
phần tử của mảng. Để sắp xếp i+1 phần tử đầu tiên, ta tìm vị trí phù hợp của 
phần tử thứ i+1 và "chèn" nó vào đó.

Minh họa

Cài đặt

for (int i = 1; i < n; i++) {
	// Tìm vị trí phù hợp cho i
	int j = i;
	while (j > 0 && data[i] < data[j-1]) --j;

	// Đưa i về đúng vị trí
	int tmp = data[i];
	for (int k = i; k > j; k--)
		data[k] = data[k-1];
	data[j] = tmp;
}

Nhận xét : Nếu danh sách đã gần đúng thứ tự, Insertion Sort sẽ chạy rất nhanh nhưng vì nếu gặp trường hợp xấu thì có độ phức tạp O(N^2) không phù hợp với số lượng lớn

Sắp xếp trộn (Merge Sort)

Ý tưởng

Các sắp xếp này dựa vào giải thuật của đệ quy
Đầu tiên chia dữ liệu thành 2 phần, và sắp xếp từng phần.
Tạo một dãy A mới để chứa các phần tử đã sắp xếp sau khi gộp.
So sánh 2 phần tử đầu tiên của 2 phần.Phần tử nhỏ hơn ta cho vào A và xóa khỏi phần tương ứng.
Tiếp tục như vậy đến khi ta cho hết các phần tử vào dãy A.

Minh họa

Cài đặt

int a[MAXN]; // mảng trung gian cho việc sắp xếp
// Sắp xếp các phần tử có chỉ số từ left đến right của mảng data.
void mergeSort(int data[MAXN], int left, int right) {
	if (data.length == 1) {
		// Dãy chỉ gồm 1 phần tử, ta không cần sắp xếp.
		return ;
	}
	int mid = (left + right) / 2;
	// Sắp xếp 2 phần
	mergeSort(data, left, mid);
	mergeSort(data, mid+1, right);
	// Trộn 2 phần đã sắp xếp lại
	int i = left, j = mid + 1; // phần tử đang xét của mỗi nửa
	int cur = 0; // chỉ số trên mảng a
	while (i <= mid || j <= right) { // chừng nào còn 1 phần chưa hết phần tử.
		if (i > mid) {
			// bên trái không còn phần tử nào
			a[cur++] = data[j++];
		} else if (j > right) {
			// bên phải không còn phần tử nào
			a[cur++] = data[i++];
		} else if (data[i] < data[j]) {
			// phần tử bên trái nhỏ hơn
			a[cur++] = data[i++];
		} else {
			a[cur++] = data[j++];
		}
	}
	// copy mảng a về mảng data
	for (int i = 0; i < cur; i++)
		data[left + i] = a[i];
}

Nhận xét : Khá là nhanh O(N∗logN) và độ chính xác lớn nhưng lại tốn bộ nhớ vì mảng A

Sắp xếp vun đống (Heap Sort)

Ý tưởng

Nói thẳng ra là dùng cấu trúc dữ liệu Heap và ở mỗi bước 
ta lấy ra phần tử nhỏ nhất trong heap, cho vào mảng đã sắp xếp.

Minh họa

Cài đặt

Heap h = Heap();
for (int i = 0; i < n; i++) {
	// thêm phần tử vào heap
	h.push(data[i]);
}
int a[MAXN];
for (int i = 0; i < n; i++) {
	// lấy phần tử nhỏ nhất và cho vào mảng đã sắp xếp
	a[i] = h.pop();
}

Nhận xét : Khá là nhanh O(N∗logN) và dễ code vì sử dụng cấu trúc dữ liệu có sẵn là Heap nhưng lại có độ chính xác không quá cao

Sắp xếp nhanh (Quick Sort)

Ý tưởng

Chia dãy thành 2 phần, một phần "lớn" và một phần "nhỏ". 
Chọn một khóa pivot
Những phần tử lớn hơn pivot chia vào phần lớn
Những phần tử nhỏ hơn hoặc bằng pivot chia vào phần nhỏ.
Gọi đệ quy để sắp xếp 2 phần.

Minh họa

Cài đặt

Heap h = Heap();
for (int i = 0; i < n; i++) {
	// thêm phần tử vào heap
	h.push(data[i]);
}
int a[MAXN];
for (int i = 0; i < n; i++) {
	// lấy phần tử nhỏ nhất và cho vào mảng đã sắp xếp
	a[i] = h.pop();
}

Nhận xét : Chạy nhanh (nhanh nhất trong các thuật toán sắp xếp dựa trên việc só sánh các phần tử).
Do đó Quicksort được sử dụng trong nhiều thư viện của các ngôn ngữ như Java, C++ (hàm sort của C++ dùng Intro sort, là kết hợp của Quicksort và Insertion Sort) nhưng mà thể đây là thứ đã khiến năm lớp 8 của tôi mắc kẹt:-1:
Nhược điểm :

Tùy thuộc vào cách chia thành 2 phần, nếu chia không tốt, độ phức tạp trong 
trường hợp xấu nhất có thể là O(N2). 
Nếu ta chọn pivot ngẫu nhiên,thuật toán chạy với độ phức tạp trung bình 
là O(N∗logN) (trong trường hợp xấu nhất vẫn là O(N2)
nhưng ta sẽ không bao giờ gặp phải trường hợp đó) và không ổn định

Sắp xếp STL C++ (Khuyên dùng)

Ý tưởng

Intro sort, là kết hợp của Quicksort và Insertion Sort

Minh họa

Cài đặt

int a[N]//tạo mảng N phần tử
std::sort(a,a+N);

Nhận xét :Ngon lành cành đào vì code thì ngon nhanh gọn lẹ lại còn độ chính xác cao

Ứng dụng về sắp xếp có ở khắp mọi nơi:

​​​​Một danh sách lớp với các học sinh được sắp xếp theo thứ tự bảng chữ cái.
​​​​Một danh bạ điện thoại.
​​​​Danh sách các truy vấn được tìm kiếm nhiều nhất trên Google.
​​​​Đây là một thuật toán vô cùng quan trọng và được sử dụng ở nhiều bài