intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Sắp xếp chèn - InsertionSort

Chia sẻ: Nguyễn Thị Phương Phương | Ngày: | Loại File: PPT | Số trang:13

Thêm vào BST
Báo xấu
84
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Một dãy ngẫu nhiên có d = O(n2) các nghịch thế. Do đó trung bình của Insert sort Q( d + n ). Insertion sort sẽ chạy trong Q( n ) thời gian nếu: Các phần tử nằm sai vị trí quá xa thì nhỏ, và… Những phần tử còn lại hầu như ở gần vị trí đúng của nó.

Chủ đề:

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

Lưu

Nội dung Text: Sắp xếp chèn - InsertionSort

  1. Insertion Sort • Nội dung – Giải thuật – Ví dụ minh họa – Phân tích thời gian chạy • Trường hợp xấu nhất • Trung bình • Tốt nhất
  2. Insertion Sort • Lưu ý quan sát sau đây: – Dãy có 1 phần tử thì được sắp. – Tổng quát : nếu ta có dãy đã được sắp có k phần tử, ta có thể chèn một phần tử mới để tạo ra một dãy được sắp có kích thước k + 1
  3. Insertion Sort Ví dụ • Hãy xem dãy được sắp sau đây chứa k = 8 phần tử • Giả sử ta muốn chèn phần tử 14 vào trong dãy sao cho dãy vẫn được sắp. • Bắt đầu đi từ cuối dãy, nếu phần tử mang giá trị lớn hơn 14, copy nó sang phải.
  4. Insertion Sort Khi tìm được phần tử có giá trị bé hơn 14, chèn 14 vào vị trí bỏ trống.
  5. Giải thuật Insertion Sort • Với dãy bất kỳ: – Xem phần tử đầu tiên là một dãy được sắp có kích thước k = 1. • Sau đó, giả sử ta đã có dãy được sắp có kích thước k. – Chèn phần tử thứ (k + 1) trong dãy chưa được sắp vào trong dãy trên. – Dãy được sắp bây giờ có kích thước k + 1
  6. Insertion Sort Giải thuật Insert sort với dãy có n phần tử Với mỗi phần tử (thứ i ) trong dãy, bắt đầu từ phần tử thứ hai …. Tìm ngược về đầu dãy, xuất phát j = i -1 Nếu phần tử đang xét thứ j lón hơn phần tử th ứ i. Dịch chuyển phần tử thứ j đến vị trí j+1 Ngược lại, đặt phần tử thứ i vào vị trí j+1
  7. Insertion Sort : Cài đặt void Insertion( int array[], int const n ) { for ( int i = 1; i < n; ++i ) { int tmp = array[i]; int j= i-1; while(j>=0 && tmp < array[j]) { array[j+1] = array[j]; j--; } array[j+1]= tmp; } }
  8. Insertion Sort: Phân tích Điều kiện này thực hiện n lần void Insertion( int array[], int const n ) { for ( int i = 1; i < n; ++i ) { Những phép gán này đươc thưc hiện trong từng bước int tmp = array[i]; lặp int j= i-1; while(j>=0 && tmp < array[j]) { array[j+1] = array[j]; j--; } array[j+1]= tmp; } }
  9. Phân tích void Insertion( int array[], int const n ) { for ( int i = 1; i < n; ++i ) { Phép so sánh đươc thưc hiện i lần trong từng bước int tmp = array[i]; lặp int j= i-1; while(j>=0 && tmp < array[j]) { array[j+1] = array[j]; j--; } Phép gán đươc thưc hiện có thể i lần trong từng bước array[j+1]= tmp; lặp } }
  10. Insertion Sort : Phân tích for ( int i = 1; i < n; ++i ) int j = i-1; while(j >=0 && tmp < array[j]) array[j+1] = array[j]; • Thời gian thực hiện giải thuật là Θ(n2) do: n −1 (n − 1)n ∑ i =1 i= 2 = Θ(n 2 ) • Thực tế, giải thuật có thể chạy nhanh hơn: – Nếu điều kiện thất bại, vòng while sẽ thoát sớm
  11. Phân tích • Nếu ta biết phép so sánh (tmp < array[j] ) để thực hiện phép gán array[j+1] = array[j] chạy như thế nào ta sẽ biết độ phức tạp của nó. • Nếu phép gán xảy ra d lần, điều kiện kiểm tra là (d+n) lần (do có n phần tử cần kiểm tra). • Tuy nhiên mỗi phép gán tương đương với sự hoán đổi 2 phần tử kề nhau. • Mỗi một phép hoán đổi là sửa lại một bộ có th ứ t ự ngược. • Vì thế d chính là số các nghịch thế trong dãy ban đầu . • Vì vậy thời gian chạy của insertsort sẽ là : Θ( d + n ).
  12. Insertion Sort Kết luận • Một dãy ngẫu nhiên có d = O(n2) các nghịch thế. Do đó trung bình của Insert sort Θ( d + n ). • Insertion sort sẽ chạy trong Θ( n ) thời gian nếu: – Các phần tử nằm sai vị trí quá xa thì nhỏ, và… – Những phần tử còn lại hầu như ở gần vị trí đúng của nó. • Tổng quát, giải thuật không có ích khi dãy ban đầu là lớn – Sắp xếp dãy có kích thước 223 ≈ 8 000 000 mất thời gian xấp xỉ một ngày – Tăng kích thước gấp đôi thời gian tăng gấp 4
  13. Insertion Sort Kết luận • Bảng sau tổng kết thời gian thực hiện của giải thuật Insertion Sort Truờng hợp Run Time Ghi chú Xấu nhất O(n2) Dãy có thứ tự ngược Trung bình O(d + n) Không may, d = O(n2) Tốt nhất O(n) Rất ít cặp có thứ tự ngược...
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2