Sắp xếp theo kiểu : insertion sort

Chia sẻ: Đặng Quang Hưng | Ngày: | Loại File: DOC | Số trang:2

0
266
lượt xem
42
download

Sắp xếp theo kiểu : insertion sort

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

Ý nghĩa của insertion sort là lấy một phần tử của mảng ra và insert vào vị trí thích hợp trong mảng

Chủ đề:
Lưu

Nội dung Text: Sắp xếp theo kiểu : insertion sort

  1. insertion sort VD : A = { 5 8 6 3 10 } Insertion sort làm như sau : Chia mảng A làm 2 phần sorted và unsorted Ban đầu sorted là B = { 5 } Unsorted là C = { 8 6 3 10 } Lần làm thứ nhất : Lấy phần tử đầu tiên của C là 8 ra---> C = { 6 3 10 } Tìm vị trí của số 8 trong mảng B ---> B = { 5 8 } Lần làm thứ hai : Lấy phần tử đầu tiên của C là 6 ra---> C = { 3 10 } Tìm vị trí của số 6 trong mảng B ---> B = { 5 6 8 } Lần làm thứ ba : Lấy phần tử đầu tiên của C là 3 ra---> C = { 10 } Tìm vị trí của số 3 trong mảng B ---> B = { 3 5 6 8 } Lần làm thứ tư : Lấy phần tử đầu tiên của C là 10 ra---> C = { } Tìm vị trí của số 10 trong mảng B ---> B = { 3 5 6 8 10} Kết thúc thuật toán Ý nghĩa của insertion sort là lấy một phần tử của mảng ra và insert vào vị trí thích hợp trong mảng Giải thuật Code: void Sortable_List::insertion_sort() // phien bản nay list được hien thưc thông qua mảng chứ kg phải con trỏ { int first_unsorted ; int position ; Record current ; for( first_unsorted = 1 ; first_unsorted < count ; first_unsorted ++) { if(entry[first_unsorted] < entry[first_unsorted-1]) { position = first_unsorted ; current = entry[first_unsorted] ; do { entry[position] = entry [ position -1] ;
  2. position -- ; } while (position > 0 && entry[position-1]> current ); entry[position] = current ; } } }
Đồng bộ tài khoản