ݺߣ

ݺߣShare a Scribd company logo

Bài t#u1eadp bài 3

•Download as DOC, PDF•
•
Hồ Lợi
Hồ Lợi
1 of 1
Download to read offline
Bài tập bài 3 Bài 1: Sắp xếp mảng gồm 12 phần tử có khóa là các số nguyên : 5, 15, 12, 2, 10, 12, 9, 1, 9, 3, 2, 3 bằng cách sử dụng: a) Sắp xếp chọn (selection). b) Sắp xếp xen (insert). c) Sắp xếp đổi chỗ trực tiếp (interchange) d) Sắp xếp nổi bọt. e) Sắp xếp trộn (Merge) f) QuickSort. g) HeapSort h) Bin Sort(radix Sort). Bài 2: Có một biến thể của sắp xếp chọn như sau: Trong bước thứ i ta chọn một phần tử có khóa nhỏ nhất và một phần tử có khóa lớn nhất trong a[i]...a[n-i+1] và hóan đổi phần tử nhỏ nhất cho a[i] và phần tử lớn nhất cho a[n-i+1]. Hãy viết thủ tục sắp xếp chọn theo giải thuật này và tính thời gian thực hiện. Bài 3: Viết thủ tục sắp xếp trộn (xem giải thuật thô trong sách tham khảo). Bài 4: Có một biến thể của QuickSort như sau: Chọn chốt là khóa của phần tử nhỏ nhất trong hai phần tử có khóa khác nhau đầu tiên. Mảng con bên trái gồm các phần tử có khóa nhỏ hơn hoặc bằng chốt, mảng con bên phải gồm các phần tử có khóa lớn hơn chốt. Hãy viết lại các thủ tục cần thiết cho biến thể này. Bài 5: Một biến thể khác của QuickSort là chọn khóa của phần tử đầu tiên làm chốt. Hãy viết lại các thủ tục cần thiết cho biến thể này. Bài 6: Hãy viết lại thủ tục PushDown trong HeapSort để có thể sắp xếp theo thứ tự tăng.

More Related Content

Bài t#u1eadp bài 3

  • 1. Bài tập bài 3 Bài 1: Sắp xếp mảng gồm 12 phần tử có khóa là các số nguyên : 5, 15, 12, 2, 10, 12, 9, 1, 9, 3, 2, 3 bằng cách sử dụng: a) Sắp xếp chọn (selection). b) Sắp xếp xen (insert). c) Sắp xếp đổi chỗ trực tiếp (interchange) d) Sắp xếp nổi bọt. e) Sắp xếp trộn (Merge) f) QuickSort. g) HeapSort h) Bin Sort(radix Sort). Bài 2: Có một biến thể của sắp xếp chọn như sau: Trong bước thứ i ta chọn một phần tử có khóa nhỏ nhất và một phần tử có khóa lớn nhất trong a[i]...a[n-i+1] và hóan đổi phần tử nhỏ nhất cho a[i] và phần tử lớn nhất cho a[n-i+1]. Hãy viết thủ tục sắp xếp chọn theo giải thuật này và tính thời gian thực hiện. Bài 3: Viết thủ tục sắp xếp trộn (xem giải thuật thô trong sách tham khảo). Bài 4: Có một biến thể của QuickSort như sau: Chọn chốt là khóa của phần tử nhỏ nhất trong hai phần tử có khóa khác nhau đầu tiên. Mảng con bên trái gồm các phần tử có khóa nhỏ hơn hoặc bằng chốt, mảng con bên phải gồm các phần tử có khóa lớn hơn chốt. Hãy viết lại các thủ tục cần thiết cho biến thể này. Bài 5: Một biến thể khác của QuickSort là chọn khóa của phần tử đầu tiên làm chốt. Hãy viết lại các thủ tục cần thiết cho biến thể này. Bài 6: Hãy viết lại thủ tục PushDown trong HeapSort để có thể sắp xếp theo thứ tự tăng.