Blog Archives
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
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
}{
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ã
Một số giải thuật cơ bản Phần 1
Đây là các loại bài về Cấu Trúc dữ liệu cơ bản mà mình sẽ viết chia sẽ với các bạn .Loạt bài này nói về Các giải thuật cơ bản,bao gồm:các giải thuật tìm kiếm trên mảng số và Các giải thuật sắp xếp.
Chúng tar bắt đầu tìm hiểu về giải thuật tìm kiếm.(các giải thuật cài đặt trên C/C++)
I Giải thuật tìm kiếm trên mảng số
1. Tìm kiếm tuyến tính (Linear Search)
Ý tưởng:
-Thuật toán tiến hành so sánh x lần lượt với các phần tử thứ 1, thứ 2,… của mảng a cho đến khi gặp phần tử có khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x.
Ví dụ: Cho dãy số sau:
5 3 6 8 9 1 2
–>Tìm phần tử có giá trị x = 9, x= 10 ???
Minh họa ví dụ
Xét dãy số A có 7 phần tử:
5 3 6 8 9 1 2
Tìm x = 9
Tìm x = 10.Tương tự (Các bạn tự làm thử nhé)
Cài đặt
int LinearSearch (int a[], int n, int x)
{
for(int i=0;i<n;i++)
if(a[i]==x)
return i; // trả về vị trí của x trong a
return - 1; // trả về -1 báo là không có x trong a
}
2. Thuật toán tìm kiếm nhị phân (Binary Search)
Ý tưởng
– Giả sử dãy số a đã có thứ tự tăng.
– Tại mỗi bước tiến hành so sánh x với phần tử nằm vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm ở bước kế tiếp là nửa trên hay nửa duới của dãy tìm kiếm hiện hành.
Ví dụ:
– Cho dãy a có 7 phần tử: 3 4 6 8 9 10 13
– Tìm x = 10 và x = 2 ???
Minh họa ví dụ
– Cho dãy số a: 3 4 6 8 9 10 13
tìm x= 10.
Cài đặt{
int left = 0, right = n- 1;
while(left<=right)
{
int mid = (left + right)/2;
if(a[mid] == x)
return mid;
else
if( a[mid]<x) left = mid+1;
else right = mid- 1;
}
return – 1;
Bài Tập Làm Cho Quen:
*Bài tập lý thuyết
Cho dãy số sau:
7 9 13 17 27 30 31 35 38 40
a. Tìm x= 17, x=35, x=40
b. Tìm x = 23, x=10, x=36
Cho dãy ký tự
Z R L K H F E C A
a. Tìm x = R, x = C
b. Tìm x = D, x = Q
*Bài tập thực hành
Cho mảng 1 chiều a chứa n số nguyên. Viết chương trình thực hiện các
yêu cầu sau:
1. Viết hàm nhập/xuất mảng a.
2. Tìm max/min của a.
3. Đếm số phần tử chẵn/lẻ trong a.
4. Tìm kiếm phần tử x trong a theo 2 dạng ( trả về vị trí/xuất câu thông
báo) với giải thuật tìm kiếm tuyến tính/ tìm kiếm nhị phân.
5. Tìm trên a có bao nhiêu phần tử x.
Đến đây cơ bản là xong 2 giải thuật tìm kiếm cơ bản.Chúng tar cùng nhau thảo luận nhé.Phần tiếp theo là các giải thuật sắp xếp,mình sẽ viết nó ở phần sau(Phần 2)
Phần 2:
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
Phần tiếp theo sẽ được viết trong thời gian sớm nhất. Hy vọng giúp ít cho các bạn.
Tác giả : Trần Thanh Nhã
I like Programming 