การนับการกลับสลับ (Count inversion) หมายถึงจำนวนการสลับที่จำเป็นเพื่อทำให้อาร์เรย์จัดเรียงแล้ว Inversion count = 0 เมื่ออาร์เรย์จัดเรียงแล้ว Inversion count = สูงสุด เมื่ออาร์เรย์จัดเรียงในลำดับย้อนกลับ
มาพัฒนาโปรแกรม C++ เพื่อนับการกลับสลับในอาร์เรย์
อัลกอริทึม
Begin ฟังก์ชัน CountInversionArray มีอาร์กิวเมนต์ a[], n = จำนวนองค์ประกอบ เริ่มต้นตัวนับ c := 0 สำหรับ i ในช่วง 0 ถึง n-1 ทำ สำหรับ j ในช่วง (i + 1) ถึง n ทำ ถ้า a[i] > a[j] แล้ว เพิ่มจำนวนนับขึ้น 1 เสร็จสิ้น เสร็จสิ้น End
ตัวอย่างโค้ด
#include<iostream> using namespace std; int CountInversionArray(int a[], int n) { int i, j, c = 0; for(i = 0; i < n; i++) { for(j = i+1; j < n; j++) if(a[i] > a[j]) c++; } return c; } int main() { int n, i; cout<<"\nEnter the number of elements: "; cin>>n; int a[n]; for(i = 0; i < n; i++) { cout<<"Enter element "<<i+1<<": "; cin>>a[i]; } cout<<"\nThe number of inversion in the array: "<<CountInversionArray(a, n); return 0; }
ผลลัพธ์
Enter the number of elements: 5 Enter element 1: 3 Enter element 2: 2 Enter element 3: 7 Enter element 4: 6 Enter element 5: 1 The number of inversion in the array: 6
