TỔNG QUAN VỀ THUẬT TOÁN TÌM KIẾM VÀ THUẬT TOÁN SẮP XẾP
Khái quát về các thuật toán tìm kiếm và thuật toán sắp xếp
Trong quá trình thao tác và khai thác dữ liệu, việc tìm kiếm là một thao tác thiết yếu Trong khoa học máy tính và toán học, bài toán tìm kiếm liên quan đến việc xác định sự tồn tại và vị trí của một phần tử trong danh sách Tốc độ tìm kiếm phụ thuộc vào trạng thái và trật tự của danh sách đó Đầu vào của bài toán là một danh sách có thể chứa hoặc không chứa phần tử cần tìm, thường gặp là tìm kiếm một số trong dãy số đã cho.
Tìm kiếm phần tử X trong danh sách N phần tử A(0), A(1), , A(n-1) là quá trình so sánh X với các phần tử của dãy để xác định sự tồn tại của X Thuật toán tìm kiếm chủ yếu dựa vào thao tác so sánh, vì vậy cần tối ưu hóa số lần so sánh để nâng cao hiệu suất của thuật toán.
Trong khoa học máy tính và toán học, bài toán sắp xếp yêu cầu sắp xếp các phần tử trong một danh sách theo thứ tự nhất định, có thể là tăng dần hoặc giảm dần Đầu vào là danh sách các phần tử chưa sắp xếp, và đầu ra là danh sách đã được sắp xếp Thông thường, bài toán này thường xem xét các phần tử là các số và thực hiện sắp xếp theo chiều tăng dần.
Sắp xếp danh sách có N phần tử A(0), A(1), , A(n-1) là quá trình tổ chức các phần tử theo thứ tự nhất định dựa trên thông tin của từng phần tử Quyết định thay đổi vị trí các phần tử phụ thuộc vào kết quả của các phép so sánh, vì vậy hai thao tác cơ bản trong thuật toán sắp xếp là so sánh và đổi chỗ Để nâng cao hiệu quả, cần giảm thiểu các phép so sánh và đổi chỗ không cần thiết Trong trường hợp danh sách lưu trữ trong bộ nhớ chính, việc tiết kiệm bộ nhớ là ưu tiên hàng đầu, dẫn đến việc các thuật toán sắp xếp tại chỗ, không yêu cầu cấp phát thêm vùng nhớ, được phát triển mạnh mẽ Để biến một danh sách chưa có thứ tự thành danh sách có thứ tự tăng, cần triệt tiêu tất cả các cặp nghịch thế, tức là sắp xếp lại danh sách sao cho mọi cặp đều là thuận thế.
Trong lĩnh vực khoa học máy tính, bài toán tìm kiếm và sắp xếp đã thu hút sự chú ý đáng kể từ các nhà nghiên cứu, trở thành một trong những chủ đề quan trọng nhất trong công nghệ.
Thuật toán tìm kiếm và sắp xếp là hai trong những thuật toán quan trọng nhất trong lập trình Chúng đang được các lập trình viên và nhà khoa học nghiên cứu và phát triển không ngừng để cải thiện hiệu suất Hiện tại, đã có hơn 40 thuật toán sắp xếp được phát minh trên toàn thế giới.
Các thuật toán tìm kiếm và sắp xếp đóng vai trò quan trọng trong nhiều chương trình và ứng dụng phần mềm Chúng được sử dụng rộng rãi để xử lý cơ sở dữ liệu và phát triển các tính năng, mô-đun cho phần mềm.
Một số ví dụ về các tính năng cần sử dụng thuật toán tìm kiếm và thuật toán sắp xếp:
Quản lý, tìm kiếm file, sắp xếp các file, data dựa vào ngày tạo, dung lượng file, tên file
Các dạng bảng xếp hạng
Để tối ưu hóa chương trình, việc tìm kiếm sản phẩm và sắp xếp theo giá là rất quan trọng Các nguồn dữ liệu đầu vào khác nhau yêu cầu áp dụng thuật toán phù hợp, vì thuật toán có thể ảnh hưởng lớn đến tốc độ sản phẩm và trải nghiệm người dùng.
Thuật toán tìm kiếm và sắp xếp là những kiến thức quan trọng mà lập trình viên mới cần nắm vững Việc tìm hiểu về các thuật toán này không chỉ giúp cải thiện khả năng tư duy giải thuật mà còn là nền tảng cần thiết cho sự nghiệp lập trình sau này.
Phân loại thuật toán tìm kiếm
Thuật toán sắp xếp có thể phân loại theo nhiều cách khác nhau dựa trên tính chất và đặc điểm của thuật toán.
1.2.1 Phân loại dựa theo dữ liệu:
Dữ liệu chưa được sắp xếp : Linear search
Dữ liệu đã sắp xếp : Binary search
1.2.2 Phân loại theo độ phức tạp của thuật toán: Độ phức tạp tính toán hoặc đơn giản là độ phức tạp của thuật toán là lượng tài nguyên cần thiết để chạy nó Độ phức tạp thường đánh giá dựa trên thời gian chạy và bộ nhớ sử dụng của thuật toán.
Dựa vào tính chất này, có thể chia thuật toán tìm kiếm thành 3 loại:
Độ phức tạp xấu O(n): Linear search
Độ phức tạp trung bình O(log n): Binary search, Tenary search ( tìm kiếm tam phân)…
Độ phức tạp tốt O (log [sqrt (n)] or log(log(n))): Jump search, interpolation search…
Phân loại thuật toán sắp xếp
Thuật toán sắp xếp có thể phân loại theo nhiều cách khác nhau dựa trên tính chất và đặc điểm của thuật toán.
1.3.1 Phân loại theo độ phức tạp của thuật toán: Độ phức tạp tính toán hoặc độ phức tạp của thuật toán là lượng tài nguyên cần thiết để chạy nó Độ phức tạp thường đánh giá dựa trên thời gian chạy và bộ nhớ sử dụng của thuật toán.
Dựa vào tính chất này, có thể chia thuật toán sắp xếp thành 3 loại:
Độ phức tạp tốt O(n log n): Heap sort, Merge sort, IntroSort
Độ phức tạp trung bình O( ): Bitonic sorter, Sorting network .
Độ phức tạp xấu O ( ): Bubble sort, Insertion sort, Selection sort
Một số thuật toán có thể đạt độ phức tạp O(n), nhưng điều này chỉ xảy ra với một số loại dữ liệu đầu vào và trong những điều kiện phần cứng cụ thể Do đó, chúng ta cần phân loại dựa trên độ phức tạp trung bình của các thuật toán.
1.3.2 Phân loại dựa theo có phải là một phương pháp so sánh hay không:
Thuật toán được gọi là có sử dụng phương pháp so sánh nếu chúng chỉ sử dụng toán tử so sánh để kiểm tra giữa hai phần tử.
Sắp xếp so sánh: Bubble Sort, Quicksort, Tree sort, Timsort, Shell sort
Sắp xếp không so sánh: Counting sort, Flashsort, Bucke tsort
1.3.3 Phân loại dựa theo khả năng thích ứng:
Khả năng thích ứng của thuật toán phụ thuộc vào việc dữ liệu đầu vào có ảnh hưởng đến nó hay không Tốc độ giải thuật có thể thay đổi tùy theo từng loại dữ liệu đầu vào Đặc điểm này giúp phân loại các thuật toán sắp xếp một cách hiệu quả.
Sắp xếp thích ứng: Merge sort, Heapsort, Intro sort
Sắp xếp không thích ứng: Bubble sort, Quicksort,
1.3.4 Phân loại dựa theo tính ổn định của thuật toán:
Trong dãy số, các phần tử có giá trị bằng nhau sẽ giữ nguyên thứ tự tương quan sau khi sắp xếp Điều này có nghĩa là các phần tử đứng trước trong dãy ban đầu vẫn sẽ đứng trước sau khi thực hiện quá trình sắp xếp.
Sắp xếp ổn định: Bubble sort, Insertion sort
Sắp xếp không ổn định: Quicksort, Heapsort
MỘT SỐ THUẬT TOÁN THÔNG DỤNG
2.1 Thuật toán sắp xếp đổi chỗ trực tiếp – Interchange sort:
Giả sử có mảng A với n phần tử, bắt đầu từ phần tử đầu tiên, ta tìm tất cả các nghịch thế chứa phần tử này và triệt tiêu chúng bằng cách đổi chỗ với phần tử tương ứng trong cặp nghịch thế Sau lần duyệt đầu tiên, phần tử nhỏ nhất (hoặc lớn nhất) được đưa về đầu mảng, tiếp tục duyệt từ phần tử ở vị trí thứ 2 trong lần sắp xếp tiếp theo Quá trình này lặp lại cho các phần tử còn lại, và sau khi xử lý với phần tử thứ n-1, ta sẽ có một dãy đã được sắp xếp hoàn chỉnh.
Input: Mảng số nguyên A có n phần tử chưa được sắp xếp
Output: Mảng A đã được sắp xếp ( tăng or giảm dần )
Bước 1: Khởi tạo biến i với: i = 0; //phần tử đầu tiên của dãy
Bước 2: Khởi tạo biến j với: j = i + 1; // phần tử liền phần tử thứ i
Vòng lặp với điều kiện (j < n) thì thực hiện:
+ Bước 3.1: So sánh nếu: (A[j] < A[i]) thì
Hoán vị A[j] với A[i] // TH sắp xếp tăng ( Nếu sắp xếp giảm thì giữ nguyên vị trí A[i] và A[j])
+ Bước 3.2: Tăng biến j: j = j + 1; //tăng j lên 1 để tìm nghịch thế mới
Bước 4: Tăng biến i: i = i + 1; //tăng i lên 1 để xét phần tử tiếp theo
So sánh (i < n - 1) thì: Quay lại Bước 2.
Ngược lại: Hết dãy, Dừng //Đã sắp xếp xong
Hình 2.1 Lưu đồ thuật toán sắp xếp đổi chỗ trực tiếp InterChange Sort
2.1.3 Cài đặt thuật toán Interchange sort: void InterchangeSort-tang(int a[], int n)
{ for (int i = 0; i < n-1; i++) for (int j = i+1; j < n; j++) if (a[i] > a[j])
} void InterchangeSort-giam(int a[], int n) { for (int i = 0; i < n-1; i++) for (int j = i+1; j < n; j++) if (a[i] < a[j]) { int temp = a[i]; a[i] = a[j]; a[j] = temp;
Bảng 2.1 Cài đặt thuật toán sắp xếp Đổi chỗ trực tiếp bằng C/C++
2.1.4 Đánh giá thuật toán Interchange sort:
Bảng 2.2 Bảng đánh giá độ phức tạp của thuật toán Sắp xếp đổi chỗ trực tiếp
InterchangeSort là một thuật toán rất dễ hiểu và dễ sử dụng nhưng chưa có tính hiệu quả của nó chưa cao
Số phép so sánh không đổi Độ phức tập của Interchange sort sẽ là : O(n2)
TH tốt nhất là dãy ban đầu đã có thứ tự: không phải hoán vị
TH xấu nhất là dãy ban đầu có thứ tự ngược : số lần hoán vị là n(n-1)/2
2.2 Thuận toán sắp xếp chọn trực tiếp – Selection sort:
Thuật toán selection sort là phương pháp sắp xếp bằng cách tìm kiếm phần tử có giá trị nhỏ nhất trong danh sách Đối với một mảng A gồm n phần tử, thuật toán sẽ chọn phần tử nhỏ nhất (hoặc lớn nhất) trong số n phần tử ban đầu và đưa nó về vị trí đầu tiên của mảng Sau đó, mảng còn lại sẽ có (n - 1) phần tử, và quy trình sẽ lặp lại từ phần tử thứ hai, tiếp tục chọn phần tử nhỏ nhất (hoặc lớn nhất) và đưa về đầu dãy Khi chỉ còn một phần tử, mảng A sẽ được sắp xếp theo thứ tự tăng dần (hoặc giảm dần).
Nói ngắn ngọn thì Selection sort chinh là thực hiện lần lượt n-1 lần việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy
Input: Mảng số nguyên A có n phần tử chưa được sắp xếp
Output: Mảng A đã được sắp xếp tăng (giảm)dần
Bước 1: Khởi tạo biến i với: i = 0;
Bước 2: Tìm phần tử A[min] nhỏ nhất trong dãy hiện hành từ A[i] đến A[n - 1].
+ Bước 2.1: Gán biến min = i; //Giả sử phần tử A[i] có GTNN
+ Bước 2.2: Tìm giá trị nhỏ nhất trong đoạn [i + 1, n - 1].
Vòng lặp với điều kiện (j < n - 1) thì thực hiện:
So sánh (A[j] < A[min]) thì gán min = j; //vị trí min mới.
Bước 3: Hoán vị hai phần tử: A[min] và A[i]
Tăng giá trị biến i: i ++; Quay lại Bước 2.
Ngược lại: Hết dãy, Dừng //Đã sắp xếp xong
Hình 2.2 Lưu đồ thuật toán sắp xếp đổi chỗ chọn trực tiếp Selection Sort
2.2.3 Cài đặt thuật toán Selection sort: void Selectionsort-tang(int a[], int n)
{ min=i; for(int j=i +1; j= right) return; x = a[(left+right)/2]; // chọn phần tử ở giữa làm chốt i = left; j = right; while(i < j)
Cách 2: Sử dụng phần tử cuối cùng làm chốt: void Quicksort(int a[], int low, int high)
{ if(low >= high) // Nếu danh sách có hai phần tử return; // Kết thúc else
{ int pivot = a[high]; int right = high-1, left = low; while(left x): Tìm x trong dãy con a[Left]…a[Mid – 1], gắn giá trị Right
+ Nếu (a[Mid] < x): Tìm x trong dãy con a[Mid+1]…a[Right], gắn giá tr Left Mid + 1;
+ Nếu (Left A[0] Tiến hành gán Max cho A[1] Tiếp tục tìm giá trị A[j] > Max
Hình 3.13 j đến cuối mảng và không tìm được giá trị A[j] > Max Tiến hành đổi chỗ
Hình 3.14 Tiếp tục lặp lại cho đến khi hoàn thành
Hình 3.15 Hoàn thành sắp xếp chọn trực tiếp
3.3.4 Mô phỏng thuật toán Sắp xếp nhanh (Quick Sort):
Hình 3.16 Giao diện khi khởi tạo chức năng Sắp xếp nhanh
Hình 3.17 Hoán vị hai phần tử thoả điều kiện thuật toán
Hình 3.18 Phân hoạch đoạn bên trái
Hình 3.20 Tiến hành phân hoạch đoạn bên phải
3.3.5 Mô phỏng thuật toán Tìm kiếm tuyến tính (Linear Search):
Hình 3.21 Mô phỏng tìm kiếm tuyến tính và nhập số cần tìm X = 50
*Lưu ý: Nếu không nhập giá trị cần tìm sẽ hiện ra thông báo Cần phải giá trị cần tìm thì thuật toán mới chạy!
Hình 3.22 Không có phần tử X = 50 và thông báo
Hình 3.23 Khởi tạo dãy số khác và tìm X = 28 thành công
3.3.6 Mô phỏng thuật toán Tìm kiến nhị phân (Binary Search):
Hình 3.24 Khởi tạo dãy số và tiến hành sắp xếp trước khi tìm kiếm
Hình 3.26 Do X = 28 < Mid = 53 nên tiến hành phân hoạch đoạn bên trái
Hình 3.27 Không tìm thấy giá trị X = 28 trong mảng
Hình 3.28 Do X = 78 > mid = 53 nên tiến hành phân hoạch đoạn bên phải
Hình 3.29 Đã tìm thấy X = 78 và kết thúc thuật toán
Trong 8 tuần thực hiện đề tài, tôi đã nắm vững kiến thức lập trình cơ sở và tư duy thuật toán, đồng thời làm chủ một số thuật toán tìm kiếm và sắp xếp phổ biến Bên cạnh đó, tôi cũng đã củng cố kiến thức về lập trình hướng đối tượng với C# và Windows Form.
Xây dựng được một chương trình mô phòng thuật toán đơn giản Chương trình có thể giúp người xem hiểu về cách thực hoạt động của thuật toán.
Chúng em nhận thức rằng kiến thức của mình còn hạn chế và chưa đầy đủ, nhưng chúng em đã nỗ lực để cải thiện và mở rộng hiểu biết thông qua việc nghiên cứu, mặc dù vẫn còn nhiều thiếu sót.
Trong tương lai, chúng em dự định hoàn thiện chương trình với đầy đủ các thuật toán sắp xếp và các thuật toán cơ bản, nhằm giúp người học lập trình có cái nhìn trực quan về các thuật toán Chúng em rất mong nhận được sự góp ý từ thầy cô và các bạn để có thể cải thiện hơn nữa.