PVA – Archives

Sưu tầm những bài viết hay trên internet…

Các thuật toán sắp xếp

Nguồn: HVAonline.net

Merge sort


Nguyên tắc :

VD ta có
12 13 45 32 100 34 65 10

Ta có ở trên là 8 phần tử cần được sắp xếp :
Ý tưởng của merge sort là thay vì sắp xếp 8 phần tử (khó sắp ) thì ta chia đôi dãy đó ra làm đôi (số phần tử nhỏ hơn –> sắp dễ hơn ) và sắp xếp các dãy con rồi ghép 2 dãy con lại ( gọi là merge 2 dãy con )

Vậy ta làm như sau:
Chia đôi –> được hai dãy con mới là 12 13 45 32 và 100 34 65 10
sắp 2 dãy con lại : 12 13 45 32 gọi là dãy A
100 34 65 10 gọi là dãy B
+ Muốn sắp A ta cũng làm y như trên
Chia đôi A , được 2 dãy mới là A11 = { 12 13 } A12 = {45 32 }
Chia đôi B được 2 dãy mới là B11 = {100 34} B12 = {65 10 }
+ Sắp xếp A11, B11 , A12 , B12
+ Muốn sắp xếp A11 thì ta cũng chia đôi đến khi sắp được
ta có 2 dãy con là A21 = {12} A22 = { 13}
Sắp 2 dãy con trên được ( đơn giản vì chỉ có một phần tử ) là A21 = {12 } A22 = {13}
Sắp xong thì ta merge lại thành A11 = { 12 13 }
+ Tương tự sắp xếp cho B11 , A12 , B12 ta cũng có
B11 = {34 100} B12 = {10 65 } A12 = {32 45 }
+Sắp xếp xong , ta sẽ merge lại A11 , A12 thành A = { 12 13 32 45 }
B11 , B12 thành B = { 10 34 65 100 }
Sắp xong A , B , ta sẽ merge chúng lại thành dãy ban đầu :
{10 12 13 32 34 45 65 100 }

Phương pháp merge:
VD A = { 12 13 32 45 }
B = { 10 34 65 100}

Đầu tiên lấy phần tử đầu tiên của A và B : 12 và 10
10 < 12 nên ta lấy 10 bỏ vào mảng kết quả là C = {10}
Giử lại số 12 , và lấy tiếp phần tử thay thế 10 trong mảng B là 34
So sánh 12 và 34 . 12 < 34 , lấy 12 ra và bỏ vào C = {10 12}
Giử lại 34 . Lấy phần tử kế tiếp để thay cho 12 trong mảng A là 32
So sánh 32 và 34 chọn 32 bỏ vảo C = { 10 12 32 }
…….. Làm tương tự ……
Đến bước cuối cùng A hết phần tử B còn lại B = { 65 100}
Ta sẽ bỏ toàn bộ mảng B vào C . Kết quả C đã được merge và có thứ tự

Giải thuật:(cho trường hợp dùng list để chứa các phần tử cần sort)

Sortable_List là một lớp list có đặc điểm là có hàm sort
Node là một template class biểu diễn cho các node trong list
Record là class dùng để biểu diễn data cần sắp xếp . ( VD như sắp một dãy các số nguyên , hay VD là sắp theo tên của các record bao gồm tên , tuổi , số điện thoại …)
sublist là list cần sắp xếp

Code:

