Chúng ta có một danh sách L, với n phần tử. Chúng ta phải kiểm tra xem danh sách có được sắp xếp theo cặp hay không. Giả sử danh sách giống như {8, 10, 18, 20, 5, 15}. Điều này được sắp xếp theo từng cặp như (8, 10), (18, 20), (5, 15) được sắp xếp. Nếu danh sách có số phần tử lẻ thì phần tử cuối cùng sẽ bị bỏ qua.
Cách làm quá đơn giản, lướt số từ trái sang phải. Hai phần tử liên tiếp được lấy và kiểm tra xem chúng đã được sắp xếp hay chưa, nếu có một cặp nào đó không được sắp xếp, hãy trả về false, nếu không tìm thấy cặp nào thì trả về true.
Ví dụ
#include <iostream>
#include <cmath>
using namespace std;
class Node{
public:
int data;
Node *next;
};
void append(struct Node** start, int key) {
Node* new_node = new Node;
new_node->data = key;
new_node->next = (*start);
(*start) = new_node;
}
bool isPairwiseSorted(Node *start) {
bool flag = true;
struct Node* temp = start;
while (temp != NULL && temp->next != NULL) {
if (temp->data < temp->next->data) {
flag = false;
break;
}
temp = temp->next->next;
}
return flag;
}
int main() {
Node *start = NULL;
int arr[] = {8, 10, 18, 20, 5, 15};
int n = sizeof(arr)/sizeof(arr[0]);
for(int i = 0; i<n; i++){
append(&start, arr[i]);
}
if(isPairwiseSorted(start)){
cout << "This is pairwise sorted";
} else {
cout << "This is not pairwise sorted";
}
} Đầu ra
This is pairwise sorted