양수와 음수를 모두 포함하는 정수 유형 배열이 제공됩니다. 예를 들어 주어진 크기의 arr[]이 있습니다. 작업은 음수로 둘러싸인 양수가 되도록 배열을 재정렬하는 것입니다. 양수와 음수가 더 많으면 배열의 끝에 정렬됩니다.
여기에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다 -
입력 - 정수 arr[] ={-1, -2, -3, 1, 2, 3}
출력 − 배열 전 배열:-1 -2 -3 1 2 3O(1) 추가 공간이 있는 양수 항목과 음수 항목을 번갈아 가며 배열을 재정렬하면 다음과 같습니다. -1 1 -2 2 -3 3
설명 - 양수 요소와 음수 요소를 모두 포함하는 크기 6의 정수 배열이 제공됩니다. 이제 모든 양수 요소가 음수 요소로 둘러싸여 있고 모든 추가 요소가 배열 끝에 추가되는 방식으로 배열을 재정렬합니다. 즉, -1 1 -2 2 -3 3이 마지막이 됩니다. 결과입니다.
입력 - 정수 arr[] ={-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};
출력 − 배열 전 배열:-1 -2 -3 1 2 3 5 5 -5 3 1 1O(1) 추가 공간이 있는 양수 항목과 음수 항목을 번갈아 가며 배열을 재정렬하면 다음과 같습니다. -1 1 -2 2 -3 3 -5 5 5 3 1 1
설명 - 양수 요소와 음수 요소를 모두 포함하는 크기 12의 정수 배열이 제공됩니다. 이제 모든 양수 요소가 음수 요소로 둘러싸여 있고 모든 추가 요소가 배열의 끝에 추가되는 방식으로 배열을 재정렬합니다. 즉 -1 1 -2 2 -3 3 -5 5 5 3 1 1이 최종 결과입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수형 요소의 배열을 입력하고 배열의 크기를 계산합니다.
-
FOR 루프를 사용하여 재정렬 작업을 수행하기 전에 배열을 인쇄하십시오.
-
배열과 배열의 크기를 매개변수로 전달하여 재정렬(arr, size) 함수를 호출합니다.
-
함수 내부 재정렬(arr, 크기)
-
정수 변수 'ptr'을 선언하고 -1로 초기화합니다.
-
i에서 크기보다 작아질 때까지 FOR 루프를 시작합니다. 루프 내에서 IF ptr이 0보다 큰지 확인한 다음 IF arr[i]가 0보다 큰지 AND arr[ptr]이 0보다 작은지 OR arr[i]가 0보다 작은지 AND arr[ptr]이 0보다 큰지 확인한 다음 move_array 함수를 호출합니다. (arr, size, ptr, i) IF i - ptr이 2보다 큰지 확인한 다음 ptr을 ptr + 2로 설정합니다. ELSE, ptr을 -1로 설정합니다.
-
IF ptr을 -1로 확인한 다음 arr[i]가 0보다 큰지 확인하고 !(i &0x01) OR (arr[i]가 0보다 작음) AND(i &0x01)을 확인한 다음 ptr을 i로 설정합니다.
-
-
move_array(int arr[], int size, int ptr, int temp)
함수 내부-
변수를 문자형의 'ch'로 선언하고 arr[temp]로 설정합니다.
-
i에서 temp까지 루프 FOR를 시작하여 i가 ptr보다 클 때까지 루프 내에서 arr[i]를 arr[i - 1]로 설정합니다.
-
arr[ptr]을 ch로 설정합니다.
-
예시
#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
char ch = arr[temp];
for(int i = temp; i > ptr; i--){
arr[i] = arr[i - 1];
}
arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
int ptr = -1;
for(int i = 0; i < size; i++){
if (ptr >= 0){
if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
move_array(arr, size, ptr, i);
if(i - ptr >= 2){
ptr = ptr + 2;
}
else{
ptr = -1;
}
}
}
if(ptr == -1){
if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
ptr = i;
}
}
}
}
int main(){
//input an array
int arr[] = {-1, -2, -3, 1, 2, 3};
int size = sizeof(arr) / sizeof(arr[0]);
//print the original Array
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
//calling the function to rearrange the array
Rearrangement(arr, size);
//print the array after rearranging the values
cout<<"\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Array before Arrangement: -1 -2 -3 1 2 3 Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3