Blog Archives

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

Tiếp theo giải thuật SelectionSort chúng tar bàn tiếp đến giải thuật Sắp xếp chèn trực tiếp – Insertion Sort.
Băt đầu nhé các bạn:

 Ý tưởng: Giả sử có 1 dãy a1 , a 2,…,an trong đó (i – 1) phần tử đầu tiên a1 , a 2,…, a(i-1) đã có thứ tự. Ý tưởng của giải thuật là tìm cách chèn phần tử a vào vị trí thích hợp của đoạn đã sắp xếp để có dãy mới a1 , a 2,…, ai đã có thứ tự. Cứ như thế các phần tử tiếp theo cho đến hết dãy. Vậy ta được 1 dãy sắp xếp.
Minh họa ví dụ Insertion sort 

 Cho dãy số a

 Bước 1: Dãy a0 -a0 đã có thứ tự. Cần chèn a1 vào dãy này để dãy vẩn có thứ tự

Bước 2: Dãy a1-a 0 đã có thứ tự. Cần chèn a2 vào dãy này để dãy vẫn có thứ tự

Bước 3: Dãy a2 -a0 đã có thứ tự. Cần chèn a3 vào dãy này để dãy vẫn có thứ tự

Bước 4: Dãy a3 -a0 đã có thứ tự. Cần chèn a 4 vào dãy này để dãy vẫn có thứ tự

Bước 5: Dãy a4 -a0 đã có thứ tự. Cần chèn a5 vào dãy này để dãy vẫn có thứ tự

Bước 6: Dãy a5 -a0 đã có thứ tự. Cần chèn a6 vào dãy này để dãy vẫn có thứ tự

Bước 7: Dãy a6 -a0 đã có thứ tự. Cần chèn a7 vào dãy này để dãy vẫn có thứ tự

Cài đặt 

Mã nguồn PHP:
 void InsertionSort(int a[],int n)
{
for(int i=1;i<n;i++)
{
int x=a[i];
for(int j=i- 1;j>=0;j- -)
{
if(a[j]>x) a[j+1]=a[j];
else  break;
}
a[j+1]=x;
}
}

Một số bài làm lý thuyết để chúng tar làm quen với giải thuật này.

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

Insertion 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

Một số bài tập cho chúng tar cài đặt làm quen trên máy

 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 insertion 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ự.

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

Advertisements

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

Mình định viết chung bên Topic Interchang Sort,Nhưng thấy nếu viết chung thì nhìn bài viết của Topic rất là dài,Và như vậy thì chúng ta thật sự rất ngại đọc,rối tung lên.Chính vì thế mình viết giải thuật tiếp theo ở đây.Thời điểm này,Mình sẽ viết tiếp Giải Thuật Chọn Trực Tiếp (Selection Sort)

Chúng ta bắt đầu nhé:

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

 Ý tưởng giải thuật 

Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí thứ 0 của dãy hiện hành; sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn (n – 1) phần tử, bắt đầu từ vị trí thứ 1; lặp lại quá trình đó trên dãy hiện hành … đến khi dãy hiện hành chỉ còn 1 phần tử thì dừng

Minh họa ví dụ Selection sort 
 Cho dãy số a:

 Bước 1: Tìm min của dãy số từ a0 – an-1 . Sau đó hoán đổi min với a0

 Bước 2: Tìm min của dãy số từ a1 – an-1 . Sau đó hoán đổi min với a1

 Bước 3: Tìm min của dãy số từ a2 – an-1 . Sau đó hoán đổi min với a2

 Bước 4: Tìm min của dãy số từ a3 – an-1 . Sau đó hoán đổi min với a3

 Bước 5: Tìm min của dãy số từ a4 – an-1 . Sau đó hoán đổi min với a4

 Bước 6: Tìm min của dãy số từ a5 – an-1 . Sau đó hoán đổi min với a5

 Bước 7: Tìm min của dãy số từ a6 – an-1 . Sau đó hoán đổi min với a6

Cài đặt

Mã nguồn:
void SelectionSort(int a[],int n)
{
for(int i=0;i<n- 1;i++)
{
int min=i;
for(int j=i+1;j<=n- 1;j++) //tìm min của dãy số
if(a[j]<a[min])         //từ ai   an-1
min=j;
swap(a[min],a[i]);
}
}

Các bài tập làm cho quen:
Ví dụ làm mô phỏng

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

Selection 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

—Phần 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 selection 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ự.

———–>Vậy là cơ bản xong về giải thuật Chọn trực tiếp(Selection Sort),Tiếp theo là chúng tar nghiên cứu tiếp đến giải Thuật Sắp xếp chèn trực tiếp – Insertion Sort .Mình sẽ viết tiếp nó ở phần Tiếp theo

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

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ã

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 

Mã nguồn :
 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.

Mã nguồn :
 Cài đặtint BinarySearch (int a[], int n, int x)
{
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ã