Về ba đoạn code sort

Kha_Nam1 · October 9, 2018, 2:02pm

Mọi người cho mình hỏi 3 cách này là thuật toán sắp sếp nổi bọt, về bản chất là nó giống nhau đúng k ạ? Và nếu khác thì khác ở đâu?

Cách 1

for (i =0; i< n-1; i++)
    for (j =n-1; j>i; j--)
    {
        if(a[i]>a[j])
        {
            tg = a[i];
            a[i] = a[j];
            a[j] = tg;
        }
    }

Cách 2:

for(int i=0;i<n-1;i++)
    for(int j=i+1;j<n;j++)
    {
        if(a[i]>a[j])
        {
            tg = a[i];
            a[i] = a[j];
            a[j] = tg;
        }
    }

Cách 3

for (i=0; i<n; i++)
{
    int tg;
    for ( int j = 0; j<n; j++)
        if( a[i] < a[j] )
        {
            tg = a[i];
            a[i] = a[j];
            a[j] = tg;
        }
}

rogp10 · October 9, 2018, 1:47pm

Cả 3 đoạn code đều KHÔNG phải là Bubble sort

Kha_Nam1 · October 9, 2018, 1:49pm

Mình mới học C, mình chỉ thắc mắc ở phần 2 vòng lặp for, bạn giải thích giúp mình nhé

vanhieu · October 10, 2018, 7:46am

Cả 3 đoạn code đều là selection sort(Sắp xếp chọn).

2 đoạn đầu: Dòng for sau suy cho cùng vẫn duyệt các phần tử từ [i+1, n].
Đoạn code thứ 3 chỉ là code tham lam hơn, nó vẫn là selection sort. Thay vì for từ [i+1, n] thì lại for từ [0, n]. Trong trường hợp này, các bước lặp từ [0,i] là vô nghĩa. So sánh với đoạn code 2 là biết.

Thuật toán sắp xếp này có độ phức tạp là O(n^2)

Một số tài liệu này sẽ giúp bạn học các thuật toán sắp xếp dễ dàng hơn:

https://visualgo.net/en/sorting
http://bigocheatsheet.com
https://nguyenvanhieu.vn/tag/thuat-toan-sap-xep/