Một số giải thuật cơ bản Phần 2_Interchange Sort

Tiếp tục phần 2 nhé các bạn.

II CÁC GIẢI THUẬT SẮP XẾP 

(Các thuật toán minh họa sắp xếp dãy không tăng trên mảng 1 chiều chứa dữ liệu là các số nguyên)

– Sắp xếp là quá trình xử lý một danh sách các phần tử để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu trữ tại mỗi phần tử.

+Các phương pháp sắp xếp thông dụng
2.1. Sắp xếp đổi chỗ trực tiếp – Interchange Sort

2.2. Sắp xếp chọn trực tiếp – Selection Sort

2.3. Sắp xếp chèn trực tiếp – Insertion Sort

2.4. Sắp xếp Nổi bọt – Bubble Sort
Và còn 1 số giải thuật khác như : Merge Sort,Bucket Sort,Heap Sort….Nhưng ở đây tar chỉ bàn luận về những vấn đề cơ bản nhất.
===========================================
Bắt Đâu
2.1. Sắp xếp đổi chỗ trực tiếp – interchange Sort 

 Khái niệm nghịch thế: 
– Xét dãy các số a: a1 , a2 , … an với a là dãy không giảm.

Nếu i<j và aj >ai thì ta gọi đó là 1 nghịch thế.

 Ví dụ: Cho dãy số a như sau:
14 5 7 8 3.
Vậy dãy trên trên có các cặp nghịch thế sau: (14, 5); (7, 3); (8, 3) ….

 Ý tưởng thuật toán: 

Xuất phát từ đầu dãy, lần lượt xét từng phần tử cho đến cuối

dãy. Tại mỗi phần tử tìm tất cả nghịch thế chứa phần tử này,

đổi chỗ phần tử này với các phần tử trong cặp nghịch thế.
Minh Họa Giải Thuật:
—Cho dãy số:

* Bước 1: Xem nghịch thế của phần tử thứ 0 – a0

* Bước 2: Xem nghịch thế của phần tử thứ 1 – a1

* Bước 3: Xem nghịch thế của phần tử thứ 2 – a2

* Bước 4: Xem nghịch thế của phần tử thứ 3 – a3

* Bước 4: Xem nghịch thế của phần tử thứ 3 – a3 tiếp theo

* Bước 5: Xem nghịch thế của phần tử thứ 4 – a4

* Bước 5: Xem nghịch thế của phần tử thứ 4 – a4 tiếp theo

* Bước 6: Xem nghịch thế của phần tử thứ 5 – a5 tiếp theo

* Bước 7: Xem nghịch thế của phần tử thứ 6- a6 tiếp theo

Cài đặt 

Mã nguồn :

void Interchangesort(int a[],int n)
{
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(a[i]>a[j])
swap(a[i],a[j]); //ham hoan doi gia
//tri 2 so nguyen
}void swap(int &x, int &y)
{
int t = x;
x = y;
y = t;
}

Vậy cơ bản là xong giải thuật Đổi chổ trực tiếp(Interchang Sort).Các bạn cài đặt thử và chạy nhé.
—Một số bài tập cơ bản để làm và hiểu rỏ hơn về giải thuật này.

Bài tập cài đặt 

 Viết bổ sung các hàm vào chương trình xử lý mảng 1 chiều

các hàm thực hiện những yêu cầu sau:

1. Viết hàm sắp xếp tăng theo PP interchange sort cho dữ liệu

số nguyên/số thực/ký tự/ chuỗi ký tự.

2. Viết hàm sắp xếp tăng theo PP interchange sort cho dữ liệu

số nguyên/số thực/ký tự/ chuỗi ký tự.

 Minh họa thao tác sắp xếp dữ liệu theo phương pháp

interchange Sort cho các dãy dữ liệu sau:

 Sắp xếp tăng:

 13 8 12 6 9 10 12 7

 A H K R E C Z G

 Sắp xếp giảm

 13 8 12 6 9 10 12 7

 A H K R E C Z G
Chúc các bạn làm tốt.
==================================================
Tiếp theo là đến giải thuật: 2.2. Sắp xếp chọn trực tiếp – Selection sort 
Có thời gian Mình sẽ viết lên sớm nhất,để cho các bạn tham khảo.waiting………………

Tác giả : Trần Thanh Nhã