30/09/2018, 16:04

[Wiki] Sort cơ bản 1 - Insert Sort - Sắp xếp chèn

Ngồi rảnh rảnh nghiên cứu lại giải thuật đã bỏ từ lâu. Bắt đầu với Insert sort.

vi.wikipedia.org

Sắp xếp chèn

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp. Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu a 1 , . . . , a ...

Hình ảnh minh họa:

Coi video này để lấy ý tưởng về Insert sort
Video 1:

Video 2:

Code lại bằng C

#include <stdio.h>

int main()
{
    int length = 5;
    int array[] = {5,2,4,3,1};
    for(int unsorted_id = 1; unsorted_id < length; unsorted_id++) {
        int element = array[unsorted_id];
        int sorted_id = unsorted_id - 1;
        while(sorted_id >= 0 && element > array[sorted_id]) {
            array[sorted_id+1] = array[sorted_id]; // shift
            sorted_id--;
        }
        array[sorted_id+1] = element; // insert
    }

    //output
    for(int i = 0; i < length; ++i)
        printf("%d ", array[i]);
    return 0;
}

Độ phức tạp O(n2)

maivanquan viết 18:06 ngày 30/09/2018

hình như trong video này có nói cả O lớn đúng ko ạ , cái đó e chẳng hiểu gi . ko hiểu người ra tính kiểu gì luôn .

Nguyễn Minh Dũng viết 18:06 ngày 30/09/2018

Cũng có cách tính, trong bài này em có thể hiểu đơn giản là có 2 loop, mỗi loop có khả năng lặp lại đủ n lần. Nên sẽ có trường hợp xấu nhất là n^2 lần loop.

for(int unsorted_id = 1; unsorted_id < length; unsorted_id++) { // loop 1
           while(sorted_id >= 0 && element > array[sorted_id]) { // loop 2
        }
    }

Dựa vào đó người ta tính ra độ phức tạp là O(n2). Ngoài loop ta cũng có nhiều thao tác tính khác, nhưng khi n càng lớn thì chi phí cho các phép tính đó càng nhỏ. Nên cách đơn giản là tính số lần loop. Trong các bài khác anh sẽ giải thích độ phức tạp.

maivanquan viết 18:20 ngày 30/09/2018

A Đạt ơi , cái O lớn mình có cần phải để ý lắm trong lập trình ko ạ , và nó có ý nghĩa gì ạ .

Nguyễn Minh Dũng viết 18:14 ngày 30/09/2018

Hiện giờ nếu không cần thiết thì em không cần phải biết cách tính, em chỉ cần nhìn vào để biết là thuật toán nào chạy nhanh hơn trong trường hợp nào thôi. Cái này không khó, nhưng nó là một khái niệm lạ. Khi nào anh khỏe sẽ làm video nói về cái này.

Nhưng em có thể hiểu như trên anh đã giải thích O(n2) có nghĩa là với n phần tử, thì trong trường hợp xấu nhất ta cần n^2 lần lặp để sắp xếp toàn bộ mảng này.

Có những thuật toán tốt hơn. Ví dụ merge sort có độ phức tạp O(n log n). Với log ở đây là log bậc 2, anh quên cách đọc chính xác là cơ số 2 hay bậc 2, ai biết đính chính dùm. Có nghĩa là với trường hợp xấu nhất ta cần n log n lần lặp để sắp xếp mảng này. Khi n càng lớn, thì tốc độ của merge sort càng nhanh hơn so với Insert Sort. Anh lấy ví dụ của n = 10^6 đi.

Insert sort: n^2 = (10^6)^2 = 10^12 lần
Merge sort: n log n = (10^6) log 10^6 = 10^6*19 (vì log2(10^6) cỡ 19.xx)

Nhìn sơ qua là thấy Merge sort nhanh hơn rồi đúng không

Nguyễn Đình Dũng viết 18:16 ngày 30/09/2018

E thêm cho cái video này nữa này

Nguyễn Minh Dũng viết 18:07 ngày 30/09/2018

@DungJun, em có thể edit post 1, bỏ video đó của em vào. Anh thấy hay đấy.

Phạm Hà Lâm viết 18:14 ngày 30/09/2018

em chạy thử 2 vòng lặp for bị báo lỗi ạ!!!

Nguyễn Minh Dũng viết 18:10 ngày 30/09/2018

2 vòng lặp for như thế nào em?

Phạm Hà Lâm viết 18:18 ngày 30/09/2018