#include <iostream>
#include <sstream>
#include <string>
int* splitIp(const std::string& ip) {
int* octets = new int[4];
std::stringstream ss(ip);
for (int i = 0; i < 4; ++i) {
std::string octet;
std::getline(ss, octet, '.');
octets[i] = std::stoi(octet);
}
return octets;
}
int findMaxOctet(std::string* ips, int n) {
int maxOctet = 0;
for (int i = 0; i < n; ++i) {
int* octets = splitIp(ips[i]);
for (int j = 0; j < 4; ++j) {
if (octets[j] > maxOctet) maxOctet = octets[j];
}
delete[] octets;
}
return maxOctet;
}
void countingSort(std::string* ips, int n, int octetIndex, int maxOctet) {
std::string* output = new std::string[n];
int* count = new int[maxOctet + 1] {0};
for (int i = 0; i < n; i++) {
int* octets = splitIp(ips[i]);
count[octets[octetIndex]]++;
delete[] octets;
}
for (int i = 1; i <= maxOctet; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
int* octets = splitIp(ips[i]);
output[--count[octets[octetIndex]]] = ips[i];
delete[] octets;
}
for (int i = 0; i < n; i++) ips[i] = output[i];
delete[] output;
delete[] count;
}
void radixSortIPs(std::string* ips, int n) {
int maxOctet = findMaxOctet(ips, n);
for (int i = 3; i >= 0; --i) countingSort(ips, n, i, maxOctet);
}
void printArray(std::string* ips, const int& n) {
for (int i = 0; i < n; i++) std::cout << ips[i] << std::endl;
}
void solution() {
int n = 5;
std::string* ips = new std::string[n]{"192.168.1.1", "10.0.0.2", "172.16.0.1",
"192.168.0.1", "10.0.0.1"};
std::cout << "Initial IP Addresses:\n";
printArray(ips, n);
radixSortIPs(ips, n);
std::cout << "\nSorted IP Addresses:\n";
printArray(ips, n);
delete[] ips;
}
int main() {
solution();
}
