จำนวนการผกผันที่เกิดขึ้นเพื่อเรียงลำดับอาร์เรย์ที่กำหนดเรียกว่าการนับผกผัน ปัญหาการผกผันเป็นปัญหาคลาสสิกที่สามารถแก้ไขได้โดยใช้อัลกอริทึมการเรียงลำดับการผสาน ในปัญหานี้ v เราจะนับองค์ประกอบทั้งหมดมากกว่าทางด้านซ้ายและเพิ่มจำนวนไปยังผลลัพธ์ ThisLogic เสร็จสิ้นภายในฟังก์ชันผสานของการเรียงลำดับการผสาน
เพื่อให้เข้าใจหัวข้อได้ดีขึ้น เรามาดูตัวอย่างกัน ให้เราพิจารณาสองอาร์เรย์ย่อยที่เกี่ยวข้องกับกระบวนการผสาน -
Input: arr[] = { 1, 9, 6, 4, 5}
Output: Inversion count is 5 คำอธิบาย
จำนวนผกผันของอาร์เรย์
จากอาร์เรย์ ให้หาจำนวนการผกผันของอาร์เรย์นั้น ถ้า (i
ตัวอย่างเช่น
ในอาร์เรย์มีการผกผัน 5 ครั้ง
(9,6), (9,4), (9,5), (6,4), (6,5)
1. เปรียบเทียบค่าขององค์ประกอบซึ่งกันและกัน
2. เพิ่มตัวนับหากค่าที่ดัชนีล่างสูงกว่า
3. แสดงผล
ตัวอย่าง
#include <stdio.h>
int Merge(int arr[], int aux[], int low, int mid, int high) {
int k = low, i = low, j = mid + 1;
int inversionCount = 0;
while (i <= mid && j <= high) {
if (arr[i] <= arr[j]) {
aux[k++] = arr[i++];
} else {
aux[k++] = arr[j++];
inversionCount += (mid - i + 1); // NOTE
}
}
while (i <= mid)
aux[k++] = arr[i++];
for (int i = low; i <= high; i++)
arr[i] = aux[i];
return inversionCount;
}
int MergeSort(int arr[], int aux[], int low, int high) {
if (high == low) // if run size == 1
return 0;
int mid = (low + ((high - low) >> 1));
int inversionCount = 0;
inversionCount += MergeSort(arr, aux, low, mid);
inversionCount += MergeSort(arr, aux, mid + 1, high);
inversionCount += Merge(arr, aux, low, mid, high);
return inversionCount;
}
int main() {
int arr[] = { 1, 9, 6, 4, 5 };
int N = 5;
int aux[N];
for (int i = 0; i < N; i++)
aux[i] = arr[i];
printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1));
return 0;
} 