BÁO CÁO THỰC TẬP CƠ SỞ
ĐỀ TÀI: TÌM HIỂU MỘT SỐ THUẬT TOÁN SẮP XẾP
Sinh viên thực hiện: Trần Đình Nguyên
Giáo viên hướng dẫn: Vũ Thị Thúy Thảo

Một số kiến thức cơ bản.

Một số thuật toán sắp xếp.

Tìm hiểu ngôn ngữ Java.

Demo chương trình.
1.Nội dung chính

Thuật toán:

Khái niệm thuật toán sắp xếp:
Thuật toán là một tập hữu hạn các chỉ thị hay
phương cách được định nghĩa rõ ràng cho việc hoàn
tất một sự việc từ một trạng thái ban đầu cho trước; khi
các chỉ thị này được áp dụng triệt để thì sẽ dẩn đến kết
quả sau cùng như đã dự đoán.
2.Một số kiến thức cơ bản

Khái niệm thuật toán sắp xếp.
•
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 thỏa mãn một thứ tự xác định
nào đó.
3.1. Sắp xếp chọn(Selection Sort)

3.1.3. Độ phức tạp của thuật toán
∗
T(n)=O(n2)
3.1.4. Ví dụ
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 2| 5 6 10 12 9 10 9 3
Bước 3: 2 2 3| 6 10 12 9 10 9 5
Bước 4: 2 2 3 5| 10 12 9 10 9 6
Bước 5: 2 2 3 5 6| 12 9 10 9 10
Bước 6: 2 2 3 5 6 9| 12 10 9 10
Bước 7: 2 2 3 5 6 9 9| 10 12 10
Bước 8: 2 2 3 5 6 9 9 10| 12 10
Bước 9: 2 2 3 5 6 9 9 10 10 12
3.2. Sắp xếp chèn(Insretion Sort).
3.2.1. Tư tưởng

Lấy dần từng phần tử từ dãy nguồn, chèn vào dãy đích sao cho
đảm bảo dãy đích có thứ tự.

Bước 1: Chèn phần tử a[2] vào danh sách đã có thứ tự a[1] sao
cho a[1], a[2] là một danh sách có thứ tự.

Bước i: Chèn phần tử a[i+1] vào danh sách đã có thứ tự a[1], a[2],
…a[i] sao cho a[1], a[2], …a[i+1] là một danh sách có thứ tự.
3.2. Thuật toán
Procedure InsertionSort;
Var i,j: Integer;
Begin
For i:=2 to n do

1.

Bước i: Xét các phần tử từ a[n] đến a[i+1], làm tương tự

Sau n bước ta được dãy đã có thứ tự.
3.3.2. Thuật toán
Procedure BubbleSort;
Var i,j: integer;
Begin
1. For i:=1 to n do
2. For j:=n downto i+1 do
3. if(a[j]<a[j-1]) then
4. Swap(a[j],a[j-1]);
End;
3.3.3. Độ phức tạp
T(n)=O(n)
3.3.4. Ví dụ
Bắt đầu Bước 1 Bước 2 Bước 3 Bước 4
5 2 2 2 2
6 5 2 2 2
2 6 5 3 3
2 2 6 5 5
10 3 3 6 6
12 10 9 9 9
9 12 10 9 9
10 9 12 10 10
3 9 10 10 12
3.4. Sắp xếp nhanh(Quick Sort)
3.4.1. Tư tưởng


Swap(A[L],A[R]);
Repeat L:=L+1 util A[L] > p;
Repeat R:=R-1 util A[R] <= p;
End;
Swap(A[i],A[R]);
End;
3.4.3. Độ phức tạp
T(n)=O(n)
3.4.4. Ví dụ

10 15 4 11 6 3 5 14 lấy chốt p=A[1]=10,L=1,R=9

Lần thứ nhất: Ta có L=2 và R=7 10 5 4 11 6 3 15 14

Khi L=4, R=6. 10 5 4 3 6 11 15 14

Khi L=6,R=5 6 5 4 3 10 11 15 14

Như vậy mảng A[1 8] đã được phân hoạch thành hai mảng con A[1 R-1] và
A[R+1 8] tức A[1 4] và A[6 8]. Sau đó tiếp tục phân hoạch hai mảng con trên.

3.5. Sắp xếp vun đống(Heap Sort)
3.5.1. Tư tưởng

Heap là một cây nhị phân đầy đủ trái mà mổi nút được
gán một giá trị khóa sao cho giá trị khóa ở nút cha
bao giờ củng nhỏ hơn hoặc bằng giá trị khóa ở hai nut
con. Do đó trong Heap ta có:

Nút gốc có khóa bé nhất

Begin
Swap(A[1],A[i]); //đổi chổ gốc
PUSHDOWN(1,i-1); //vun lại đống
End;
End;
3.5.3. Độ phức tạp
T(n)=O(nlogn)
3.5.4. Ví dụ 2,3,5,6,4,1,5
Vun cây gốc A[3] được mảng A={2,3,7,6,4,1,5}
Vun cây gốc A[2] được mảng A={2,6,7,3,4,1,5}
Vun cây gốc A[1] được mảng A={7,6,5,3,4,1,2}
Bây giờ A={7,6,5,3,4,1,2} đã là đống.
Sắp xếp
Đổi chổ A[1] với A[7]: A={2,6,5,3,4,1,7} và vun lại mảng A[1 6] được mảng A={6,4,5,3,2,1,7}.
Đổi chổ A[1] với A[6]: A={1,4,5,3,2,6,7} và vun lại mảng A[1 5] được mảng A={5,4,2,3,1,6,7}
Đổi chổ A[1] với A[5]: A={1,4,2,3,5,6,7} và vun lại mảng A[1 4] được mảng A={4,3,2,1,5,6,7}
Đổi chổ A[1] với A[4]: A={1,3,2,4,5,6,7} vá vun lại mảng A[1 3] được mảng A={3,2,1,4,5,6,7}
Đổi chổ A[1] với A[3]: A={2,1,3,4,5,6,7} và vun lại mảng A[1 2] được mảng A={2,1,3,4,5,6,7}
Đổi chổ A[1] với A[2]: A={1,2,3,4,5,6,7}
Mảng còn lại chỉ một phần tử quá trình sắp xếp đã xong.
4.1. Java là gì?
Java là ngôn ngữ lập trình hướng đối tượng( tựa C++)
do Sun Microsystem đưa ra vào giữa thập niên 90.
Chương trình viết bằng ngôn ngữ java có thể chạy trên
bất kì hệ điều hành nào có cài máy ảo java( Java Vitual
Machine).
4. Giới thiệu về ngôn ngữ Java
4.2. Lịch sử phát triển

Ngôn ngữ lập trình Java do James Gosling và các công