Sortable_List<Record>::recursive_merge_sort(Node<Record> *&sublist )
 {
     if ( sublist  != 0 && sublist->next != 0 } //tức là có tồn tại 2 node trở lên
//để có thể chia đôi sublist được
     {
               Node <Record > *second_half = divide_from (sublist);
               recursive_merge_sort(sublist) ;
               recursive_merge_sort(second_half) ;
               sublist = merge(sublist, second_half)
     }
 }

 Node<Record>* Sortable_List <Record>::divide_from( Node<Record> *sublist)
 {
           Node<Record> *position , *midpoint , *second_half ;
           if (( midpoint = sublist) == NULL) return NULL ; // hổng có ds để chia
           position  = midpoint->next ;
           while(position != 0)
         {
                   position = position->next ;
                   if ( position  != 0)
                   {
                             midpoint = midpoint->next ;
                             position = position->next ;
 // midpoint duyêt 1 thì position duyệt 2 node cùng 1 lúc nên khi position kết thúc = NULL
//thì midpoint cũng đang ở vị trí chính giữa;
                   }
         }
           second_half = midpoint->next ;
           midpoint->next = NULL ;
           return second_half ;
 }

 Node <Record> * merge(Node<Record> *first , Node<Record>* second )
 {
       Node<Record> *last_sorted ;
       Node<Record> combined ;
       last_sorted = &combined ;
       while ( first != NULL && second !=  NULL )
       {
               if (first->entry <= second->entry ) {
                         last_sortesorted->next = first ;
                         last_sorted = first ;
                         first = first->next ;
               }
               else
               {
                       last_sorted->next = second ;
                       last_sorted = second ;
                       second = second->next ;
               }
         }
         if ( first == NULL )
               last_sorted->next = second ;
         else
               last_sorted-> next = first  ;
         return combind.next
 }

//

PS : Hàm merge này viết hay , không tạo ra một ds mới để chứa kết quả như ta trình bày ở VD mà chỉ dùng một ds các con trỏ (combined) để chỉ đến thứ tự các node ở trên cả hai first và second. Cách này có lợi nếu Record là một trường phức tạp .

_________________________

Quick sort

Ý tưởng:
Gần giống như merge sort , ta sẽ chia đôi mảng cần xếp rồi sắp xếp các mảng con , sau đó sẽ ghép mảng con đã sắp xếp thành mảng ban đầu nhưng đã sắp xếp

Điểm khác nhau: Là chổ ta chia đôi mảng con theo nguyên tắc riêng :
Gọi điểm mà tại đó ta chia đôi mảng ban đầu có trị là pivot (không nhất thiết là nằm đúng vị trí chính giữa . Nhưng giải thuật sẽ chạy tốt nếu nó nằm gần điểm chính giữa) và ta sẽ không cần merge 2 dãy con (do đó nhìn chung sẽ chạy nhanh hơn ) , thỏa điều kiện là tất cả những phần tử bên trái pivot đều nhỏ hơn pivot và nằm bên phải pivot thì lớn hơn pivot

VD :
2 4 6 7 18 14 13
Ta chọn phần tử pivot = 7 ( do bên trái của nó nhỏ hơn pivot = 7 , bên phải lớn hơn pivot = 7 ) (Thực ra ta phải tìm pivot , do ở đây làm bằng tay nên dễ thấy )
Chia đôi : A = { 2 4 6 } B = { 18 14 13 }
+ Sắp A
+ Trong dãy A ta cũng chọn phần tử pivot là 4
+ Được 2 dãy con là A11 = {2 } A12 = {6}
+ Sắp A11 ( sắp sẵn rồi )
+ Sắp A12 ( sắp sẵn rồi )
+ Tạo lại mảng A = { A11 được sắp , pivot , A12 được sắp } = {2 4 6 }
+Sắp B . Trong B ta không thấy được pivot do chọn cái nào ta cũng không thấy thỏa . Nhưng mục tiêu của quick sort là làm sao ta được dãy
<C= dãy có trị nhỏ hơn pivot > pivot < D= dãy có trị lớn hơn pivot >
Sắp 2 dãy con C , D rồi ghép lại ta được dãy sắp thứ tự .

Vì vậy áp dụng một giải thuật tìm pivot trong B( sẽ trình bày sau ) ta sẽ được C = { 13} D = {18} và pivot là 14 .
+ Sắp dãy con C , D ( do chỉ có một phần tử nên không sắp , hoặc tìm pivot)
+ Ghép lại tạo thành mảng B được sắp B = { 13 14 18 }

+Ghép A và B để tạo thành mảng được sắp xếp ban đầu

Thuật toán

Code:

