ข้อกำหนดโจทย์
กำหนดอาเรย์ของ N องค์ประกอบที่แตกต่างกัน หาจำนวนการสลับน้อยที่สุดที่จำเป็นเพื่อเรียงลำดับอาเรย์
ตัวอย่าง
ถ้าอาเรย์คือ {4, 2, 1, 3} แล้วต้องการ 2 การสลับ
- สลับ arr[0] กับ arr[2]
- สลับ arr[2] กับ arr[3]
อัลกอริทึม
1. สร้าง vector of pair ใน C++ โดยมี first element เป็นค่าอาเรย์ และ second element เป็นดัชนีของอาเรย์ 2. เรียงลำดับ vector of pair ตาม first element ของ pair 3. วนลูปผ่าน vector และตรวจสอบว่าดัชนีที่จับคู่กับค่าถูกต้องหรือไม่ ถ้าไม่ ให้สลับไปเรื่อยๆ จนกว่าองค์ประกอบจะถูกวางถูกต้อง และนับจำนวนการสลับ
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
vector<pair<int, int>> vec(n);
for (int i = 0; i < n; ++i) {
vec[i].first = arr[i];
vec[i].second = i;
}
sort(vec.begin(), vec.end());
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (vec[i].second == i) {
continue;
}
swap(vec[i].first, vec[vec[i].second].first);
swap(vec[i].second, vec[vec[i].second].second);
if (i != vec[i].second) {
--i;
}
++cnt;
}
return cnt;
}
int main() {
int arr[] = {4, 2, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum swaps = " << getMinSwaps(arr, n) << endl;
return 0;
}
เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้
ผลลัพธ์
Minimum swaps = 2
