Đếm số lần di chuyển “chuyển sang trước” tối thiểu để sắp xếp một mảng trong C ++

Chúng ta được cung cấp với một mảng số từ 1 đến n. Mục tiêu ở đây là tìm ra không. trong số các hoạt động 'chuyển tới trước' cần thiết để sắp xếp mảng đã cho. Mảng không có sự lặp lại. Thao tác 'chuyển sang trước' chọn một phần tử và đặt ở vị trí đầu tiên, ở đây là chỉ mục 0.

Chúng tôi sẽ duyệt qua mảng từ cuối, nếu phần tử ở đúng vị trí thì không cần di chuyển khác. Đối với các phần tử từ 1 đến n, vị trí chính xác trong mảng của phần tử arr [i] phải đánh bại chỉ số i + 1. arr [0] phải là 1, arr [1] phải là 2 và …… .arr [n-1] phải là n.

Đầu vào

Arr[]= { 4,3,2,1 }

Đầu ra

Minimum move-to-front operations: 3

Giải thích

Pull 3, 3,4,2,1 count=1
Pull 2, 2,3,4,1 count=2
Pull 1, 1,2,3,4 count=3

Đầu vào

Arr[]= { 6,1,2,5,4,3 }

Đầu ra

Minimum move-to-front operations: 5

Giải thích

Pull 5, 5,6,1,2,4,3 count=1
Pull 4, 4,5,6,1,2,3 count=2
Pull 3, ,4,5,6,1,2 count=3
Pull 2, 2,3,4,5,6,1 count=4
Pull 1, 1,2,3,4,5,6 count=5

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

• Mảng số nguyên Arr [] lưu trữ các số từ 1 đến n.

• Kích thước biến số nguyên lưu trữ độ dài của mảng Arr []

• Hàm movetoFront (int arr [], int n) nhận một mảng và độ dài của nó làm đầu vào và trả về số lượng tối thiểu các phép toán 'chuyển tới trước' cần thiết để sắp xếp mảng đã cho đó.

• Biến đếm được khởi tạo với kích thước của mảng vì tất cả các phần tử có thể được di chuyển trong trường hợp mảng thứ tự giảm.

• Bắt đầu đi ngang từ chỉ mục cuối cùng và di chuyển về phía trước, nếu giá trị của phần tử là cùng tên là số đếm, (đối với các phần tử được sắp xếp từ 1 đến n, n là cuối cùng, n-1 là thứ hai cuối cùng, v.v.) thì tính giảm dần khi phần tử đó là ở đúng vị trí.

• Theo cách này ở cuối vòng lặp, số đếm có kết quả mong muốn.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int movetoFront(int arr[], int n){
   //take count as all elements are correctly placed
   int count = n;
   // Traverse array from end
   for (int i=n-1; i >= 0; i--){
      // If current item is at its correct position,
         //decrement the count
      //range is 1 to n so every arr[i] should have value i+1
      //1 at 0 index, 2 at 1 index........
      if (arr[i] == count)
         count--;
   }
   return count;
}
int main(){
   int Arr[] = {5, 3, 4, 7, 2, 6, 1};
   int size = 7;
   cout <<"Minimum 'move-to-front' to sort array:"<< movetoFront(Arr, size);
   return 0;
}

Đầu ra

Minimum 'move-to-front' to sort array:6