Kiến trúc máy tính - Phần 11

Chia sẻ: Lê Trung Thống | Ngày: | Loại File: PPT | Số trang:18

Thêm vào BST

Báo xấu

89
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Dãy các phần tử được sắp theo thứ tự tăng hoặc giảm dần theo một hoặc một vài thuộc tính của nó (các thuộc tính này gọi là thuộc tính khóa). Thuộc tính khóa được sắp xếp theo một hàm logic, ví dụ (

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Kiến trúc máy tính - Phần 11

Hôm nay 1. Các phương pháp sắp xếp 2. Giao bài tập lớn Sorting 1
Bài 11. Sắp xếp (Sorting) Sorting 2
Sorting Bài toán Input: Dãy các phần tử (và một thứ tự)  (Dãy các phần tử thường được lưu bằng mảng.)  Output: Dãy các phần tử được sắp theo thứ tự tăng hoặc giảm dần  theo một hoặc một vài thuộc tính của nó (các thuộc tính này gọi là thuộc tính khóa). Thuộc tính khóa được sắp xếp theo một hàm logic, ví dụ  (
Các thuật toán với thời gian chạy O(n2)  Nổibọt – Bubble sort  Chèn – Insertion sort  Chọn – Selection sort Sorting 4
Sắp xếp nổi bọt – Bubble sort Ý tưởng: Thực hiện chuyển dần các phân tử có giá trị khóa nhỏ về đầu dẫy, các phần tử có khóa lớn về cuối dãy. Ví dụ sắp xếp dãy sau theo thứ tự tăng dần: 5 4 2 3 1 1 2 5 4 3 1 2 3 5 4 Bước 1 Bước 3 5 4 2 3 1 1 5 4 2 3 1 2 3 5 4 1 5 4 2 3 1 2 3 4 5 Bước 4 Bước 2 1 2 5 4 3 Sorting 5
Thuật toán Algorithm BubbleSort(Array A, n) Input: Mảng A có n phần tử Output: Mảng A được sắp theo thứ tự tăng dần của khóa for i ← 1 to n1 do for j ← n downto i+1 do if A[j].Key
Chứng minh thời gian chạy của thuật toán trong trường hợp xấu nhất là O(n2) ? Sorting 7
Thời gian chạy Algorithm BubbleSort(Array A, n) Input: Mảng A có n phần tử Output: Mảng A được sắp theo thứ tự tăng dần của khóa for i ← 1 to n1 do n+2 for j ← n downto i+1 do ni if A[j].Key
Ví dụ: Mô tả quá trình sắp xếp của dãy số 12 43 11 34 23 43 Sorting 9
Sắp xếp chọn Selection sort 5 4 2 3 1 • Ý tưởng: Chọn phần tử có khóa 1 4 2 3 5 Bước 1 nhỏ nhất trong các phần tử còn 1 2 4 3 5 Bước 2 lại chuyển nó về đầu và loại bỏ Bước 3 1 2 3 4 5 nó khỏi dãy. 1 2 3 4 5 • Ví dụ sắp xếp Bước 4 dãy sau theo thứ 1 2 3 4 5 tự tăng dần: 5 4 2 3 1 Sorting 10
Thuật toán Algorithm SelectionSort(Array A, n) Input: Mảng A có n phần tử Output: Mảng A được sắp theo thứ tự tăng dần của khóa for i ← 1 to n1 do posmin ← i ; for j ← i+1 to n do if A[posmin].Key > A[j].Key then posmin ← j ; if posmin ≠ i then swap (A[i], A[posmin]); Sorting 11
Chứng minh thời gian chạy của thuật toán trong trường hợp xấu nhất là O(n2) ? Sorting 12
Thời gian chạy for i ← 1 to n1 do n+2 posmin ← i ; 1 for j ← i+1 to n do ni 2 if A[posmin].Key
Ví dụ: Mô tả quá trình sắp xếp của dãy số 12 43 11 34 23 435 Sorting 14
Sắp xếp chèn – Insertion sort 5 4 2 3 1 Ý tưởng: Lấy phần tử thứ A[j] chèn vào dãy 4 5 2 3 1 gồm các phần tử từ A[1]..A[j-1] sao cho ta được dãy A[1]..A[j] 2 4 5 3 1 được sắp. Trong đó dãy A[1]..A[j-1] là dãy đã 2 3 4 5 1 được sắp. 1 2 3 4 5 Ví dụ sắp xếp dãy sau theo thứ tự 1 2 3 4 5 tăng dần: 5 4 2 3 1 Sorting 15
Thuật toán Algorithm InsertionSort(Array A, n) Input: Mảng A có n phần tử Output: Mảng A được sắp theo thứ tự tăng dần của khóa for i ← 2 to n do j ← i1; x ← A[i]; while (A[j].Key>x.Key) and (j>0) do A[j+1] ← A[j]; j ← j1; A[j+1] ← x; Sorting 16
Chứng minh thời gian chạy của thuật toán trong trường hợp xấu nhất là O(n2) ? Sorting 17
Ví dụ: Mô tả quá trình sắp xếp của dãy số 12 43 11 34 23 43 12 435 Sorting 18