透過交換相鄰元素對 1 到 N 進行排序

---

陣列是一種線性資料結構，用於儲存元素，而排序陣列則按升序包含所有元素。透過交換相鄰元素對陣列進行排序意味著我們可以任意次數交換相鄰元素，並且必須對陣列進行排序。我們將得到兩個陣列，第一個陣列是要排序的陣列，另一個數組是布林陣列，表示當前元素是否可交換。

如果給定陣列的長度為 N，則所有存在的元素都將是從 1 到 N。

輸入

Given array:   1 2 4 3 5 7 6 
Boolean array: 0 1 1 1 0 1 1 

輸出

Yes, we can sort the array. 

解釋

我們可以交換 3 和 4，因為它們是可交換的，並且我們可以交換 6 和 7。

輸入

Given array:   1 2 4 3 5 7 6 
Boolean array: 0 1 1 1 0 1 0 

輸出

No, we cannot sort the array. 

解釋

我們可以交換 3 和 4，因為它們是可交換的，但我們不能交換 6 和 7，這使得該陣列未排序。

樸素方法

在這種方法中，我們將遍歷陣列，並將遍歷布林陣列。如果當前索引是可交換的，那麼我們將遍歷到最後一個可交換索引，並使用排序函式對所有元素進行排序。最後，我們將檢查陣列是否已排序。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if the current array is sorted or not 
bool isSorted(int arr[], int n){    
   // traversing over the array 
   for(int i =1; i<n ;i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   // traversed over the whole array means sorted 
   return true;
}
// function to swap the elements of the array 
bool check(int arr[], bool brr[], int n){
	// traversing over the boolean array 
	for (int i = 0; i < n - 1; i++) {
		if (brr[i] == 1){
			int j = i;
			while (brr[j] == 1){
			   j++;
			}			
			// using sort function sort the array 
			sort(arr + i, arr + 1 + j);
			i = j; // updating the value of i
		}
	}

	return isSorted(arr, n);
}
int main(){
	int arr[] = { 1, 4, 2, 3, 5, 7, 6};
	bool brr[] = { 0, 1, 1, 1, 0, 1, 1 };
	int n = sizeof(arr) / sizeof(arr[0]); // getting the size of array    
	if(check(arr, brr, n)){
	   cout<<"Yes, the given array can be sorted"<<endl;
	}
	else{
	   cout<<"No, the given array cannot be sorted"<<endl;
	}    
   return 0;
}

輸出

No, the given array cannot be sorted

時間和空間複雜度

上面程式碼的時間複雜度為 O(N*log(N))，其中 N 是給定陣列的大小。

上面程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。

方法 2

在這種方法中，我們將遍歷給定陣列，並檢查當前元素是否不在其排序位置且不可交換，如果不可交換，則返回 false。否則，我們將獲取當前點到下一個不可交換索引或陣列末尾的所有可交換元素的資料。如果該範圍內存在的元素少於或多於當前範圍，我們將返回 false，否則在最後我們可以返回 true。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check the array can be sorted by swapping 
bool check(int arr[], bool brr[], int n){    
   int notAtPlace = 0; // variable to store elements that are not at place 
   int swappable = 0; // variable to store total elements that are swappable    
	// traversing over the Boolean array 
	for (int i = 0; i < n ; i++) {
	   if(arr[i] != (i+1) && brr[i] == 0) return false;	    
		if (brr[i] == 1 && arr[i] != i+1){
			int j = i;			
			//variable to get the maximum swappable value 
			// variable to get the minimum swappable value
			int mx = arr[i]-1;
			int mi = arr[i]-1;			
			while(j < n && brr[i] == 1){
			   mx = max(mx, arr[j]-1);
			   mi = min(mi, arr[j]-1);
			   j++;
			}
			if(mx > j || mi < i){
			   return false;
			}
			i = j-1;
		}
	}
   // traversed over the whole array means possible to sort
	return true;
}
int main(){
	int arr[] = { 1, 4, 2, 3, 5, 7, 6};
	bool brr[] = { 0, 1, 1, 1, 0, 1, 1 };
	int n = sizeof(arr) / sizeof(arr[0]); // getting the size of array     
	if(check(arr, brr, n)){
	   cout<<"Yes, the given array can be sorted"<<endl;
	}
	else{
	   cout<<"No, the given array cannot be sorted"<<endl;
	}    
   return 0;
}

輸出

Yes, the given array can be sorted

時間和空間複雜度

上面程式碼的時間複雜度為 O(N)，其中 N 是給定陣列的大小，因為我們只遍歷陣列一次。

上面程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。

結論

在本教程中，我們實現了一個程式，用於查詢給定陣列是否可以透過交換可交換的相鄰元素進行排序。另一個數組將提供任何陣列是否可交換。我們實現了兩種方法，一種具有 O(N*log(N)) 時間和 O(1) 空間複雜度，而另一種具有相同空間複雜度，但時間複雜度提高到 O(N)。