เราได้รับอาร์เรย์ขององค์ประกอบที่แตกต่างกันซึ่งไม่มีการจัดเรียง เป้าหมายคือการหาเส้นตัดหลังจากจัดเรียงอาร์เรย์แล้ว ข้ามเส้นจะถูกนับดังแสดงด้านล่าง -
-
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