C++ Online Compiler
Example: Block Swap Array Rotation in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// Block Swap Array Rotation #include <iostream> #include <vector> // For std::vector #include <algorithm> // For std::swap // Helper function to print the array void printArray(const std::vector<int>& arr) { for (int x : arr) { std::cout << x << " "; } std::cout << std::endl; } // Helper function to swap two blocks of 'len' elements // starting at index 'i' and 'j' respectively. void swapBlocks(std::vector<int>& arr, int i, int j, int len) { for (int k = 0; k < len; ++k) { std::swap(arr[i + k], arr[j + k]); } } // Recursive function to perform block swap rotation // current_start_idx: The starting index of the current sub-array segment // current_len: The total length of the current sub-array segment // d: The number of positions to rotate by within this segment void _blockSwap(std::vector<int>& arr, int current_start_idx, int current_len, int d) { // Base cases d %= current_len; // Ensure d is within the current_len bounds if (d == 0 || d == current_len) { return; // No rotation needed } // Let the current segment be [A][B] // A: arr[current_start_idx ... current_start_idx + d - 1] // B: arr[current_start_idx + d ... current_start_idx + current_len - 1] int len_A = d; int len_B = current_len - d; if (len_A == len_B) { // Case 1: A and B are of equal length. Just swap them. swapBlocks(arr, current_start_idx, current_start_idx + len_A, len_A); } else if (len_A < len_B) { // Case 2: A is shorter than B. // Swap A with the last 'len_A' elements of B (B2). // B = [B1][B2], where B1 has length (len_B - len_A) and B2 has length len_A. // Swap A (at current_start_idx) with B2 (at current_start_idx + len_B). swapBlocks(arr, current_start_idx, current_start_idx + len_B, len_A); // After swapping, the array segment becomes [B2][B1][A]. // Now, the new problem is to rotate the prefix [B2][B1] (effectively B) by 'len_A' positions. // This means rotating arr[current_start_idx ... current_start_idx + len_B - 1] by len_A. _blockSwap(arr, current_start_idx, len_B, len_A); } else { // len_A > len_B // Case 3: A is longer than B. // Swap B with the last 'len_B' elements of A (A2). // A = [A1][A2], where A1 has length (len_A - len_B) and A2 has length len_B. // Swap B (at current_start_idx + len_A) with A2 (at current_start_idx + len_A). swapBlocks(arr, current_start_idx, current_start_idx + len_A, len_B); // After swapping, the array segment becomes [B][A1][A2]. // Now, the new problem is to rotate the suffix [A1][A2] (effectively A) by (len_A - len_B) positions. // This means rotating arr[current_start_idx + len_B ... current_start_idx + current_len - 1] // by (len_A - len_B) positions. _blockSwap(arr, current_start_idx + len_B, len_A, len_A - len_B); } } // Wrapper function for the Block Swap algorithm void rotateArrayBlockSwap(std::vector<int>& arr, int d) { int n = arr.size(); if (n == 0) return; _blockSwap(arr, 0, n, d); } int main() { // Step 1: Initialize array and rotation amount std::vector<int> arr1 = {1, 2, 3, 4, 5, 6, 7}; int d1 = 2; // Rotate by 2 positions std::cout << "Original array: "; printArray(arr1); // Step 2: Apply the Block Swap algorithm rotateArrayBlockSwap(arr1, d1); // Step 3: Print the rotated array std::cout << "Rotated array by " << d1 << " positions: "; printArray(arr1); std::cout << std::endl; // Test with another example: d > n std::vector<int> arr2 = {10, 20, 30, 40, 50}; int d2 = 7; // Rotate by 7 positions (effectively 7 % 5 = 2) std::cout << "Original array: "; printArray(arr2); rotateArrayBlockSwap(arr2, d2); std::cout << "Rotated array by " << d2 << " positions: "; printArray(arr2); std::cout << std::endl; // Test with d = 0 or d = n std::vector<int> arr3 = {1, 2, 3}; int d3 = 0; std::cout << "Original array: "; printArray(arr3); rotateArrayBlockSwap(arr3, d3); std::cout << "Rotated array by " << d3 << " positions: "; printArray(arr3); std::cout << std::endl; std::vector<int> arr4 = {1, 2, 3}; int d4 = 3; std::cout << "Original array: "; printArray(arr4); rotateArrayBlockSwap(arr4, d4); std::cout << "Rotated array by " << d4 << " positions: "; printArray(arr4); std::cout << std::endl; return 0; }
Output
Clear
ADVERTISEMENTS