Tìm hiểu về giải thuật: Một số phương pháp sắp xếp cơ bản

Bài viết được sự cho phép của BBT Tạp chí Lập trình

  Cấu trúc dữ liệu và giải thuật - Thuật toán tìm kiếm
  Kỹ Thuật Phân Tích Giải Thuật

1. Sắp xếp kiểu lựa chọn (Selection Sort)

Một trong những phương pháp đơn giản nhất để thực hiện sắp xếp một bảng khóa là dựa trên phép lựa chọn.

Nguyên tắc cơ bản của phương pháp sắp xếp này là “ở lượt thứ i(i=1,2,…,n) ta sẽ chọn trong dãy khoá Ki, Ki+1,…,Kn khoá nhỏ nhất và đổi chỗ nó với Ki ”.

Như vậy thì rõ ràng là sau j lượt, j khoá nhỏ hơn đã lần lượt ở các vị trí thứ nhất, thứ hai,…, thứ j theo đúng thứ tự sắp xếp. Ví dụ:

Sắp xếp dãy số sau theo thứ tự tăng dần: “42, 23, 74, 11, 65, 58, 94, 36, 99, 87”.

Sau đây là giải thuật:

Cho dãy khóa K gồm n phần tử. Giải thuật này thực hiện sắp xếp các phần tử của K theo thứ tự tăng dần dựa vào phép chọn phần tử nhỏ nhất trong mỗi lượt.

Procedure SELECT-SORT(K, n)
For i:=1 to n-1 do
     Begin
         M:=i;
         For j:=i+1 to n do
         If K[j]<K[m] then m:=j;
             If m!= j then
             Begin {đổi chỗ}
                 X:=K[i];
                 K[i]:=K[m];
                 K[m]:=X;
             End
     End
Return;

2. Sắp xếp chèn (Insertion Sort)

Nguyên tắc sắp xếp ở đây dựa theo kinh nghiệm của những người chơi bài. Khi có i-1 lá bài đã được sắp xếp ở trên tay, nay rút thêm lá bài thứ i nữa thì sắp xếp lại như thế nào ? Có thể so sánh lá bài mới lần lượt với lá bài thứ (i-1), thứ (i-2)… để tìm ra chỗ thích hợp và chèn nó vào chỗ đó.

Dựa trên nguyên tắc này, có thể triển khai một cách sắp xếp như sau:

Thoạt đầu K1 được coi như bảng chỉ gồm có một khoá đã sắp xếp. Xét thêm K2, so sánh nó với K1 để xác định chỗ chèn nó vào, sau đó ta sẽ có một bảng gồm 2 khoá đã được sắp xếp. Đối với K3 lại so sánh với K2, K1 và cứ tương tự như vậy với K4, K5, K6,… cuối cùng sau khi xét xong Kn thì bảng khoá đã được sắp xếp hoàn toàn.

Ta thấy ngay phương pháp này rất thuận lợi khi các khoá của dãy được đưa dần vào miền lưu trữ. Đó cũng chính là không gian nhớ dùng để sắp xếp. Có thể minh hoạ qua bảng sau:

Nhưng nếu các khóa đã có mặt ở bộ nhớ trong trước lúc sắp xếp rồi thì sao ?

Sắp xếp vẫn có thể thực hiện được ngay tại chỗ chứ không phải chuyển sang một miền sắp xếp khác. Lúc đó các khoá cũng lần lượt được xét tới và việc xác định chỗ cho khoá mới vẫn làm tương tự, chỉ có khác là: để dành chỗ cho khoá mới nghĩa là phải dịch chuyển một số khoá lùi lại sau, ta không có sẵn chỗ trống như trường hợp nói trên (vì khoá đang xét và các khoá sẽ được xét đã chiếm các vị trí đằng sau này rồi), do đó phải đưa khoá mới này ra một chỗ nhớ phụ và sẽ đưa vào vị trí thực của nó sau khi đã đẩy các khóa cần thiết lùi lại.

Sau đây là giải thuật ứng với trường hợp này:

Procedure SELECT-SORT(K, n)
For i:=1 to n-1 do
     Begin
         M:=i;
         For j:=i+1 to n do
         If K[j]<K[m] then m:=j;
             If m!= j then
             Begin {đổi chỗ}
                 X:=K[i];
                 K[i]:=K[m];
                 K[m]:=X;
             End
     End
Return;

{Trong thủ tục này người ta dùng X làm ô nhớ phụ để chứa khoá mới đang được xét. Để đảm bảo cho khoá mới trong mọi trường hợp, ngay cả khi vị trí thực của nó là vị trí đầu tiên, đều được chèn vào giữa khóa nhỏ hơn nó và khoá lớn hơn nó, ở đây đưa thêm vào một khoá giả K0, có giá trị nhỏ hơn mọi khoá của bảng, và đứng trước mọi khoá đó. Ta quy ước K0 = – }.

