Blog Archives

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

Advertisements