# Chuyên đề Sắp xếp (Sorting)
Viết bởi: Nguyễn Thế Ngọc Hà
Chuẩn bị bởi: Nguyễn Thế Ngọc Hà và Trần Bá Anh Hào
## Sắp xếp trộn (Merge Sort)
### Ý tưởng
Hoạt động theo kiểu đệ quy:
- Chia dữ liệu làm 2 phần.
- Sắp xếp 2 phần đó bằng kĩ thuật 2 con trỏ (2 pointer).
### Ưu điểm
- Chạy nhanh, độ phức tạp $O(NlogN)$.
- Ổn định
### Nhược điểm
- Cần dùng thêm bộ nhớ để tạo một mảng để lưu.
### Mô phỏng
https://visualgo.net/en/sorting
### Cài đặt

// 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[MAX], 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];
}

## Sắp xếp chọn (Selection Sort)
### Ý tưởng
Lần lượt chọn ra các phần tử nhỏ nhất trong dãy để đưa nó về đúng vị trí.
### Ưu điểm
Dễ cài đặt, ngắn.
### Nhược điểm
Chạy rất lâu với dữ liệu lớn, độ phức tạp $O(N^2)$.
### Mô phỏng
https://visualgo.net/en/sorting
### Cài đặt

int mn,idx;
for (int i=0;i<n;i++){
    mn=a[i];
    idx=i;
    for (int j=i;j<n;j++){
        if (mn>a[j]){
            //Lưu chỉ số của phần tử nhỏ nhất vừa tìm
            mn=a[j];
            idx=j;
        }
    }
    swap(a[idx],a[i]); //Tráo đổi vị trí với phần tử thứ i
}

## Sắp xếp đếm phân phối (Counting Sort)
### Ý tưởng
Các phần tử được lưu giữ trong một mảng từ $1$ đến $c$ và $c = O(N)$. Chỉ số của mảng phụ chính là các phần tử ở mạng cần sắp xếp còn giá trị các phần tử thể hiện cho số lần xuất hiện của phần tử ấy.
### Ưu điểm
Chạy rất nhanh, trong 1 số trường hợp mà các phần tử trong mảng không phân cách quá lớn thì thuật toán này là nhanh nhất.
### Nhược điểm
Sử dụng nhiều bộ nhớ.
### Cài đặt

for (int i=0;i<n;i++){
    d[a[i]]++;
    mx=max(a[i],mx);
}
for(int i=0;i<=mx;i++){
    while (d[i]!=0){
        cout<<i<<" ";
        i--;
    }
}