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

ltd · May 2, 2015, 3:25am

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.

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)

maiquan · November 2, 2014, 5:45pm

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 .

ltd · November 3, 2014, 12:51am

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.

maiquan · November 3, 2014, 2:45pm

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ì ạ .

ltd · November 3, 2014, 3:20pm

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

DungJun · November 30, 2014, 2:26am

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

ltd · November 30, 2014, 2:39am

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

phamhalam · December 1, 2014, 3:05pm

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

ltd · December 1, 2014, 3:51pm

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

phamhalam · April 1, 2015, 1:20pm

lỗi c99 mode ở 2 lệnh for ạ???

nhatlonggunz · December 3, 2014, 7:31am

bạn thử làm theo ở phút 2:30 xem

ltd · December 3, 2014, 7:30am

Làm theo hướng dẫn của @nhatlonggunz là được nhé.

VinhTuongBK10 · October 17, 2015, 3:27pm

Lỗi là do bạn xài code::block
bạn phải khai báo như thế này mới không bị lỗi:

int I;
for (I =0; I< ; I++)

phải khai báo int I ở ngoài mới được nhé. ^^ @phamhalam