Dưới đây là một vài ví dụ về việc áp dụng các thuật toán tìm kiếm và sắp xếp cơ bản vào mảng cấu trúc các bạn có thể tham khảo.
Thuật toán tìm kiếm:
1. Tìm kiếm tuyến tính (Linear Search):
Ý tưởng:
- Lần lượt so sánh giá trị x với các phần tử trong mảng arr[] bắt đầu từ phần tử đầu tiên
- Bài toán kết thúc khi tìm được phần tử có gia trị bằng x hoặc khi hết mảng
2. Tìm kiếm nhị phân (Binary Search):
Ý tưởng:
- So sánh x với phần tử giữa dãy gọi là arr[mid]. Nếu x=arr[mid] thì tìm thấy, nếu x<arr[mid] thì nếu có x chỉ có thể ở nửa dãy trái, nếu x>arr[mid] thì x chỉ có thể ở nửa dãy phải.
Khi sử dụng BinarySeach, dãy phải được sắp xếp theo thứ tự tăng dần trước khi tìm kiếm
Thuật toán sắp xếp:
1. Selection Sort:
Ý tưởng:
- Chọn phần tử nhỏ nhất trong mảng
- Đưa phần tử này về đầu mảng
- (Lặp) Tiếp tục sắp xếp mảng từ vị trí thứ 2
2. Interchange Sort:
Ý tưởng:
- Xuất phát từ đầu dãy, tìm hết các nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ 2 phần tử trong cặp nghịch thế bằng hàm (swap) có sẵn. Và lặp lại xử lý trên với phần tử kế trong dãy.
3. Bubble Sort (Sắp xếp nổi bọt):
Ý tưởng:
- Nghịch thế
- Xuất phát từ cuối dãy, hoán vị các cặp nghịch thế kế tiếp nhau
- Lặp lại cho đến khi mảng được sắp xếp xong
4. Shaker Sort:
Ý tưởng:
- Xuất phát từ cuối dãy
- Xét 2 phần tử gần nhau, nếu là nghịch thế thì hoán vị 2 phần tử này với mục đích đẩy phần tử nhỏ nhất về đầu dãy
- Trong mỗi lần sắp xếp sẽ thực hiện 2 lượt:
- Lượt đi: đẩy phần tử nhỏ nhất về đầu dãy
- Lượt về: đẩy phần tử lớn nhất về cuối dãy
5. Insertion Sort (Sắp xếp chèn):
Ý tưởng:
- Chia mảng cần sắp xếp thành 2 mảng con: mảng T chứa arr[0], mảng P chứa phần còn lại
- Chọn 1 phần tử arr[i] trong P, tìm vị trí thích hợp và chèn arr[i] vào mảng T
- Lặp lại cho đến khi mảng P rỗng
Tác giả: Nguyễn Thị Trà Giang (sinh viên lớp 22DTH2, khoa Công nghệ thông tin), Nguyễn Trần Đoan Thi (sinh viên lớp 22DTH1, khoa Công nghệ thông tin)
Tài liệu Kết Nối Trẻ 