Cấu trúc dữ liệu & giải thuật
Giải thuật sắp xếp dữ liệu
Lời mở đầu
Trong kỷ nguyên Công Nghệ Thông Tin, cấu trúc dữ liệu là nền tảng trong
mọi hoạt động của các tổ chức.Cấu trúc dữ liệu được biểu hiện dưới nhiều khía
cạnh. Cấu trúc dữ liệu và giải thuật là một môn học cơ sở trong chương trình
đào tạo trang bị cho sinh viên những kiến thức cơ bản về cấu trúc, dữ liệu khi
thiết kế và cài đặt các phần mềm.
Trong các bước giải quyết một bài toán trên máy tính, công đoạn lập trình
có vai trò quan trọng nhất. Việc ứng dụng tin học ngày càng phát triển, các yêu
cầu của thực tiễn ngày càng đa dạng. Điều đó đòi hỏi phải thiết kế các giải thuật
giải quyết một cách hiệu quả nhất vấn đề đặt ra.
Sắp xếp (sort) là một quá trình biến đổi một danh sách các đối tượng thành
một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóng một vai trò
rất quan trọng trong việc tìm kiếm dữ liệu. Chẳng hạn, chúng ta thử hình dung
xem một cuốn từ điển nếu các từ không được sắp xếp thứ tự mà người ta vẫn
thường làm sẽ khó khăn thế nào trong việc tra cứu các từ. Trong lĩnh vực kinh
tế việc sắp lại càng quan trọng.
Với sự bùng nổ của công nghệ thông tin đã xuất hiện nhiều ngôn ngữ lập
trình ví dụ như foxpro, pascal,C+,C++,...Trong đó, ngôn ngữ lập trình cấp cao
pascal là một ngôn ngữ có định kiểu mạnh mẽ, gần gũi với ngôn ngữ tự nhiên
và được nhiều người biết đến. Đó chính là lý do mà nhóm chúng tôi đã lựa
chọn ngôn ngữ này để sử dụng cho bài toán sắp xếp.
Để giải quyết một bài toán sắp xếp ta có rất nhiều cách như: sắp xếp theo
kiểu lựa chọn, sắp xếp theo kiểu đổi chỗ, sắp xếp theo kiểu vun đống,...
Thông qua ngôn ngữ lập trình pascal nhóm chúng tôi đã đưa ra một số
thuật toán sắp xếp cơ bản. Mong được sự ủng hộ của thầy cô và các bạn.
Sắp xếp dữ liệu - giải thuật và ứng dụng 1
Cấu trúc dữ liệu & giải thuật
Giới thiệu và phân tích bài toán.
1)Tên đề tài

Procedure Insert_sort (K,n)
{ Để đảm bảo việc chèn được thực hiện ngay từ khoá đầu tiên ta đưa vào
dãy khoá sắp xếp một khoá giả có giá trị nhỏ hơn tất cả các khóa thực sự trong
dãy và đứng ở đầu dãy
K[0]= -
∞
; x=K[i]
X: lưu trữ khoá đang xét ở lượt thứ i}
1.( Khởi tạo biến)
K[0]:= -
∞
;
2.( Sắp xếp)
for i:=2 to n do
begin
x=K[i]; j= i-1 ( j là số khoá đã được sắp xếp trước khoá k[i])
while x < K[j] do K[j +1] := K[j]
j:=j -1; end;
K[ j+1] :=x;
End;
Sắp xếp dữ liệu - giải thuật và ứng dụng 3
Cấu trúc dữ liệu & giải thuật
3.Return;
c. Mô tả hoạt động của giải thuật sắp xếp theo kiểu chèn:
Ví dụ 1-1 Sắp xếp mảng gồm 10 mẩu tin đã cho trong ví dụ11.

Khoá
Bước
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
Ban đầu 5 6 2 2 10 12 9 10 9 3

1.(Khởi tạo)
For i:=1 to n-1 do
For j:=n down to i+1 do begin
If k[j]<k[j-1] then begin
X:=k[j];
k[j]:=k[j-1];
k[j-1]:=x;
end;
end;
2.Return
* Mô tả hoạt động giải thuật sắp xếp nổi bọt
Sắp xếp dữ liệu - giải thuật và ứng dụng 6
Cấu trúc dữ liệu & giải thuật
Ví dụ 1-2: Sắp xếp mảng gồm 10 mẩu tin đã cho trong ví dụ 1-1.

Khoá
Bước
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
Ban đầu 5 6 2 2 10 12 9 10 9 3
Bước 1 2 5 6 2 3 10 12 9 10 9
Bước 2 2 5 6 3 9 10 12 9 10
Bước 3 3 5 6 9 9 10 12 10
Bước 4 5 6 9 9 10 10 12
Bước 5 6 9 9 10 10 12
Bước 6 9 9 10 10 12
Bước 7 9 10 10 12
Bước 8 10 10 12
Bước 9 10 12
Kết quả 2 2 3 5 6 9 9 10 10 12
Bảng sắp xếp nổi bọt

if K[m]<K[i] then begin
X:=K[m]
K[m]:=K[i];
K[i]:=X;
End;
End;
2.Return.
c. Mô tả hoạt động của sắp xếp kiểu lựa chọn
Hình 2-1: Sắp xếp chọn
Ví dụ1-3: Sắp xếp mảng gồm 10 mẩu tin có khóa là các số nguyên: 5, 6,
2, 2, 10, 12, 9, 10, 9 và 3

Khoá
Bước
a[1] a[2] a[3] a[4] A[5] a[6] A[7] a[8] a[9] a[10]
Sắp xếp dữ liệu - giải thuật và ứng dụng 10
Cấu trúc dữ liệu & giải thuật
Ban đầu 5 6 2 2 10 12 9 10 9 3
Bước 1 2 6 5 2 10 12 9 10 9 3
Bước 2 2 5 6 10 12 9 10 9 3
Bước 3 3 6 10 12 9 10 9 5
Bước 4 5 10 12 9 10 9 6
Bước 5 6 12 9 10 9 10
Bước 6 9 12 10 9 10
Bước 7 9 10 12 10
Bước 8 10 12 10
Bước 9 10 12
Kết quả 2 2 3 5 6 9 9 10 10 12
Bảng mô tả sắp xếp kiểu lựa chọn
• Ví dụ

xếp ).
C. Giải thuật.
{ Việc thực hiện vun đống được thực hiện lặp đi lặp lại nhiều lần nên ta
sẽ xây dựng 1 thủ tục để thực hiện vun đống, với cây có gốc là I và có n nút }.
Procedure Vundong (i,n)
{Giải thuật nhăm vun đống đối với cây nhị phân hoàn chỉnh có gốc là I
mà 2 cây con có gốc tương ứng 2i, 2i+1, đã là đống.
1{khởi tạo}.
{ Khoá cha: là biến lưu trữ nút cha}
Khoacha=K[i]
jchỉ số của các con.
Sắp xếp dữ liệu - giải thuật và ứng dụng 13
Cấu trúc dữ liệu & giải thuật
Khoacha:=K[i];
j:=2i;
while j,<n do begin
{Tìm con lớn nhất trong 2 con }.
If j<n and K[j] <K[j+1] then
j: =j+1;
{So sánh khoá cha lớn hơn con lớn nhất}
If Khoacha[j/2]=Khoacha;
{Đưa khoá cha vào đúng vị trí}
return; end;
3. { Khoá con lớn nhất > Khoacha}
K[
 
2/j
]= K[j] ;
j:= 2j
{Chuyển khoá con lớn nhất lên và đi xuống}