- .:: HVAOnline ::.

Selection Sort

Nguyên tắc :
Chia mảng cần sắp thành 2 phần
Phần đã được sắp và phần chưa được sắp :
<A = phần được sắp> < B= phần chưa được sắp>
C = phần tử đầu tiên của B

Bước 1 : Tìm trong B phần tử lớn nhất max_key
Bước 2 : swap C và max_key ( hoán đổi vị trí )
Bước 3 : Bỏ max_key vào A . Khi này A mới = { A cũ , max_key } .
Quay lại bước 1

Gọi Sortable_List là list được hiện thực bằng mảng
Code:

void Sortable_List<Record>::selectionsort() 

         {

                     for ( int position = count -1 ; position > 0 ; position -- ) 

                     {

                               int max = max_key(0,position) ; // tìm key lớn nhất 

                               swap (  max , position ) ; 

                     }

         }

         

         void Sortable_List<Record>::swap ( int low , int high)

         {

                     Record temp ;

                     temp = entry[low] ;

                     entry[low] = entry[high] ;

                     entry[high] = temp ;

         }

         

         .... max_key(int low , int high) 

         {

                 int largest , current ;

                 largest = low ;

                 for ( current = low +1 ; current <= high ; current ++ )

                         if ( entry[largest] < entry[current] )

                         {

                                     largest = current ;

                           }

                   return largest ;

           }