void Sortable_List<Record>::quick_sort()
 {
           recursive_quick_sort(0 , count -1 ) ;
 }

 void Sortable_List<Record>::recursive_quick_sort(int low , int high )
 {
           int pivot_position ;
           if (low < high )
           {
                     pivot_position = partition (low , high ) ;
                     recursive_quick_sort(low , high ) ;
                     recursive_quick_sort(pivot_position +1 , high ) ;
           }
 }

 int Sortable_List<Record>::partition(int low , int high )
 {
               Record pivot ;
               int i , last_small;
               swap ( low , (low +high) /2 ;
               pivot = entry[low] ;
               last_small = low ;
               for ( i = low +1 ; i <= high ; i ++ )
               {
                         if(entry[i] < pivot )
                         {
                                     last_small = last_small +1 ;
                                     swap ( last_small , i ) ;
                         }

               }
                 swap (low , last_small );
                 return last_small ;
 }

PS : Hiệu quả của giải thuật quicksort phụ thuộc rất nhiều vào việc chọn cho được pivot tốt ( tức nếu pivot nằm gần chính giữa thì đạt gần tối ưu )

Có rất nhiều phiên bản quicksort khác nhau nếu ta thay đôi cách tìm pivot . VD Ở cách trên phương pháp làm là chọn phần tử giữa để lấy trị của nó làm pivot ,rồi sau đó sẽ di chuyển phần tử giữa để nó đúng vào vị trí cần có của pivot là <bên trái nhỏ hơn pivot > pivot <bên phải lớn hơn pivot > . Ta có thể chọn cách khác là lấy phần tử đầu làm trị pivot . Sau đó di chuyển phần tử đầu đến đúng vị trí cần có của pivot .
Do đó ta sẽ có rất nhiều cách để hiện thực một ý tưởng và nhiều phiên bản của quick sort . Bởi vậy tui thích xem ý tưởng hơn là đưa ra những đoạn code rồi ngồi xem code nó chạy như thế nào .

————————————-

HEAP SORT

Heap là một cấu trúc dữ liệu , có thể được biểu diễn thông qua 2 cách :
-Dạng thứ 1: Dạng cây nhị phân có đặc điểm là node cha thì lớn hơn 2 node con trực tiếp của nó .
-Dạng thứ 2: nếu ta đánh số các node theo thứ tự từ trên xuống và từ trái qua . Bắt đầu là node root = 0 , thì ta có thể định nghĩa heap thông qua mảng một chiều , có đặc điểm là phần tử thứ k sẽ lớn hơn các phần tử thứ 2k+1 và 2k+2 . Ta có thể dễ nhận thấy là phàn tử thứ 0 sẽ tương ứng với root trong cây ở cách biểu diễn thứ 1

Nguyên tắc sắp xếp của heap sort
Dựa vào tính chất của heap trong cách biểu diễn thứ 1 và thứ 2 , ta có thể thấy phần tử đầu tiên trong cách biểu diễn theo mảng sẽ là phần tử lớn nhất —> cách sắp xếp đơn giản là : ( Gọi mảng ban đầu là A )

Khởi tạo : Tạo heap từ mảng ban đầu đã cho (mảng A )
1. Lấy phần tử đầu tiên trong mảng ra bỏ vào mảng kết quả
2. Tạo lại heap từ mảng A
3.Quay lại bước 1

VD : Ta lấy một mảng đã được tạo thành một heap :

y r p d f b k a c

Lấy phần tử đầu tiên là y bỏ vào mảng kết quả C = { y }

khi này A = r p d f b k a c
Tạo heap A = r f p d c b k a

Lấy phần tử đầu tiên ra là r bỏ vào mảng C = { r y }
Khi này A = { f p d c b k a }
Tạo heap cho A = { p f k d c b a}

Lấy phần tử đầu tiên ra là p bỏ vào mảng C = { p r y }
Khi này A = { f k d c b a }
Tạo heap cho A = { k f b d c a}

Lấy phần tử đầu tiên ra là k bỏ vào mảng C = { k p r y }
Khi này A = { f b d c a }
Tạo heap cho A = { f d b a c}

Lấy phần tử đầu tiên ra là f bỏ vào mảng C = { f k p r y }
Khi này A = { b d c a }
Tạo heap cho A = { d c b a}

Lấy phần tử đầu tiên ra là d bỏ vào mảng C = {d f k p r y }
Khi này A = { c b a }
Tạo heap cho A = { c a b }

Lấy phần tử đầu tiên ra là c bỏ vào mảng C = {c d f k p r y }
Khi này A = { b a }
Tạo heap cho A = { b a }

Lấy phần tử đầu tiên ra là b bỏ vào mảng C = {b c d f k p r y }
Khi này A = { a }
Tạo heap cho A = { a }

Kết thúc ta có được mảng C đã có thứ tự .

Cải tiến:
Ta có thể hạn chế việc sử dụng thêm mảng C bằng cách tận dụng luôn mảng A ban đầu . Ta làm như sau

A = y r p d f b k a c
Bước 1 :
Lấy y ra
Lấy c ra
Bỏ y vào chổ của c .
Bỏ c vào chỗ của y

Khi ta bỏ y vào chỗ của c thì giống như ta bỏ y vảo mảng C .
Khi này mảng A sẽ coi như gồm 2 phần A = c r p d f b k a —- y

Bước 2 : tạo heap cho phần đứng trước của A là c r p d f b k a
Phần sau là chứa y để nguyên

Ta sẽ có A mới là : r f p d c b k a — y

Quay lại bước 1 : Lấy r , a ra và swap r và a
A sẽ thành A= a f p d c b k — r y
Tạo heap cho A = p f k d c b a — r y
………..
Làm tương tự đến khi kết thúc

Qua VD ta thấy rằng phần quan trọng nhất là làm sao sinh ra heap từ một mảng cho trước

Sau đây là phần code cho phần cải tiến
Giải thuật

Post Condition : Dùng để phục hồi lại heap .
Pre Condition :

Ta sẽ có A mới là : r f p d c b k a — y
Quay lại bước 1 : Lấy r , a ra và swap r và a
A sẽ thành A= a f p d c b k — r y
Tạo heap cho A = p f k d c b a — r y

Thì khi này current chính là a
low là 0
high là 7

Code:

void Sortable_List<Record>::insert_heap(const Record &current, int low , int high )
 {
               int large ;
               large = 2*low+1 ;
               while ( large <= high ) {
                         if (large < high  && entry[large] < entry[large+1] )
                                     large ++ ;
                         if(current >= entry[large] )
                           {
                                 break ;
                           }
                           else
                           {
                                 entry[low] = entry[large] ;
                                 low = large ;
                                 large = 2 *  low + 1 ;
                           }
               }
               entry[low] = current ;
 }

Tạo ra heap lúc ban đầu , lúc chưa chạy giải thuật
 void Sortable_List<Record>::bulidheap()
 {
           int low ;
           for ( low = count / 2- 1; low >= 0 ; low -- )
           {
                   Record current = entry[low] ;
                   insert_heap(current, low, count -1) ;
           }
 }

 void Sortable_List<Record>::heapsort ()
 {
             Record current ;
             int last_unsorted ;
             buildheap() ;
             for ( last_unsorted = count -1 ; last_unsorted > 0 ; last_unsorted -- )
             {
                       current = entry[ last_unsorted] ;
                       entry[last_unsorted]  = entry[0] ;
                       insert_heap(current,0,last_unsorted-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<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 ;
                 }
       }
 }

------------------------------------------------------
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 ;
           }

