Simple coding : [Algorithm] Các thuật toán sắp xếp cơ bản

Các thuật toán sắp xếp cơ bản.

Sắp xếp là một bài toán rất quan trọng trong các lĩnh vực khoa học, ví dụ khi ta có một nhóm sinh viên và muốn sắp xếp nhóm theo thứ tự tăng dần về điểm thi hay ngân hàng muốn sắp xếp tên khách hàng theo alpha belta ,… . Vì thế thuật toán sắp xếp luôn được nghiên cứu và tìm cách phát triển. Trong bài này ta tìm hiểu một vài thuật toán tìm kiếm đơn giản.

Các bài toán sắp xếp có đối tượng gồm một hoặc nhiều bản ghi, trong đó có một trường thể hiện quan hệ thứ tự nó được gọi là khóa (key). Mảng các đối tượng trên là danh sách cần sắp xếp, mục đích của việc sắp xếp là tổ chức lại danh sách trên. Các bài toán sắp xếm cơ bản thường có độ phức tạp là O(n²) .

I. Selection sort
- Đây có lẽ là thuật toán dễ nhìn nhất, nó được miêu tả đơn giản như sau: (Pascal)
            + Đầu tiên ta chọn phần tử nhỏ nhất trong n phần tử từ a[1] đến a[n] sau đó gán cho a[1].
            + Tiếp theo ta tìm phần tử nhỏ nhất trong n – 1 phần tử đầu tiên rồi gán cho a[2].
            + Tổng quát ở bước thứ i ta tìm phần tử nhỏ nhất trong n – i + 1 phần tử trong a[i] đến a[n]
            + Cứ như vậy ta cần n - 1 bước để được một mảng sắp xếp giảm dần.

Ví dụ: Cho một mảng các số 1 4 5 2 9 3. Sắp xếp chúng giảm dần. (C++)
            Ta có mảng a[] = {1, 4, 5, 2, 9, 3};
            Bước 1: Ta tìm phần tử nhỏ nhất trong trong a[0] đến a[5] rồi gán giá trị cho a[0]
            Bước i : ta tìm phần tử nhỏ nhất từ a[i] đến a[5] rồi gán giá trị đó cho a[i].

Code :
Đoạn code dưới đây bằng C++ sắp xếp một mảng giảm dần.
#include <iostream>

