Thuật toán trong lập trình - Phần 2: Tìm kiếm và Sắp xếp
Sau khi đã nắm được các khái niệm cơ bản về thuật toán, chúng ta hãy cùng bắt tay ngay vào việc tìm hiểu và thực hành thôi nào! Trong bài viết này, chúng ta sẽ cùng nhau tìm hiểu về cách hoạt động của một vài thuật toán tìm kiếm, thuật toán sắp xếp cơ bản nhất nhé!
Danh sách các bài viết:
Các thuật toán Tìm kiếm
Tìm kiếm tuần tự (Linear Search)
Đây là một trong những thuật toán tìm kiếm cơ bản nhất với độ phức tạp thời gian là O(n) cho trường hợp xấu nhất và O(1) cho trường hợp tốt nhất.
Định nghĩa: Trong khoa học máy tính, tìm kiếm tuyến tính hoặc tìm kiếm tuần tự là một phương pháp để tìm một phần tử trong danh sách bằng cách tuần tự kiểm tra từng phần tử cho đến khi tìm thấy hoặc đã tìm qua toàn bộ danh sách.
Cùng tìm hiểu thuật toán này bằng một ví dụ thực tế như sau: giả sử chúng ta có 7 người với chiều cao khác nhau đứng thành một hàng theo thứ tự ngẫu nhiên. Đặt chiều cao của những người đó là 180, 140, 170, 160, 190, 130, 150 (cm) và đặt tên cho những người đó là P1, P2 ,… .. P7 tương ứng. Muốn tìm một người có chiều cao 160 cm với phương pháp tìm kiếm tuyến tính, chúng tai bắt đầu bằng cách đi qua từng người và hỏi mọi người chiều cao cá nhân của họ và nếu nó bằng 160 cm, chúng ta sẽ ghi lại lại vị trí hoặc tên của người đó, nếu không có ai cao 160cm thì chúng ta sẽ ghi nhận không có ai. Trong ví dụ này, chúng ta sẽ hỏi từng người về chiều cao của họ và kết quả P4 là người có chiều cao 160 cm.
Dưới đây là mã giả cho tìm kiếm tuyến tính và bạn hãy thử triển khai nó bằng ngôn ngữ lập trình ưa thích của mình.
Bước 1. Nhập vào một mảng và số x cần tìm kiếm.
Bước 2. Duyệt qua từng phần tử trong mảng và so sánh với số x.
Bước 3. Nếu phần tử đó bằng x thì trả về vị trí của phần đó đó.
Bước 4. Nếu không tìm thấy phần tử nào bằng với x trong mảng thì trả về -1.
Tìm kiếm nhị phân (Binary Search)
Tìm kiếm nhị phân là một thuật toán tìm kiếm để tìm vị trí của một phần tử trong mảng đã được sắp xếp. Tóm lại, thuật toán tìm kiếm này tận dụng lợi thế mảng đã được sắp xếp bằng cách bỏ qua một nửa số phần tử sau một lần so sánh.
Định nghĩa: Trong khoa học máy tính, tìm kiếm nhị phân, còn được gọi là tìm kiếm nửa khoảng, tìm kiếm logarit, là một thuật toán tìm kiếm để tìm vị trí của giá trị đích trong một mảng được sắp xếp. Tìm kiếm nhị phân so sánh giá trị cần tìm với phần tử giữa của mảng. Nếu chúng không bằng nhau, một nửa trong đó sẽ bị loại bỏ và tiếp tục tìm kiếm trên nửa còn lại, một lần nữa lấy phần tử ở giữa để so sánh với giá trị cần tìm và lặp lại điều này cho đến khi tìm thấy giá trị đó. Nếu kết thúc tìm kiếm với một nửa còn lại rỗng, thì không tìm thấy giá trị đó trong mảng.
Bây giờ chúng ta sẽ tìm hiểu thuật toán Tìm kiếm nhị phân với ví dụ mà chúng ta đã sử dụng trong Tìm kiếm tuyến tính nhé!
Không giống như tìm kiếm tuyến tính, tìm kiến nhị phân yêu cầu các phần tử trong mảng phải được sắp xếp trước. Đây là điều kiện tiên quyết để thực hiện tìm kiếm nhị phân.
Bước 1: Chúng ta hãy xem xét những người đang đứng trong một hàng có chiều cao như sau
Bước 2: Giả sử chúng ta đang tìm người có chiều cao x = 160cm
Bước 3: Đặt 2 con trỏ low và high ở vị trí đầu tiên và cuối cùng của mảng
Bước 4: Tìm phần ở giữa của mảng bằng: Arr[(low+high)/2] = 160
Bước 5: Nếu x bằng với giá trị cần tìm thì trả về vị trí mid đó. Nếu không thì so sánh phần tử mid với giá trị cần tìm.
Bước 6: Nếu x lớn hơn phần tử mid thì ta tiếp tục so sánh x với các phần tử bên phải của phần tử mid. Điều này được thực hiện bằng cách đặt low = mid + 1.
Bước 7: Nếu x nhỏ hơn phần tử mid thì ta tiếp tục so sánh x với các phần tử bên trái của phần tử mid. Điều này được thực hiện bằng cách đặt high = mid – 1
Bước 8: Lặp lại cho đến khi low bằng high thì dừng thuật toán.
Ở trong ví dụ này, chúng ta sẽ tìm thấy người có chiều cao 160cm ở vị trí thứ 4.
Kỹ thuật tìm kiếm này nhanh hơn, dễ thực hiện hơn, không cần thêm bộ nhớ và giảm độ phức tạp về thời gian của chương trình ở mức độ lớn hơn. Độ phức tạp thời gian cho trường hợp xấu nhất là O (logn).
Dưới đây là mã giả cho thuật toán này, hãy thử triển khai thuật toán này bằng ngôn ngữ ưa thích của bạn ngay nhé!
Bước 1. Nhập phần tử X mà chúng ta cần tìm kiếm và mảng / danh sách đã được sắp xếp.
Bước 2. So sánh X với phần tử ở giữa trong mảng.
Bước 3. Nếu X bằng với phần tử ở giữa, chúng ta trả về vị trí chính giữa đó.
Bước 4. Nếu X lớn hơn phần tử ở giữa, thì X chỉ có thể nằm trong nửa mảng con bên phải sau phần tử ở giữa, sau đó ta áp dụng lại thuật toán cho nửa bên phải.
Bước 5. Nếu X nhỏ hơn phần tử ở giữa, thì X phải nằm ở nửa bên trái, điều này là do mảng đã được sắp xếp. Sau đó ta áp dụng thuật toán cho nửa bên trái.
Các thuật toán sắp xếp
Sắp xếp là các thao tác hoán vị của một danh sách các phần tử sao cho các phần tử có thứ tự tăng hoặc giảm. Có nhiều thuật toán sắp xếp khác nhau với sự khác biệt nằm ở độ phức tạp và thời gian thực hiện. Chúng ta sẽ tìm hiểu các thuật toán cơ bản sau:
Selection sort
Bubble sort
Insertion sort
Selection sort
Định nghĩa: Sắp xếp chọn là một thuật toán chọn phần tử nhỏ nhất (lớn nhất) từ danh sách chưa được sắp xếp trong mỗi lần lặp và đặt phần tử đó vào đầu danh sách chưa được sắp xếp. Thuật toán hoạt động như hình dưới đây.
Bây giờ sẽ là mô tả về cách hoạt động bằng cách chia nhỏ ra để dễ hiểu hơn nhé!
Chúng ta bắt đầu bằng cách giả định rằng thanh đầu tiên (3) trong biểu đồ có chiều cao nhỏ nhất, sau đó chúng ta duyệt qua mảng, so sánh nó với từng thanh và nếu chiều cao của một thanh nào đó nhỏ hơn, chúng ta sẽ đặt nó thành thanh có chiều cao nhỏ nhất mới và cuối cùng, chúng ta sẽ có thanh có chiều cao nhỏ nhất (2). Sau đó, chúng ta sẽ hoán đổi với thanh đầu tiên, dẫn đến thanh nhỏ nhất bây giờ nằm ở vị trí đầu tiên trong biểu đồ.
Sau khi xong vị trí đầu tiên, chúng ta sẽ tiếp tục với thanh thứ hai (44). Giả sử đó là thanh nhỏ nhất cho lần lặp tiếp theo vì thanh đầu tiên đã được sắp xếp và ở đúng vị trí. Chúng ta sẽ lặp lại các quy trình. Sau n-1 lần lặp để sắp xếp đầy đủ biểu đồ, trong đó n là số phần tử/thanh. Mã giả được cung cấp bên dưới, hãy cố gắng triển khai thuật toán với một ngôn ngữ lập trình ưa thích của bạn nhé!
Bước 1 - Đặt MIN ở vị trí 0
Bước 2 - Tìm kiếm phần tử nhỏ nhất (lớn nhất) trong danh sách
Bước 3 - Hoán đổi giá trị đó tại vị trí MIN
Bước 4 - Tăng MIN để trỏ đến phần tử tiếp theo
Bước 5 - Lặp lại cho đến khi danh sách được sắp xếp.
Bubble sort
Định nghĩa: Sắp xếp bong bóng, còn được gọi là sắp xếp chìm, là một thuật toán sắp xếp cơ bản lặp lại qua một danh sách, so sánh các phần tử lân cận và hoán đổi chúng nếu chúng không theo thứ tự. Danh sách được lặp đi lặp lại nhiều lần cho đến khi nó hoàn thành sắp xếp. Phương pháp sắp xếp này được đặt tên theo cách mà các thành phần nhỏ hơn hoặc lớn hơn "nổi lên" đầu danh sách. Phương pháp này thì đơn giản và hoạt động kém hiệu quả trong các tình huống thực tế, chủ yếu được sử dụng như một phương pháp hỗ trợ giảng dạy.
Cách hoạt động của thuật toán Bubble Sort
Chúng ta bắt đầu bằng cách duyệt qua danh sách và so sánh mọi thành viên lân cận, hoán đổi chúng nếu chúng không theo thứ tự và khi kết thúc lần lặp đầu tiên, chúng ta sẽ có phần tử lớn nhất nằm ở cuối.
Đối với những lần lặp sau, chúng ta sẽ bắt đầu với phần tử đầu tiên và lặp lại quy trình so sánh và hoán đổi, nhưng lần này chúng ta sẽ chỉ lặp đến vị trí của phần tử kế cuối vì phần tử cuối cùng đã được sắp xếp và ở đúng vị trí. Thế nên, để sắp xếp một danh sách, chúng ta phải thực hiện n-1 lần, trong đó n là đại diện cho số phần tử trong danh sách.
Dưới đây là mã giả tương tự và hãy triển khai mã này bằng ngôn ngữ lập trình ưa thích của bạn nhé!
Bước 1. Trong lần lặp đầu tiên, bắt đầu bằng cách so sánh phần tử thứ nhất và thứ hai và hoán đổi nếu phần tử thứ nhất lớn hơn. Sau đó, làm tương tự cho phần tử thứ 2 và thứ 3. Vào cuối lần lặp, bạn sẽ nhận được phần tử lớn nhất ở cuối danh sách.
Bước 2. Bây giờ làm tương tự trong các lần lặp tiếp theo.
Bước 3. Thực hiện điều này (số phần tử - 1) lần.
Bước 4. Bạn sẽ nhận được danh sách được sắp xếp.
Insertion sort
Định nghĩa: Sắp xếp chèn là một thuật toán sắp xếp đơn giản, mảng sẽ được chia thành một phần đã được sắp xếp và một phần chưa được sắp xếp, các giá trị từ phần chưa được sắp xếp được chọn và đặt ở vị trí chính xác trong phần được sắp xếp. Thuật toàn này kém hiệu quả khi sắp xếp trên các danh sách lớn nếu so sánh với các thuật toán nâng cao như quicksort, heapsort hoặc merge sort. Tuy nhiên, nó vẫn có một vài ưu điểm nhất định. Thuật toán xây dựng một mảng được sắp xếp một phần tử tại một thời điểm, sắp xếp chèn có độ phức tạp trung bình và trường hợp xấu nhất đều là O(n²) phép so sánh và O(n) phép hoán vị.
Dưới đây là chi tiết về cách hoạt động của thuật toán Sắp xếp chèn.
Insertion Sort hoạt động theo cách tương tự như cách chúng ta sắp xếp các quân bài trên tay trong một ván bài. Giả sử các số trong hình trên nằm trên tay phải, chúng ta sẽ bắt đầu với thẻ bài ngoài cùng bên trái và cầm nó bằng tay trái. Có thể nói danh sách bên tay trái chính là danh sách đã được sắp xếp vì chỉ có một thẻ duy nhất. Sau đó ta cũng lại chọn thẻ ngoài cùng bên trái từ tay phải và so sánh với thẻ duy nhất ở bên trái, sau khi so sánh, chúng ta cầm nó bên tay trái theo thứ tự. Tiếp theo, chúng ta sẽ lấy thẻ ngoài cùng bên trái từ tay phải và so sánh nó với tất cả các thẻ khác ở tay trái, đặt nó ở vị trí phù hợp, cho đến khi chúng ta có ba thẻ theo thứ tự được sắp xếp ở bên tay trái và chúng ta sẽ lặp lại các quy trình này cho đến khi không còn quân bài nào trong tay phải. Đây là mã giả cho sắp xếp chèn, cùng triển khai mã giả này bằng ngôn ngữ lập trình ưa thích của bạn nhé.
Bước 1: Duyệt qua mảng từ arr [1] đến arr [n].
Bước 2: So sánh phần tử hiện tại (khóa) với phần tử đứng trước nó.
Bước 3: Nếu nó nhỏ hơn, phần tử đứng trước phải nhường chỗ cho phần tử hiện tại (khóa).
Bước 4: Lặp lại so sánh cho đến khi phần tử hiện tại lớn hơn phần tử đứng trước.
Trong bài tiếp theo, chúng ta sẽ tìm hiểu về hai thuật toán hấp dẫn hơn là Sliding Window và Two Pointer. Đó cũng là phần cuối cùng của series này. Cùng đón xem nhé!