- .:: HVAOnline ::.

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<Record>::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] ;

                                     position -- ;

                         } while (position > 0 && entry[position-1]> current );

                         entry[position] = current ;

                 }

       }

 }