Procedure SELECT-SORT(K, n)
For i:=1 to n-1 do
     Begin
         M:=i;
         For j:=i+1 to n do
         If K[j]<K[m] then m:=j;
             If m!= j then
             Begin {đổi chỗ}
                 X:=K[i];
                 K[i]:=K[m];
                 K[m]:=X;
             End
     End
Return;

{xác định chỗ cho khoá mới được xét và dịch chuyển các khóa cần thiết }

Procedure SELECT-SORT(K, n)
For i:=1 to n-1 do
     Begin
         M:=i;
         For j:=i+1 to n do
         If K[j]<K[m] then m:=j;
             If m!= j then
             Begin {đổi chỗ}
                 X:=K[i];
                 K[i]:=K[m];
                 K[m]:=X;
             End
     End
Return;

{đưa X vào đúng chỗ}

Procedure SELECT-SORT(K, n)
For i:=1 to n-1 do
     Begin
         M:=i;
         For j:=i+1 to n do
         If K[j]<K[m] then m:=j;
             If m!= j then
             Begin {đổi chỗ}
                 X:=K[i];
                 K[i]:=K[m];
                 K[m]:=X;
             End
     End
Return;

Bảng ví dụ minh hoạ tương ứng với các lượt sắp xếp theo giải thuật này, tương tự như bảng đã nêu ở trên, chỉ có khác là không có chỗ nào trống trong miền sắp xếp cả, vì những chỗ đó đang chứa các khoá chưa được xét tới trong mỗi lượt (người đọc có thể tự lập ra bảng minh hoạ này).

3. Sắp xếp kiểu đổi chỗ (exchange sort)

Trong các phương pháp sắp xếp nêu trên, tuy kĩ thuật đổi chỗ đã được sử dụng, nhưng nó chưa trở thành một đặc điểm nổi bật. Bây giờ ta mới xét tới phương pháp mà việc đổi chỗ một cặp khoá kế cận, khi chúng ngược thứ tự, sẽ được thực hiện thường xuyên cho tới khi toàn bộ bảng các khóa đã được sắp xếp. Ý cơ bản có thể nêu như sau:

Bảng các khóa sẽ được duyệt từ đáy lên đỉnh. Dọc đường, nếu gặp hai khoá kế cận ngược thứ tự thì đổi chỗ chúng cho nhau. Như vậy trong lượt đầu khoá có giá trị nhỏ nhất sẽ chuyển dần lên đỉnh. Đến lượt thứ hai khoá có giá trị nhỏ thứ hai sẽ được chuyển lên vị trí thứ hai… Nếu hình dung dãy khoá được đặt thẳng đứng thì sau từng lượt sắp xếp, các giá trị khoá nhỏ sẽ nổi dần lên giống như các bọt nước nổi lên trong nồi nước đang sôi. Vì vậy phương pháp này thường được gọi bằng cái tên khá đặc trưng là: sắp xếp kiểu nổi bọt (bubble sort).

Ví dụ:

Sau đây là giải thuật:

Procedure SELECT-SORT(K, n)
For i:=1 to n-1 do
     Begin
         M:=i;
         For j:=i+1 to n do
         If K[j]<K[m] then m:=j;
             If m!= j then
             Begin {đổi chỗ}
                 X:=K[i];
                 K[i]:=K[m];
                 K[m]:=X;
             End
     End
Return;

Giải thuật này rõ ràng còn có thể cải tiến được nhiều. Chẳng hạn, xét qua ví dụ ở trên ta thấy: sau lượt thứ 3 không phải chỉ có ba khóa 11, 23, 36 vào đúng vị trí sắp xếp của nó mà là 5 khoá. Còn sau lượt thứ 4 thì tất cả các khóa đã nằm đúng vào vị trí của nó rồi. Như vậy nghĩa là năm lượt cuối không có tác dụng gì thêm cả. Từ đó có thể thấy: nếu nhớ được vị trí của khoá được đổi chỗ cuối cùng ở mỗi lượt thì có thể coi đó là giới hạn cho việc xem xét ở lượt sau. Chừng nào mà giới hạn này chính là vị trí thứ n, nghĩa là trong lượt ấy không có một phép đổi chỗ nào nữa thì sắp xếp có thể kết thúc được. Nhận xét này sẽ dẫn tới một giải thuật cải tiến hơn, chắc chắn có thể làm cho số lượt giảm đi và số lượng các phép so sánh trong mỗi lượt cũng giảm đi nữa. Người đọc hãy tự xây dựng giải thuật theo ý cải tiến này.

 (Nguồn: Cấu trúc dữ liệu và giải thuât –

Đỗ Xuân Lôi – NXB Đại học quốc gia Hà Nội).

Bài viết gốc được đăng tải tại Tạp Chí Lập Trình

Có thể bạn quan tâm:

Xem thêm các IT Jobs hấp dẫn tại TopDev