Cơ bản thuật toán sắp xếp và đồ thị - DSA On Thi Thao tác 2. Môn Cấu trúc dữ liệu và giải thuật (UET) | Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội.

lOMoAR cPSD| 59735516 Cơ bản thuật toán:
các thuật toán sort (selection, insertion, merge, quick, heapsort),
đồ thị (DFS, BFS,cây bao trùm min, đường đi ngắn nhất (Dijkstra)
- hiểu ý tưởng, làm bằng tay được,
- biết độ phức tạp tính toán theo thời gian chạy và bộ nhớ, trường hợp tốt nhất/tồi nhất/trung bình.
- áp dụng được cho bài toán cụ thể (với bài toán cụ thể, cho biết cần sử dụng thuật toán
gì để giải, mô hình hóa dữ liệu của bài toán như thế nào)
- biết được ưu nhược điểm của mỗi thuật toán (ví dụ insertion sort chạy nhanh đối với mảng gần sắp xếp)
- khi có câu hỏi lựa chọn một giải pháp (cấu trúc dữ liệu hoặc thuật toán) trong các giải
pháp có sẵn, cần giải thích được lý do. 1. Selection Sort
- Ý tưởng: Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong danh sách chưa được sắp xếp.
Đưa phần tử đó về vị trí đúng trong danh sách đã được sắp xếp. Lặp lại cho đến khi
danh sách được sắp xếp hoàn toàn.
- Độ phức tạp thuật toán: Tốt nhất: O(n) (khi mảng đã được sắp xếp); trung bình, xấu nhất: O(n^2).
- Độ phức tạp bộ nhớ: O(1).
- Có ổn định không: Không. - Ưu/Nhược điểm:
- Phù hợp với danh sách nhỏ < 20 phần tử; Không yêu cầu thêm bộ nhớ.
- Độ phức tạp cao O(n^2); Không ổn định: Thứ tự phần tử bằng nhau có thể bị thay đổi.
- Bài toán cụ thể: Sắp xếp học sinh theo điểm số tăng dần.
- Giải pháp tối ưu khi nào: Khi danh sách nhỏ và cần giảm số lần hoán đổi. - C++:
void selectionsort(int arr[], int n)
{ for(int i = 0; i < n; i++) { int min_pos = i;
for(int j = i + 1; j < n; j++) { if(a[j] < a[min_pos]) { min_pos = j; } } swap(a[i], a[min_pos]); } } 2. Insertion Sort
- Ý tưởng: Chia danh sách thành hai phần đã được sắp xếp và chưa được sắp xếp. Lấy
từng phần tử từ phần chưa được sắp xếp, chèn đúng vào vị trí trong phần đã sắp xếp. Lặp lại quá trình. lOMoAR cPSD| 59735516
- Độ phức tạp thuật toán: Tốt nhất: O(n); Trung bình, tệ nhất: O(n^2).
- Độ phức tạp bộ nhớ: O(1).
- Có ổn định không: Có. - Ưu/nhược điểm:
- Là thuật toán ổn định, Hiệu quả với danh sách hoặc mảng có kích thước nhỏ.
- Hiệu suất kém: O(n^2). Không phù hợp với danh sách lớn và danh sách ngẫu nhiên.
- Bài toán cụ thể: Sắp xếp danh sách nhỏ các số.
- Giải pháp tối ưu khi nào: Khi danh sách nhỏ < 20 phần tử. Danh sách gần như đã sắp
xếp. Hệ thống yêu cầu ổn định. Dùng cho các mảng con nhỏ trong Merge Sort hoặc Quick Sort. - C++:
void insertionsort(int arr[], int n)
{ for(int i = 1; i < n; i++) { int x = a[i]; int pos = i - 1;
while(pos >= 0 && x < a[pos]) { a[pos + 1] = a[pos]; pos--; } a[pos + 1] = x; } } 3. Merge Sort
- Ý tưởng: Chia mảng ban đầu thành hai nửa bằng nhau cho đến khi còn một phần tử,
Sắp xếp các mảng con. Gộp hai mảng con đã sắp xếp thành một mảng lớn cũng được sắp xếp.
- Độ phức tạp thuật toán: Tốt nhất, trung bình, tệ nhất: O(nlog(n)).
- Độ phức tạp bộ nhớ: O(n). - Ưu/nhược điểm:
- Thời gian chạy ổn định O(nlog(n)) cho mọi trường hợp và dữ liệu lớn. Không phụ thuộc
vào phân bố dữ liệu ban đầu.
- Cần bộ nhớ phụ O(n), không phù hợp với môi trường hạn chế bộ nhớ. Tốc độ chậm hơn
Quicksort, cài đặt phức tạp hơn Bubble và Insertion.
- Bài toán cụ thể: Sắp xếp một mảng số nguyên.
- Giải pháp tối ưu khi nào: Dữ liệu lớn cần ổn định. hạn chế thời gian chạy tệ nhất. - C++:
void merge(int arr[], int left, int middle, int right)
{ vector x(a + left,a + middle + 1);
vector y(a + middle + 1, a + right + 1);
int i = 0; int j = 0; while(i < x.size() && j
< y.size()) { if(x[i] <= y[j]) { a[left] = x[i]; left++; i++; lOMoAR cPSD| 59735516 } else { a[left] = y[j]; left++; j++; } } while(i < x.size()) { a[left] = x[i]; left++; i++; } while(j < y.size()) { a[left] = y[j]; left++: j++; } }
void mergesort(int arr[], int left, int right)
{ if(left >= right) return; int middle =
(left + right) / 2; mergesort(a, left,
middle); mergesort(a, middle+1, right);
merge(a, left, middle, right); } 4. Quick Sort
- Ý tưởng: Chọn Pivot (1 phần tử trong mảng làm điểm mốc), chia mảng thành hai phần;
phần bên trái chứa các phần tử nhỏ hơn hoặc bằng pivot; phần bên phải chứa các phần
tử lớn hơn pivot; Áp dụng đệ quy Quicksort cho đến khi mỗi phần chỉ còn một phần tử.
- Độ phức tạp thuật toán: Tốt nhất: O(nlog(n)); Trung bình: O(nlog(n)); Tệ nhất: O(n^2)
- Độ phức tạp bộ nhớ: O(log(n)) -
Có ổn định không: Không - Ưu/nhược điểm:
- Nhanh (Thường nhanh hơn Merge Sort trong thực tế): không cần bộ nhớ phụ lớn; cấu trúc đơn giản.
- Không ổn định; Đệ quy sâu.
- Bài toán cụ thể: Sắp xếp một mảng số nguyên
- Giải pháp tối ưu khi nào: Dữ liệu ngẫu nhiên; Không gian bộ nhớ hạn chế; Cần tốc độ cao. - C++:
int partition(vector &arr, int low, int high)
{ int pivot = arr[high]; int i = low - 1;
for(int j = low; j < high; j++) { if(arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i+1], arr[high]); return i+1; } lOMoAR cPSD| 59735516
void quicksort(vector &arr, int low, int high)
{ int(low < high) { int pi =
partition(arr, low, high); quicksort(arr,
low, pi-1); quicksort(arr, pi+1, high); } } 5. Heap Sort
- Ý tưởng: Dựa trên cấu trúc dữ liệu heap(đống), chuyển đổi mảng ban đầu thành một
Max(min-heap) - phần tử lớn nhất nằm ở gốc. Đổi gốc với phần tử cuối, loại phần tử
cuối ra khỏi heap. Điều chỉnh phần còn lại đảm bảo tính chất Max-heap. tiếp tục duy trì.
- Độ phức tạp thuật toán: Tốt nhất, trung bình, tệ nhất: O(nlog(n))
- Độ phức tạp bộ nhớ: O(1) - Có ổn định không: Không - Ưu/nhược điểm:
- Thời gian chạy ổn định; Không dùng bộ nhớ phụ; Không phụ thuộc vào phân bố dữ liệu.
- Không ổn định, hiệu suất thấp hơn quicksort trong thực tế.
- Bài toán cụ thể: Sắp xếp một mảng số nguyên.
- Giải pháp tối ưu khi nào: Không gian bộ nhớ hạn chế, Dữ liệu cần sắp xếp trên chỗ, Dữ liệu không ổn định. - C++:
void heapify(vector &arr, int n, int i) { int largest
= i; int left = 2*i+1; int right = 2*i+2; if(left <
n && arr[left] > arr[largest]) largest = left; if(right < n
&& arr[right] > arr[largest]) largest = right;
if(largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } }
void heapsort(vector &arr) { int
n = arr.size(); for(int i = n/2 - 1;
i >= 0; i--) { heapify(arr, n,
i); for(int i = n - 1; i >= 0; i- -) { swap(arr[0], arr[i]); heapify(arr, i , 0); } } } 6. BFS
- Ý tưởng: duyệt hoặc tìm kiếm trên đồ thị/ cây theo chiến lược rộng trước. sử dụng hàng
đợi để duyệt qua các đỉnh theo mức độ từ gần -> xa.
- Độ phức tạp thuật toán: Tốt nhất, trung bình, tệ nhất: O(V+E). - Độ phức tạp bộ nhớ: O(V) - Ưu/nhược điểm:
- Đơn giản và dễ triển khai, Tìm đường đi ngắn nhất (đồ thị vô hướng, không có trọng số). lOMoAR cPSD| 59735516
- Bộ nhớ tốn kém, không phù hợp với đồ thị có trọng số.
- Bài toán cụ thể: tìm đường đi ngắn nhất trên đồ thị vô hướng, không trọng số từ đỉnh bắt
đầu đến một đỉnh đích.
- Giải pháp tối ưu khi nào: tìm đường ngắn nhất trên đồ thị không trọng số, khám phá
toàn bộ đồ thị, không yêu cầu tối ưu hóa về bộ nhớ. 7. DFS
- Ý tưởng: duyệt hoặc tìm kiếm trên đồ thị/ cây theo chiến lược sâu trước. sử dụng ngăn
xếp (stack) hoặc đệ quy để khám phá các đỉnh, ưu tiên đi sâu vào nhánh hiện tại cho
đến khi không thể tiếp tục.
- Độ phức tạp thuật toán: Tốt nhất, trung bình, tệ nhất: O(V+E).
- Độ phức tạp bộ nhớ: O(V). - Ưu/nhược điểm:
- Đơn giản và dễ triển khai, hiệu quả với đồ thị lớn, khám phá thành phần liên thông.
- Không tìm đường đi ngắn nhất, rủi ro tràn ngăn xếp đệ quy, tốn bộ nhớ hơn.
- Bài toán cụ thể: Kiểm tra thành phần liên thông của đồ thị
- Giải pháp tối ưu khi nào: Khám phá toàn bộ đồ thị, Bài toán tìm đường, Không yêu cầu đường đi ngắn nhất
8. Minimum Spanning Tree - Kruskal and Prim - Ý tưởng:
- Kruskal: là thuật toán dựa trên canh, chọn lần lượt các cạnh có trọng số nhỏ
nhất và thêm vào cây bao trùm, với điều kiện không tạo thành chu trình.
- Prim: là thuật toán dựa trên đỉnh, mở rộng cây bao trùm bằng cách lần lượt thêm
các đỉnh kề với cây hiện có trọng số nhỏ nhất.
- Độ phức tạp thuật toán: - Kruskal: O(ElogE). - Prim: O((V+E)logV).
- Độ phức tạp bộ nhớ: - Kruskal: O(E+V). - Prim: O(V+E). - Ưu/nhược điểm:
- Kruskal: Dễ triển khai trực quan, Phù hợp với đồ thị thưa; Hiệu suất giảm nếu đồ
thị có rất nhiều cạnh.
- Prim: Phù hợp với đồ thị dày đặc, không cần sắp xếp các cạnh trước; Cần hàng
đợi ưu tiên để quản lý, việc triển khai phức tạp hơn so với Kruskal, hiệu suất
giảm với đồ thị thưa
- Bài toán cụ thể: Tìm cây bao trùm tối thiểu.
- Giải pháp tối ưu khi nào: - Kruskal: Đồ thị thưa.
- Prim: Đồ thị dày đặc. 9. Dijkstra lOMoAR cPSD| 59735516
- Ý tưởng: tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong một
đồ thị có trọng số không âm.
- Độ phức tạp thuật toán: Tốt nhất, trung bình, tệ nhất: O((V+E)logV).
- Độ phức tạp bộ nhớ: O(V+E). - Ưu/nhược điểm:
- Hiệu quả với đồ thị có trọng số không âm, Đảm bảo tìm đường đi ngắn nhất tới mọi đỉnh.
- Không hoạt động với đồ thị có cạnh có trọng số âm, phức tạp hơn về mặt triển khai.
- Bài toán cụ thể: Tìm đường đi ngắn nhất từ 1 đỉnh đến tất cả các đỉnh.
- Giải pháp tối ưu khi nào: Đồ thị không âm, đồ thị thưa, Đường đi ngắn nhất từ một nguồn duy nhất.