เราได้รับอาร์เรย์ขององค์ประกอบที่แตกต่างกันซึ่งไม่มีการจัดเรียง เป้าหมายคือการหาเส้นตัดหลังจากจัดเรียงอาร์เรย์แล้ว ข้ามเส้นจะถูกนับดังแสดงด้านล่าง -
-
Arr[]={ 1,2,4,3,5 } มีกากบาท 3 เส้นดังแสดงด้านล่าง
-
อา[]={ 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 ใช้ตัวแปรการนับ
-
องค์ประกอบแรกได้รับการจัดเรียงแล้ว ดังนั้นเริ่มจากองค์ประกอบที่สองจนถึงสิ้นสุด (i=1 ถึง i
-
ตอนนี้ให้เลื่อนองค์ประกอบทั้งหมดไปทางขวาหากเป็น> item และ j>0 สำหรับการเพิ่มกะแต่ละครั้งให้นับเนื่องจากสิ่งเหล่านี้ถูกข้ามด้วยรายการ
-
ที่ส่วนท้ายของ while loop ให้วางรายการไว้ที่ตำแหน่งที่ถูกต้องคือ arr[j+1].
-
ทำสิ่งนี้กับองค์ประกอบทั้งหมดและนับองค์ประกอบที่ข้าม
-
ค่าที่เพิ่มขึ้นของการนับเป็นจำนวน ข้ามเส้นได้
ตัวอย่าง
#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
