Đếm các dòng chéo trong một mảng trong C ++

Chúng ta được cung cấp với một mảng các phần tử riêng biệt chưa được sắp xếp. Mục đích là để tìm các dòng chéo sau khi mảng được sắp xếp. Các đường chéo được tính như hình dưới đây -

• Arr [] ={1,2,4,3,5} Có 3 đường chéo như hình dưới đây

• Arr [] ={1,2,3,4,5}. Không có đường chéo nào vì mảng đã được sắp xếp.

Chúng tôi sẽ đếm các dòng chéo bằng cách sử dụng sắp xếp chèn trong đó một phần tử từ bên phải được thêm vào các phần tử được sắp xếp ở bên trái của nó. Mỗi lần phần tử được thêm vào phần đã sắp xếp, số gia tăng khi phần tử đó di chuyển đến đúng vị trí của nó. Nó sẽ vượt qua bằng cách vượt qua tất cả các yếu tố lớn hơn.

Hãy cùng hiểu với các ví dụ.

Đầu vào - arr [] ={4,3,1,2}

Đầu ra - Đếm số dòng chéo trong mảng - 5

Giải thích - Đường 4-4 ​​và 3-3 cắt các đường 1-1 và 2-2. Tổng số 4 đường chéo.

Cả 4-4 và 3-3 đều chéo nhau một lần. Tổng 4 + 1 =5 đường chéo.

Đầu vào - arr [] ={0,1,5,3}

Đầu ra - Đếm số dòng chéo trong mảng - 1

Giải thích - Cả 5-5 và 3-3 chéo nhau một lần. Tổng số 1 đường chéo.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Chúng tôi lấy một mảng số nguyên arr [] được khởi tạo với các số riêng biệt.

• Hàm inserttionSort (int arr [], int n) nhận một mảng và độ dài của nó làm đầu vào và sau khi sắp xếp nó trả về kết quả là số lượng các dòng chéo.

• Lấy đầu tiên không có dòng chéo nào là 0. Biến đếm được sử dụng.

• Phần tử đầu tiên đã được sắp xếp, vì vậy bắt đầu từ phần tử thứ hai cho đến hết (i =1 đến i

• Bây giờ chuyển tất cả các phần tử sang phải nếu chúng> item và j> 0. Đối với mỗi số gia tăng ca vì tất cả chúng được gạch chéo theo mục.

• Ở cuối vòng lặp while, hãy đặt mục vào đúng vị trí của nó là arr [j + 1].

• Làm điều này cho tất cả các phần tử và đếm các phần tử mà chúng giao nhau.

• Giá trị gia tăng của số đếm là không. trong số các đường chéo có thể.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int insertionSort(int arr[], int n){
   int count=0;
   int item;
   int j;
   for (int i = 1; i < n; i++){
      item = arr[i];
      j = i - 1;
      //insert element at correct position in sorted part, no. of elements it passes
      //from right till correct position is count of cross lines.
      while (j >= 0 && arr[j] > item){
         arr[j + 1] = arr[j];
         j = j - 1;
         count++;
      }
      arr[j + 1] = item;
   }
   return count;
}
int main(){
   int arr[] = { 4,5,3,1,2};
   int n = 5;
   cout<<"Number of cross lines: "<<insertionSort(arr, n);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Number of cross lines: 8