---------------------------------------------------------------
3. thuật toán sắp xếp cơ số (exchange radix sort):

ý tưởng của thuật toán này cũng tương tự như quick sort. trong

trường hợp đặc biệt mảng cần sắp xếp là các số nguyên, ta biểu diễn các

phần tử của mảng ở dạng nhị phân rồi tiến hành chia mảng thành 2 phần

dựa trên các bít nhị phân của nó: phần đầu gồm những số có bit cao nhất

băng 0, phần còn lại có bít cao nhất bằng 1 (ta gọi bit này là bit z).

dễ nhận thấy rằng tất cả các phần tử của phần đầu sẽ nhỏ hơn các phần

tử ở phần cuối.

sau đó quá trình lại được tiếp tục (đệ quy) bằng cách sắp xếp

tương tự đối với từng phần, tất nhiên bit để căn cứ so sánh lúc này sẽ

là bit z-1 (z là bit cao nhất). cứ như vậy đến khi sắp xếp căn cứ vào

bit 0 thì quá trình sắp xếp hoàn tất và ta có mảng được sắp xếp.

chương trình mô phỏng giải thuật trên như sau:

Code:

 void *radixsort(int l, int r, int b){ /* sắp xếp đoạn [l,r] dựa theo bit b */
   int i, j;
   if (l >= r) return;
   i = l; j = r;
   do {
     while (((i < j) && ((a[i]>>b) & 1)) == 0) ++i; /* tìm phần tử có bit b = 1 từ đầu đoạn */
     while (((i < j) && ((a[j]>>b) & 1)) == 1) --j;  /* tìm phần tử có bit b = 0 từ cuối đoạn */
     temp = a[i]; /* đổi chỗ chúng */
     a[i] = a[j];
     a[j] = temp;
   } while (i != j); /* đến khi phân đoạn xong */
   if (((a[j] >> b) & 1) == 0) ++j; /* j là điểm bắt đầu đoạn có bit b = 1 */
   if (b > 0) { /* chưa xét tới bit cuối cùng */
     radixsort(l, j-1, b-1);
     radixsort(j, r, b-1);
   }

và trong chương trình muốn sắp xếp chỉ cần gọi radixsort(1, n, z)
với n là số phần tử và z là số bit nhiều nhất của các phần tử.

có thể nhận thấy là code của thuật toán này có nhiều nét tương đồng với code

của thuật toán quicksort.
thuật toán trên có thể mở rộng cho sắp xếp theo cơ số r bất kỳ,

chứ không chỉ riêng cơ số 2. khi đó các phần tử sẽ được biểu diễn trong

hệ cơ số r, và việc so sánh sẽ căn cứ theo các chữ số (tình từ cao

xuống thấp) trong hệ cơ số r đó. tất nhiên lúc đó chúng ta sẽ không

phân ra làm 2 đoạn như trên, mà sẽ có tất cả r đoạn: đoạn đầu tiên chứa

chữ số 0 ở đầu, đoạn tiếp chứa chữ số 1 ở đầu, ..., đoạn cuối cùng chứa

chữ số r-1.
thuật toán trên làm việc rất tốt với các hệ thống (ngôn ngữ lập

trình) sử dụng các thao tác cấp thấp ở mức độ bit. khi đó thuật toán

này nhanh hơn hẳn quicksort. tuy nhiên hiện nay hầu hết các hệ thống

đều thao tác đến mức độ byte, word nên cũng hạn chế đi tốc độ của thuật

toán này.

độ phức tạp của thuật toán này là O(n.min(z,log2(n))), trong đó n

là số phần tử cần được sắp xếp và z là số bit cần được so sánh.

4. thuật toán sắp xếp cơ số trực tiếp (straight radix sort):

ý tưởng của thuật toán này cũng gần giống như thuật toán sắp xếp cơ số ở trên.

giả sử ta có 1 mảng các số nguyên dương. đầu tiên ta sẽ sắp xếp

các phần tử căn cứ theo chữ số đơn vị bằng 1 thuật toán sắp xếp ổn

định. sau đó, ta lại sắp xếp tiếp các phần tử theo chữ số hàng chục

cũng bằng 1 thuật toán sắp xếp ổn định (thuật toán sắp xếp ổn định là

gì, chút nữa mình giải thích kỹ hơn). vì là thuật toán sắp xếp ổn định

nên nêu 2 phần tử có chữ số hàng chục giống nhau thì phần tử nào có chữ

số hàng đơn vị nhỏ hơn sẽ đứng trước.

quá trình lại được tiếp tục bằng cách sắp xếp theo hàng trăm,

nghìn, ... đến khi kết thúc. do tính ổn định của thuật toán sắp xếp tại

từng bước nên đảm bảo kết quả cuối cùng của ta sẽ thu được mảng sắp xếp

tăng dần.

thuật toán này có thể mở rộng ra bằng cách ở mỗi bước ta không lấy

1 chữ số ra để so sánh mà lấy 1 cụm chữ số để tiết kiệm thời gian. 1

cụm chữ số có thể bao gồm 2, 3, ... chữ số liên tiếp nhau, để cho tiện

ta vẫn gọi cụm chữ số đó là 1 "chữ số". khi đó tại mỗi bước, thời gian

sắp xếp sẽ giảm đi từ 2, 3 ... lần do không phải lặp lại.

thông thường, để sắp xếp các phần tử theo 1 chữ số thì thuật toán

tốt nhất mà ta nên dùng ở đây là thuật toán đếm phân phối. lý do là vì

các chữ số nằm trong khoảng nào ta đã biết, và việc đếm trên chúng hoàn

toàn dễ dàng.

khi viết chương trình phải chú ý các điểm sau:

- phải thiết kế các cụm "chữ số" thích hợp sao cho việc tách các "chữ số" đó ra từ
1 phần tử của mảng là đơn giản.

- sử dụng ít lần nhất phép đếm phân phối.

- phép đếm phân phối phải được thực hiện nhanh.

bây giờ chúng ta nói đến tính ổn định của thuật toán sắp xếp:

tính ổn định của thuật toán sắp xếp:

một thuật toán được gọi là ổn định nếu nó bảo toàn thứ tự ban đầu của các phần tử bằng nhau

trong mảng. Điều này có nghĩa là nếu trong mảng có 2 phần tử a[i] và a[j], a[i] đứng trước a[j].
nếu 2 phần tử này có giá trị bằng nhau a[i] = a[j] thì sau khi sắp xếp,

một thuật toán ổn định sẽ đặt a[i] lên trước a[j] để đảm bảo thứ tự ban đầu

của chúng trong mảng.Điều này là không cần thiết lắm nếu chúng ta chỉ tiến hành sắp xếp

đối với mảng 1 chiều các số thực. nhưng vấn đế sẽ nảy sinh khi sắp xếp

những mảng mà mỗi phần tử của nó là 1 cấu trúc, trong đó chúng ta cần

phải sắp xếp dựa theo 1 trường khoá nào đó. ví dụ như có 1 danh sách

lớp, và cần phải sắp xếp danh sách này theo trình tự tăng dần của ngày

sinh chẳng hạn. khi đó nếu 2 người cùng ngày sinh thì sao? vấn đề này

được giải quyết nhờ vào tính ổn định trong 1 thuật toán, tức là nếu 2

người cùng ngày sinh thì thứ tự trong danh sách ban đầu sẽ được bảo toàn.

trong những thuật toán đã trình bày ở trên thì thuật toán sắp xếp

nổi bọt, chọn, đếm phân phối là những thuật toán ổn định, còn những

thuật toán sắp xếp khác (nói chung là đòi hỏi phải đổi giá trị của 2

phần tử bất kỳ trong mảng) là không ổn định.
trên nguyên tắc có thể biến bất cứ thuật toán không ổn định nào thành thuật toán ổn định

bằng phương pháp sau:

giả sử ta cần sắp xếp 1 mảng, ta sẽ thêm cho mỗi phần tử 1 khoá index là

thứ tự ban đầu của chúng trong mảng cũ. trong thuật toán sắp xếp được áp dụng,

khi cần đổi chỗ 2 phần tử giống nhau A và B thì ta sẽ

so sánh khoá index của chúng, phần tử nào có khoá nhỏ hơn thì đứng trước.

(tham khảo tài liệu Bài giảng chuyên đề của Lê Minh Hoàng)

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: