Sơ lược về các chủ đề
Sau đây là sơ lược về các chủ đề sẽ được đề cập trong phần này của chương trình:
+ Phần cơ sở: là các công cụ và phương pháp được dùng xuyên suốt cho tất cả các chương sau của phần này. Nó gồm một phần bàn luận ngắn về Pascal, theo sau là giới thiệu về các cấu trúc dữ liệu cơ bản gồm mảng, xâu liên kết, ngăn xếp, hàng đợi và cây. Chúng ta sẽ bàn luận về công dụng thực tiễn đệ quy và bắt đầu hướng tới việc phân tích và tiếp cận thực toán.
+ Sắp xếp: Các phương pháp sắp xếp sẽ được phát triển, được mô tả, được so sánh với nhau. Các thuật toán cho nhiều vấn đề có liên quan sẽ được xem xét gồm có hàng đợi ưu tiên, phép chọn và phép trộn. Một vài nền tảng trong số này được dùng như là nền tảng cho các thuật toán khác tiếp sau trong phần này.
+ Xử lý chuỗi: gồm một loạt các phương pháp để phân tích câu. Các ky thuật nén tập và mật mã cũng sẽ được khảo sát. Cũng vậy, một giới thiệu về các chủ đề nâng cao cùng được cung cấp qua việc xem xét một vài bài toán cơ bản quan trọng trong phạm vi của chúng.
+ Hình học: là một sự tập hợp có chọn lọc các phương pháp để giải quyết các bài toán liên quan đến điểm và đường ( và các đối tượng hình học đơn giản khác ). Chúng ta sẽ xem xét các thuật toán để tìm bao lồi của một tập điểm, phần giao của các đối tượng, để giải bài toán điểm gần nhất, tìm kiếm nhiều chiều ...
+ Đồ thị: Một chiến lược tổng quát để tìm kiếm trên các đồ thị sẽ được phát triển và được áp dụng cho các bài toán liên thông cơ bản, gồm có đường đi ngắn nhất, cây liên thông tối thiểu, mạng và so khớp. Một sự xem xét thống nhất đối với các thuật toán này chứng tỏ rằng tất cả đều dựa vào một thủ tục và thủ tục này phụ thuộc vào một cấu trúc dữ liệu cơ bản đã phát triển trước đó.
+ Các thuật toán toán học: gồm các phương pháp cơ bản từ số học và các số nguyên, đa thức, và ma trận cũng như các thuật toán để giải quyết cac vấn đề toán học mà nó phát sinh trong nhiều ngữ cảnh : việc tạo số ngẫu nhiên, lỡi giải của các chương trình đồng thời, xấp xỉ dữ liệu, và lấy tích phân. Sự nhấn mạnh thiên về các khía cạnh thuật toán của phương pháp, chứ không phải trên nền tảng của toán học
+ Các chủ đề cao cấp: được thảo luận nhằm mục đích liên hệ các chủ đề trong tập sách này với nhiều lĩnh vực nghiên cứu cao cấp khác. Phần cứng chuyên dụng, quy hoạch động, quy hoạch tuyến tính, tìm kiếm- vét cạn ...
I. Sắp xếp:
1. Khái niệm:
a) Sắp xếp là một quá trình tổ chức lại một dãy các dữ liệu theo một trật tự nhất định.
b) Mục đích của việc sắp xếp là nhằm giúp cho việc tìm kiếm dữ liệu một cách dễ dàng và nhanh chóng. Sắp xếp là một việc làm hết sức cơ bản và được dùng rộng rãi trong các kĩ thuật lập trình nhằm sử lý dữ liệu.
c) Các giải thuật sắp xếp được phân chia thành hai nhóm chính là:
- Sắp xếp trong (hay sắp xếp mảng).
Toàn bộ cơ sở dữ liệu cần sắp xếp phải được đưa vào bộ nhớ chính của máy tính. Do đó nó thường được sử dụng khi khối lượng dữ liệu không vượt quá dung lượng bộ nhớ chính.
Nhóm sắp xếp trong bao gồm các phương pháp :
* Phương pháp đếm.
* Phương pháp chèn.
* Phương pháp chọn.
* Phương pháp đổi chổ.
* Phương pháp trộn.
- Sắp xếp ngoài (hay sắp xếp tập tin).
Vận dụng trong trường hợp ta phải sắp xếp các tập tin chứa nhiều mẫu tin và mỗi mẫu tin có chiều dài tương đối lớn do đó ta không thể nạp toàn bộ vào bộ nhớ chính để sắp xếp thứ tự. Vì vậy ta phải có những phương pháp thích hợp cho việc sắp xếp tập tin.

2. Sắp xếp trong:
a) Khái niệm:
Cấu trúc dữ liệu thích hợp cho các phần tử cần sắp xếp thứ tự là Record. Mỗi phần tử có hai vùng đặc trương là: Vùng Key để chứa khoá của phần tử và được sử dụng trong các giải thuật tìm kiếm, vùng info dùng để chứa đữ liệu các phần tử.
Ta khai báo :
Type
Item = Record
key : Integer;
Info : Integer;
End;
Var
A : Array[1..n] of Item;
Khoá của phần tử có thể là chữ hoặc số.
Yêu cầu giải thích là dùng ít vùng nhớ và thời gian thực hiện nhanh.
b) Phương pháp đếm (Counting sort)
* Giải thích:
Nội dung của phương pháp này là đếm các phần tử có khoá nhỏ hơn hay bằng khoá của các phần tử A[i]. Nếu có j phần tử có khoá nhỏ hơn khoá của phần tử A[i] thì phần tử A[i] sẽ có vị trí theo thứ tự (j+1) trong dãy đã có thứ tự.
Trong giải thuật, ta dùng mảng Count[i] ( i = 1, 2, .. n ) với Count[i] cho biết số phần tử có khoá nhỏ hơn khoá của phần tử A[i]. Như vậy Count[i+1] là vị trí của phần tử A[i] trong dãy đã có thứ tự.
* Ví dụ:
Sắp xếp dãy 2 3 1 5 2 7 6 9 4
i: 1 2 3 4 5 6 7 8
Count: 2 0 4 1 6 5 7 3
Như vậy phần tử có khoá 9 ở vị trí 8 vì Count[9]=7.
* Thể hiện bằng Pascal:
Procedure Count_Sort;
Var
Count : Array[1..n] of Integer;
A : Array[1..n] of Item;
i,j : Integer;
Begin
For i := 1 to n do Count[i] := 0;
For i := n downto 2 do
For j := i-1 downto 1 do
If A[i].Key < A[j].Key Then
Count[j] := Count[j] + 1
Else Count[i] := Count[i] + 1;
For i := 1 to n do S[Count[i] + 1] := A[i];
For i := 1 to n do A[i] := S[i];
End;
c) Phương pháp chèn (Insertion Sort)
* Giải thích:
Nội dung của phương pháp này là giả sử ta có dãy A[1]..A[i-1] đã có thứ tự, có phải xác định vị trí thích hợp của phần tử A[i] trong dãy A[1]..A[i - 1] bằng phương pháp tìm kiếm tuần tự từ A[i - 1] trở về A[1] để tìm ra vị trí thích hợp của A[i]. Ta chèn A[i] vào vị trí này và kết quả là đãy A[1] .. A[i] có thứ tự. Ta áp dụng cách làm này với i = 2, 3, ..., n.
* Ví dụ:
Ta phải sắp xếp dãy số:
39 50 7 37 89 13 1 62
i=2 39 50 7 37 89 13 1 62
i=3 39 50 7 37 89 13 1 62
i=4 7 39 50 37 89 13 1 62
i=5 7 37 39 50 89 13 1 62
i=6 7 37 39 50 89 13 1 62
i=7 7 13 37 39 50 89 1 62
i=8 1 7 13 37 39 50 89 62
1 7 13 37 39 50 89 62
* Thể hiện bằng Pascal:
Procedure Insertion_Sort;
Var
x : Item;
i,j : Integer;
Begin
For i := 2 to n do
Begin
x := A[i];
A[0] := x;
j := j - 1;
While x.Key < A[j].Key do
Begin
A[j+1] := A[j];
j := j - 1;
End;
A[j+1] := x;
End;
End;
d) Phương pháp chọn (Selection Sort)
* Giải thích:
Nội dung của phương pháp này là ở bước thứ i (i = 1, 2, 3, ..., n-1 ) ta lựa chọn phần tử nhỏ nhất trong dãy A[i]..A[n] rồi đổi chổ phần tử này với phần tử A[i]. Cuối cùng ta sẽ có dãy A[1]..A[n] có thứ tự.
* Ví dụ:
Ta phải sắp xếp dãy số :
39 50 7 37 89 13 1 62
i=1 39 50 7 37 89 13 1 62
i=2 1 50 7 37 89 13 39 62
i=3 1 7 50 37 89 13 39 62
i=4 1 7 13 37 89 50 39 62
i=5 1 7 13 37 89 50 39 62
i=6 1 7 13 37 50 50 39 62
i=7 1 7 13 37 39 50 89 62
1 7 13 37 39 50 89 62
* Thể hiện bằng Pascal:
Procedure Selection_Sort;
Var
x : Item;
i,j ,k : Integer;
min : Integer;
Begin
For i := 2 to n-1 do
Begin
min := A[i].Key;
k := i;
For i := 1 to n-1 do
For j := i+1 to n do
If A[j].Key < min Then
Begin
min := A[j].Key;
k := j;
End;
x := A[k];
A[k] := A[i];
A[i] := x;
End;
End;
e) Phương pháp đổi chỗ:
Có rất nhiều phương pháp sắp xếp dựa trên việc đổi chỗ giữa 2 phần tử của dãy. Sau đây chúng ta xét các phương pháp:
- Bubble Sort.
- Shake Sort.
- Sell Sort.
- Quick Sort.

* Bubble Sort:
* Giải thích:
Nội dung của phương pháp này là duyệt các dãy A[1], ..., A[n]. Nếu A[i].Key > A[i+1].Key (i = 1, 2, 3, ..., n-1)#0 thì ta đổi chỗ A[i].Key với phần tử A[i+1].Key. Lập lại quá trình duyệt dãy này cho đến khi không còn việc đổi chổ của hai phần tử.
Chú ý rằng bất cứ lúc nào phần tử nhỏ nhất cũng gặp trước tiên. Nó như những bột khí nhẹ sẽ nổi lên trên khi đun nước. Sau đó ở thứ hai phần tử nhỏ thứ 2 sẽ được đặ vào đúng một vị trí. Vì vậy sắp xếp nổi bột thao tác như một kiểu sắp xếp chọn, mặc dù nó không làm nhiều việc hơn để đưa từng phần tử vào đúng vị trí.
* Ví dụ:
Ta phải sắp xếp dãy số:
39 50 7 37 89 13 1 62
Bước 0 1 2 3 4 5 6 7
50 1 1 1 1 13 1 62
39 39 7 7 7 7 7 7
7 50 39 13 13 13 13 13
37 7 50 39 37 37 37 37
89 37 13 50 39 39 39 39
13 89 37 37 50 50 50 50
1 13 89 62 62 62 62 62
62 62 62 89 89 89 89 89
* Thể hiện bằng Pascal:
Procedure Bubble_Sort;
Var
x : Item;
i,j : Integer;