int main(){

int a[] = {1, 4, 5, 2, 9, 3};

int lowData, lowIndex;

for(int i = 0; i < 6 - 1; i++){

for(int j = i + 1; j < 6; j++){

if(a[i] < a[j]){

lowData = a[j];

lowIndex = j;

}

int tmp = a[lowIndex];

a[lowIndex] = a[i];

a[i] = a[lowIndex];

}

// Print data after sorted.

for(int i = 0; i < 6 - 1; i++){

std::cout << a[i] << " ";

}

return 0;

}
Vd 2: Sắp xếp lớn dần mảng kí tự “abdfg”.

#include <iostream>

#include <cstring>

int main(){

std::string a = "abdfg";

int lowIndex;

char lowData;

for(int i = 0; i < a.length() - 1; i++){

for(int j = i + 1; j < a.length(); j++){

if(a[i]< a[j]){

lowData = a[j];

lowIndex = j;

}

char tmp = a[i];

a[i] = a[lowIndex];

a[lowIndex] = tmp;

}

std::cout << a;

return 0;

}

Ta xét đoạn code sau để tìm độ phức tạp của bài toán:
1. for(int i = 0; i < 6 - 1; i++){

2. for(int j = i + 1; j < 6; j++){

3. if(a[i] < a[j]){

4. int tmp = a[i];

5. a[i] = a[j];

6. a[j] = tmp;

7. }

8. }

9. }

Dễ thấy đoạn code sau có hai vòng for lông nhau từ dòng 2 - 6 chạy n - i lần nhóm câu lệnh có độ phức tạp O(1). Như vậy thời gian tổng cộng là:
T(n) = (n - 1)*n/2 =O(n²)

* Ưu điểm của thuật toán trên là dễ nhìn dễ hiểu, còn nhược điểm là chạy lâu, tốn thời gian

II, Insertion sort

Có một thuật toán được xem ngang với selection sort đó là Insertion sort, được hiểu đơn giản như sau:
Nếu ta có một dãy các số nguyên, muốn sắp xếp tăng dần
B1: Ta bắt đầu xét từ vị trí thứ 2, xen phân tử thứ 2 vào danh sách đứng trước nó ( tức là phần tử đầu ). Nếu a[2] nhỏ hơn a[1] thì hoán đổi 2 vị trí thằng này.

B2: Xen phần tử thứ 3 vào danh sách đứng trước nó, tức là 2 phần tử đầu. Nếu a[3] < a[2] hoán đổi vị trí 2 cái này, nếu a[2] nhỏ hơn a[1] lại hoán đổi hai vị trí. Tức là nó tìm đến vị trí phù hợp với nó là phần tử đứng sau nhỏ hơn nó rồi chèn vào đó.

B3: Cứ tương tự như vậy ta chèn phần tử a[i] vào danh sách a[1] đến a[i -1].

Ta có code sau được viết bằng C++:

- 18/3/2016

- argc count number argument

- argv is value of argument

- demo insertion sort

#include <iostream>

#include <cstdlib>

// - function print elements of arr

// - argument arr is array need to be printed

// - argument num is number of arr 's element.

void printArr(int arr[], int num);

// - function sort.

void insertion(int arr[], int num);

int main(int argc, char** argv){

const int MAX = 10;

int arr[MAX];

for(int i = 0; i < argc - 1; i++){

arr[i] = atoi(argv[i + 1]);

}

printArr(arr, argc - 1);

insertion(arr, argc - 1);

std::cout << std::endl;

printArr(arr, argc - 1);

return 0;

}

void printArr(int arr[], int num){

for(int i = 0; i < num; i++){

std::cout << arr[i] << " ";

}

void insertion(int arr[], int num){

for(int i = 1; i < num; i++){

int j = i, v = arr[i];

while(j > 0 && arr[j - 1] > v){

//int tmp = arr[j];

//arr[j] = arr[j - 1];

//arr[j - 1] = tmp;

arr[j] = arr[j - 1];

j--;

//printArr(arr, i);

//std::cout << std::endl;

}

arr[j] = v;

}

- Đây là hàm ta cần xét :

void insertion(int arr[], int num){

for(int i = 1; i < num; i++){

int j = i, v = arr[i];

while(j > 0 && arr[j] < arr[j - 1]){

//int tmp = arr[j];

//arr[j] = arr[j - 1];

//arr[j - 1] = tmp;

arr[j] = arr[j - 1];

j--;

}

arr[j] = v;

}

Xét while(j > 0 && arr[j - 1] > v ) ta thấy j > 0 đây được coi là chốt chặn ngăn ngừa việc xét ra ngoài mảng, arr[j - 1] > v tìm xem đã có chỗ chèn phù hợp cho v hay chưa. Nếu chưa ta có : arr[j] = arr[j - 1]; j--; Tức là đẩy dần các phần tử lên phía bên phải để lấy chỗ chèn. Cuối cùng là bước chèn khi đã tìm được chỗ hợp lý : arr[j] = v; Trước đó ta đã lưu giá trị cần chèn: v = arr[i]; .

Nói chung thuật đơn giản được mô tả thể này: Ta sắp xếp phần tử thứ k thì ta đi tìm chỗ cần chèn phù hợp cho nó trong k - 1 phần tử đằng trước đã sắp xếp, sau đó đẩy dãy từ điểm chèn đến điểm đang xét sang một nấc bên phải rồi chèn phần tử đó vào.

Ta nhận thấy độ phức tạp ở đây tương tự như selection sort là O(n2).

Nhược điểm cũng giống selection sort là không dùng được cho dữ liệu lớn.
Bạn có thể tham khảo thêm ở: https://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_ch%C3%A8n

III, Bubble sort
Có một phương pháp linh hoạt và được dạy khá nhiều trong trường lớp đó là sắp xếp nổi bọt (bubble sort). Ta hãy tưởng tượng các bong bóng bất kì được để dọc, tượng trưng cho một mảng bất kì. Khi đó phương pháp này được hình dung là: Cứ quả nào nhẹ hơn thì nó nổi lên trên đầu.

Ta có một mảng arr với n phần tử, ta có các bước để giải quyết bài toán tăng dần:
B1: duyệt từ n đến 1, nếu phần tử đứng trước i lớn hơn phần tử đứng sau i + 1 thì hoán đổi vị trí cho nhau. Sau vòng này thì ở vị trí 1 sẽ được số nhỏ nhất
B2 : Duyệt tương tự đến khi còn 1 phần tử hoặc trong vòng duyệt không cần đổi chỗ bất cứ phần tử nào.

Code :

/*

- 18/3/2016

- argc count number argument

- argv is value of argument

- demo insertion sort

#include <iostream>

#include <cstdlib>

// - function print elements of arr

// - argument arr is array need to be printed

// - argument num is number of arr 's element.

void printArr(int arr[], int num);

// - function sort.

void bubble(int arr[], int num);

int main(int argc, char** argv){

const int MAX = 10;

int arr[MAX];

for(int i = 0; i < argc - 1; i++){

arr[i] = atoi(argv[i + 1]);

}

printArr(arr, argc - 1);

bubble(arr, argc - 1);

std::cout << std::endl;

printArr(arr, argc - 1);

return 0;

}

void printArr(int arr[], int num){

for(int i = 0; i < num; i++){

std::cout << arr[i] << " ";

}

void bubble(int arr[], int num){

int f = 1;

for(int i = 0; i < num - 1; i++){

f = 1;

for(int j = num; j > i; j--){

if(arr[j] < arr[j - 1]){

//swap

int tmp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = tmp;

f = 0;

}

if(f) break;

}

Độ phức tạp của thuật toán này là O(n^2). Ưu điểm của thuật này là nếu trong một vòng lặp mà không cần hoán đổi bất cứ vị trí thằng nào thì thoát ra.

Simple coding

Lập trình

Thứ Sáu, 18 tháng 3, 2016

[Algorithm] Các thuật toán sắp xếp cơ bản

Không có nhận xét nào:

Đăng nhận xét

Tổng số lượt xem trang