정렬되지 않은 고유한 요소의 배열이 제공됩니다. 목표는 배열이 정렬된 후 십자선을 찾는 것입니다. 십자선은 아래와 같이 계산됩니다 -
-
Arr[]={ 1,2,4,3,5 } 아래와 같이 3개의 십자선이 있습니다.
-
Arr[]={ 1,2,3,4,5 }. 배열이 이미 정렬되어 있으므로 십자선이 없습니다.
오른쪽의 요소가 왼쪽의 정렬된 요소에 추가되는 삽입 정렬을 사용하여 십자선을 계산합니다. 요소가 정렬된 부분에 추가될 때마다 올바른 위치로 이동할 때 카운트가 증가합니다. 더 큰 모든 요소를 교차하여 통과합니다.
예를 들어 이해합시다.
입력 - arr[]={4,3,1,2 }
출력 − 배열의 십자선 개수 − 5
설명 − 라인 4-4 및 3-3은 라인 1-1 및 2-2와 교차합니다. 총 4개의 크로스 라인.
4-4와 3-3은 모두 한 번 교차합니다. 총 4+1=5 십자선.
입력 - arr[]={ 0,1,5,3 }
출력 − 배열의 십자선 개수 − 1
설명 − 5-5와 3-3은 모두 한 번 교차합니다. 총 1개의 교차선입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
고유한 숫자로 초기화된 정수 배열 arr[]을 사용합니다.
-
InsertionSort(int arr[], int n) 함수는 배열과 배열의 길이를 입력으로 받고 정렬 후 결과로 십자선의 개수를 반환합니다.
-
십자선의 초기 개수를 0으로 합니다. Count 변수를 사용합니다.
-
첫 번째 요소는 이미 정렬되어 있으므로 두 번째 요소부터 끝까지(i=1 ~ i
-
이제> item 및 j>0인 경우 모든 요소를 오른쪽으로 이동합니다. 항목별로 교차하므로 각 교대 증분에 대해 카운트합니다.
-
while 루프가 끝나면 arr[j+1]인 올바른 위치에 항목을 놓습니다.
-
모든 요소에 대해 이 작업을 수행하고 교차하는 요소를 계산합니다.
-
count 값을 no로 증가시킵니다. 의 교차선이 가능합니다.
예시
#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;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Number of cross lines: 8