shaker_sort.cpp

void ShakerSort(int *a, int N)
{
    // Thuật toán cải tiến thuật toán sắp xếp nổi bọt
    // Bình thường khi ta sắp xếp nổi bọt, giả sử tăng dần
    // Thì phần tử nhỏ nhất sẽ được dồn về trái, dần dần cho đến hết.
    // Còn với thuật toán này ta sẽ dồn phần tử nhỏ nhất về trái, phần tử lớn lớn sang phải đồng thời
    int left, right, k;
 
    left = 0;
    right = N-1;
    k = N-1;
            
    while(left < right)
    {       
        for(int j = right; j > left; j--)
        {
            if(a[j] < a[j-1])
            { 
                swap(a[j], a[j-1]); 
                k = j;  
            }              
        }
        left = k;
 
        for (int j = left; j < right; j++)
        {  
            if (a[j] > a[j+1])
            { 
                swap(a[j], a[j+1]); 
                k = j;
            }    
        } 
        right = k;
    }
}