Ta được cho một mảng; ta cần sắp xếp mảng này theo thứ tự mà phần tử đầu tiên là phần tử nhỏ nhất, phần tử thứ hai là phần tử lớn nhất, phần tử thứ ba là phần tử nhỏ thứ hai, phần tử thứ tư là phần tử lớn thứ hai và cứ thế. Ví dụ −
Input : arr[ ] = { 13, 34, 30, 56, 78, 3 } Output : { 3, 78, 13, 56, 34, 30 } Giải thích : mảng được sắp xếp lại theo thứ tự { 1st min, 1st max, 2nd min, 2nd max, 3rd min, 3rd max } Input : arr [ ] = { 2, 4, 6, 8, 11, 13, 15 } Output : { 2, 15, 4, 13, 6, 11, 8 }Phương pháp tìm giải pháp
Bài toán này có thể giải quyết dùng hai biến, 'x' và 'y' trỏ đến phần tử lớn nhất và nhỏ nhất, nhưng mảng phải được sắp xếp trước, vì vậy ta cần sắp xếp mảng trước. Sau đó tạo mảng rỗng mới cùng kích thước để lưu mảng đã sắp xếp lại. Bây giờ lặp qua mảng và nếu phần tử lặp ở chỉ số chẵn, thêm arr[x] vào mảng rỗng và tăng x lên 1. Nếu phần tử ở chỉ số lẻ, thêm arr[y] vào mảng rỗng và giảm y đi 1. Làm điều này cho đến khi y nhỏ hơn x.
Ví dụ
#include <bits/stdc++.h> using namespace std; int main () { int arr[] = { 2, 4, 6, 8, 11, 13, 15 }; int n = sizeof (arr) / sizeof (arr[0]); // tạo mảng mới lưu mảng đã sắp xếp lại. int reordered_array[n]; // sắp xếp mảng gốc sort(arr, arr + n); // biến trỏ đến chỉ số phần tử nhỏ nhất và lớn nhất. int x = 0, y = n - 1; int i = 0; // lặp qua mảng cho đến khi max nhỏ hơn hoặc bằng max. while (x <= y) { // nếu i chẵn thì lưu phần tử chỉ số max if (i % 2 == 0) { reordered_array[i] = arr[x]; x++; } // lưu phần tử chỉ số min else { reordered_array[i] = arr[y]; y--; } i++; } // in mảng đã sắp xếp lại. for (int i = 0; i < n; i++) cout << reordered_array[i] << " "; // hoặc cập nhật mảng gốc // for (int i = 0; i < n; i++) // arr[i] = reordered_array[i]; return 0; }Kết quả
2 15 4 13 6 11 8
Giải thích mã trên
- Biến khởi tạo x=0 và y = độ_dài_mảng(n) - 1.
- while( x<=y) duyệt mảng cho đến khi x lớn hơn y.
- Nếu đếm chẵn (x), phần tử được thêm vào mảng cuối, và biến x tăng 1.
- Nếu i lẻ, thì (y) phần tử được thêm vào mảng cuối, và biến y giảm 1.
- Cuối cùng, mảng đã sắp xếp lại lưu trong reordered_array[ ].
Kết luận
Trong bài viết này, ta thảo luận giải pháp sắp xếp lại mảng cho trước theo dạng nhỏ nhất, lớn nhất. Ta cũng viết chương trình C++ cho bài toán. Tương tự, ta có thể viết chương trình này bằng bất kỳ ngôn ngữ nào khác như C, Java, Python, v.v. Hy vọng bạn thấy bài viết hữu ích.