In mảng theo thứ tự tăng dần

Đề bài: 

Nhập một số n và dãy số thực a0, a1, ..., an-1. Không đổi chỗ các phần tử và không dùng thêm mảng số thực nào khác(Có thể sử dụng mảng số nguyên nếu cần). Hãy cho hiện lên màn hình dãy trên theo thứ tự tăng dần.

Thông thường khi thực hiện bài toán sắp xếp ta sẽ sử dụng các thuật toán như Bubble sort, Quick sort hay Merge sort, ...Nhưng ở đây yêu cầu là không được đổi chỗ các phần tử và không được sử dụng thêm mảng số thực khác lên ta cần phải nghĩ một phương pháp khác.

Sắp xếp sử dụng mảng vị trí

Một cách đơn giản nhất theo như gợi ý đó là sử dụng thêm một mảng số nguyên. Ta sẽ sử dụng mảng số nguyên này để lưu vị trí các phần tử. Khi tiến hành sắp xếp mảng số thực, ta sẽ không thay đổi vị trí các phần tử của mảng số thực mà thay vào đó sẽ thay đổi vị trí các phần tử của mảng số nguyên này.

void sapXep(float x[], int n) {
    int temp;
    int pos[n];
    for(int i = 0; i < n; i++) { //Khởi tạo gía trị cho mảng vị trí
        pos[i] = i;
    }
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {
            //Ta sẽ duyệt mảng x qua giá trị của mảng pos
            if(x[pos[i]] > x[pos[j]]) {
                temp = pos[i];   
                pos[i] = pos[j];
                pos[j] = temp;
            }
        }
    }
}

Sau khi sắp xếp ta thu được một mảng số nguyên(pos) lưu vị trí các phần tử của mảng số thực đã qua sắp xếp. Việc còn lại chỉ là in ra mảng số thực với chỉ số chạy là giá trị của mảng vị trí.

for(int i = 0; i < n; i++) {
        cout<<x[pos[i]]<<endl;
 }

Dowload source code

Sắp xếp mảng sử dụng min, max

Nếu không muốn phải sử dụng thêm một mảng vị trí như trên, có một cách khác đó là sử dụng hai giá trị min, max của mảng để in ra theo thứ tự đã sắp xếp.

Ta sẽ sử dụng thêm hai hàm, một hàm tìm giá trị max, hàm còn lại tìm vị trí của phần tử min. Sau đó đặt vào một vòng lặp duyệt hết độ dài của mảng, mỗi lần lặp sẽ in ra giá trị của phần tử nhỏ nhất và gán nó bằng phần tử có giá trị lớn nhất. Vì giá trị các phần tử trong mảng sẽ luôn nhỏ hơn giá trị max lên sẽ đảm bảo không có phần tử nào được in 2 lần.

VD có một mảng A có 3 phàn từ:

               A[] = {1 6 2}      =>       max(A) = 6

Lần duyệt 1:  min_pos = 0
   + In ra màn hình: 1
   + Mảng mới: A[] = {6, 6, 2}

Lần duyệt 2: min_pos = 2
   + In ra màn hình: 2
   + Mảng mới: A[] = {6, 6, 6}

Lần duyệt 3: min_pos = 1
   + In ra màn hình: 6
   + Mảng mới: A[] = {6, 6, 6}

Vậy ta đã thu được dãy số đã qua sắp xếp: 1  2  6

void sapXep(float x[], int n) {
    cout<<"Day sau khi sap xep la: ";
    for(int i = 0; i < n; i++) {
        cout<<x[min_pos(x, n)]<<" "; //In ra phần tử nhỏ nhất
        x[min_pos(x, n)] = max(x, n); //Gán gíá trị cho phần tử nhỏ nhất bằng phần tử lớn nhất
    }
}

Dowload source code