Trước tiên, ta tìm hiểu phương pháp sắp xếp chèn[insertion sort],đây là một thuật toán hiệu quả để sắp xếp các thành phần có số lượng nhỏ. Kỹ thuật sắp xếp chèn làm việc giống như cách thức mà nhiều người xếp một tay bài tây hay bài rumi. Ta bất đầu bằng một tay trái trắng với các lá bài tung sấp trên bàn. Sau đó, lần lượt dỡ từng lá bài một ra khỏi bàn rồi chèn nó vào đúng vị trí trong tay trái. Để tìm đúng vị trí cho một lá bài, ta so sánh nó với mỗi lá bài sấn có trong tay, từ phải qua trái, như minh họa trong Hình 1.1.
Mã giả sắp xêp chèn của chúng ta được trình bày dưới dạng một thủ tục tên INSERTION-SORT, nó nhận một mảng A|1..m1 dưới dạng một tham sô”, chứa một dãy cỏ chiều dài n sẻ được sắp xốp. (Trong mà, sỏn thành phần trong A được biểu thị bằng ỉeru>th\A\.) Các con sô”nhập được sắp xếp tại chồ: các con sốđược dàn xốp lại trong mảng A, luôn cỏ tối đa một sô” lượng bâl biên của chúng được lưu trữ ngoài máng. Mans đầu vào A chứa dày kết xuất đã sắp xốp khi INSERTION-SORT hoàiuất.
INSERTION-SORT(A)
- for / <r- 2to ỊengthịA]
- do key <r- A[ị]
- i> chèn A[ị] vào chuỗi có sắp xếp A[ 1. j -1 ].
- ỉ<-j- 1
- while / > 0 và A[i] >key
- doA[í‘+l]^4[/]
- / <— / – 1
- A[i +1] <— key
Hình 1.2 nêu cách làm việc của thuật toán này với A =<5, 2, 4, 6, 1, 3>. Chỉ sốjnêu rõ “lá bài hiện hành” đang được chèn vào tay. Các thành phần mảng A[\..j – 1] tạo thành tay đang được sắp xếp, và các thành phần A[ị + 1 ..n\ tương ứng với đông lá bài vẫn còn trên bàn. Chỉ sô” jdời từ trái sang phải qua mảng. Với mỗi lần lặp của vòng lặp for “phía ngoài”, thành phần A[ị] được lấy ra khỏi mảng (dòng 2). Sau đó, bắt đầu tại vị trí j – 1, các thành phần liên tiếp được dời về bên phải một vị trí cho đến khi tìm thây vị trí đúng đắn cho A[ị] (các dòng 4-7), tại điểm mà nó được chèn (dòng 8).
Hình 1.2 Phép toán INSERTION-SORT trên mảng A -<5, 2, 4, 6, 1, 3)>. Vị trí của chỉsốjđược nêu rõ bởi một vòng tròn.
Các quy ước mã gỉầ
Tập sách này sử dụng các quy ước dưới đây trong mã giả.
- Thụt đầu dòng để nêu rõ câu trúc khôi Ví dụ, thân của vòng lặp
for bắt đầu trên dòng 1 bao gồm các dòng 2-8, và thân của vòng lặp while bắt đầu trên dòng 5 chứa các dòng 6-7 nhưng không có dòng 8. Kiểu thụt dòng của chúng ta cũng áp dụng cho các câu lệnh if-then- else. Dùng kiểu thụt dòng thay vì các dâu chỉ quy ước của cấu trúc khối, như các câu lệnh begin vàend, sẽ tránh được sự bừa bộn trong khi vẫn bảo toàn, thậm chí còn tăng cường, tính minh bạch’.
- Các kiến tạo vòng lặp while, for, và repeat và các kiến tạo điều kiện if, then, và else cũng được diễn dịch giống như trong Pascal.
- Ký hiệu “t>” nêu rõ phần còn lại của dòng là một chú giải.
- Kiểu nhiều phép gán theo dạng i j <r- e sẽ gán cho cả hai biến i và j giá trị của biểu thức e; nó sẽ được xem như tương đương với phép gán j <r~ € theo sau là phép gán / <—
- Các biến (như ỉ, j, và key)là cục bộ đối với thủ tục đã cho. Ta không dùng các biến toàn cục mà không khai báo tường minh.
- Các thành phần mảng được truy cập bằng cách đặc tả tên mảng theo sau ià chỉ số trong các dấu ngoặc vuông. Ví dụ, A[f] nêu rõ thành phần thứi của mảng A. Ký hiệu được dùng để nêu rõ một miền các giá trị trong một mảng. Do đó, A[l..j] nêu rõ mảng con A bao gồm các thành phần A[l], A[2],…, A[jl
- Dữ liệu phức hợp thường được tổ chức thành các đối tượng[objects], bao hàm các thuộc tính[attributes] hoặc các trường[fields]. Để truy cập một trường cụ thể, ta dùng tên trường theo sau là tên đốì tượng của nó trong các dấu ngoặc vuông. Ví dụ, ta xem một mảng như một đối tượng có thuộc tính lengthnêu rõ sô” lượng thành phần mà nó chứa. Để đặc tả sô” lượng thành phần trong một mảng A, ta viết ỉength[Aị Tuy ta dùng các dâu ngoặc vuông cho cả trường hợp chỉ sô” mảng lẫn các thuộc tính đối tượng, song nó vẫn rõý theo từng ngữ cảnh diễn dịch.
Một biến biểu thị cho một mảng hay đôi tượng sẽ được xử lý như một biến trỏ[pointer] đến dữ liệu biểu thị cho mảng hay đô”i tượng đó. Với tât cả trường/của một đôi tượng X, việc ấn định ỵ<r- Xsẽ khiến/[y] = /[*]. Vả lại, nếu giờ đây ta â”n định f[x]<— 3, thì sau đó không những là/[x] = 3, mà còn ỉà/[y] = 3. Nối each khác, Xvà y trỏ đến (“là”) cùng đôi tượng sau phép gán y<— X.
Đôi lúc, một biến trỏ không tham chiếu một đôi tượng nào cả. Trong trường hỢp này, ta gán cho nó giá trị đặc biệt NIL.
- Các tham sô” được chuyền cho thủ tục theo giá trị: thủ tục được gọi
1: Trong các ngôn ngữỉập trình thực thụ, ta không nên sử dụng một mình tính nang thụt dòng để nêu rõ cấu trúc khối, bởi các cấp thụt dòng khó xác định khi mã được tách thành nhiều trang.
sê nhận bản sao các tham số riêng của nó, và nếu nó gán một giá trị cho một tham số, thường trình gọi [calling routine] sẽkhông thấy sự thay đổi đó. Khi các đôi tượng được chuyền, biến trỏ đến dữ liệu biểu thị cho đối tượng đó sẽ được chép, song các trường của đối tượng thì không. Ví dụ, nếu X là một tham số của một thủ tục được gọi [called procedure], thủ tục gọi sẽ không thấy phép gán X <— y trong thủ tục được gọi. Tuy nhiên, phép gán/[x] <— 3 lại lộ diện.
