I am trying to solve a problem where i have to sort an array based on the frequency of the elements(in case of a tie the one that comes first in the input array should be present first that is i have to maintain the initial order of elements) in O(nlgn) time. I came up with the following logic↵
↵
- Make an array of objects and initialize its index and value at that index using the given array.↵
- Now sort the array of objects, using the value.↵
- Fill their frequencies in the object's frequency field.↵
- Sort according to frequency and index↵
↵
↵
My implementation gives an error of **error: must use '.*' or '->*' to call pointer-to-member function** moreover the error occurs at the 1st instance of stable_sort(). C++ compiler details are g++ 4.9.2↵
↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
using namespace std;↵
↵
class Element {↵
int index, value, frequency;↵
public:↵
Element();↵
void setIndex(int);↵
void setValue(int);↵
void setFrequency(int);↵
int getIndex();↵
int getValue();↵
int getFrequency();↵
};↵
↵
class Solution {↵
public:↵
void sortByFrequency(int [], int);↵
bool compareByValue(Element *, Element *);↵
bool compareByFrequency(Element *, Element *);↵
};↵
↵
Element::Element() {↵
frequency = index = value = 0;↵
}↵
↵
void Element::setIndex(int i) {↵
index = i;↵
}↵
↵
void Element::setValue(int i) {↵
value = i;↵
}↵
↵
void Element::setFrequency(int i) {↵
frequency = i;↵
}↵
↵
int Element::getIndex() {↵
return index;↵
}↵
↵
int Element::getValue() {↵
return value;↵
}↵
↵
int Element::getFrequency() {↵
return frequency;↵
}↵
↵
void Solution::sortByFrequency(int a[], int n) {↵
Element obj[n];↵
for(register int i = 0; i < n; i++) {↵
obj[i].setIndex(i);↵
obj[i].setValue(a[i]);↵
}↵
stable_sort(obj, obj + n, compareByValue);↵
obj[0].setFrequency(1);↵
for(register int i = 1; i < n; i++) {↵
if(obj[i].getValue() == obj[i - 1].getValue()) {↵
obj[i].setFrequency(obj[i].getFrequency() + obj[i - 1].getFrequency() + 1);↵
obj[i - 1].setFrequency(-1);↵
obj[i].setIndex(obj[i - 1].getIndex());↵
} else {↵
obj[i].setFrequency(1);↵
}↵
}↵
stable_sort(obj, obj + n, compareByFrequency);↵
for(register int i = n - 1, j = 0; i >= 0; i--) {↵
if(obj[i].getFrequency() != -1) {↵
for(register int k = 0; k < obj[i].getFrequency(); k++) {↵
a[j++] = obj[i].getValue();↵
}↵
}↵
}↵
}↵
↵
bool Solution::compareByValue(Element *a, Element *b) {↵
return (a -> getValue() < b -> getValue());↵
}↵
↵
bool Solution::compareByFrequency(Element *a, Element *b) {↵
if(a -> getFrequency() != b -> getFrequency()) {↵
return (a -> getFrequency() < b -> getFrequency());↵
} else {↵
return (a -> getIndex() > b -> getIndex());↵
}↵
}↵
↵
int main() {↵
int a[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8};↵
int n = sizeof(a)/sizeof(a[0]);↵
Solution obj;↵
obj.sortByFrequency(a, n);↵
for(register int i = 0; i < n; i++) {↵
cout << a[i] << " ";↵
}↵
return 0;↵
}↵
↵
~~~~~
↵
- Make an array of objects and initialize its index and value at that index using the given array.↵
- Now sort the array of objects, using the value.↵
- Fill their frequencies in the object's frequency field.↵
- Sort according to frequency and index↵
↵
↵
My implementation gives an error of **error: must use '.*' or '->*' to call pointer-to-member function** moreover the error occurs at the 1st instance of stable_sort(). C++ compiler details are g++ 4.9.2↵
↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
using namespace std;↵
↵
class Element {↵
int index, value, frequency;↵
public:↵
Element();↵
void setIndex(int);↵
void setValue(int);↵
void setFrequency(int);↵
int getIndex();↵
int getValue();↵
int getFrequency();↵
};↵
↵
class Solution {↵
public:↵
void sortByFrequency(int [], int);↵
bool compareByValue(Element *, Element *);↵
bool compareByFrequency(Element *, Element *);↵
};↵
↵
Element::Element() {↵
frequency = index = value = 0;↵
}↵
↵
void Element::setIndex(int i) {↵
index = i;↵
}↵
↵
void Element::setValue(int i) {↵
value = i;↵
}↵
↵
void Element::setFrequency(int i) {↵
frequency = i;↵
}↵
↵
int Element::getIndex() {↵
return index;↵
}↵
↵
int Element::getValue() {↵
return value;↵
}↵
↵
int Element::getFrequency() {↵
return frequency;↵
}↵
↵
void Solution::sortByFrequency(int a[], int n) {↵
Element obj[n];↵
for(register int i = 0; i < n; i++) {↵
obj[i].setIndex(i);↵
obj[i].setValue(a[i]);↵
}↵
stable_sort(obj, obj + n, compareByValue);↵
obj[0].setFrequency(1);↵
for(register int i = 1; i < n; i++) {↵
if(obj[i].getValue() == obj[i - 1].getValue()) {↵
obj[i].setFrequency(obj[i].getFrequency() + obj[i - 1].getFrequency() + 1);↵
obj[i - 1].setFrequency(-1);↵
obj[i].setIndex(obj[i - 1].getIndex());↵
} else {↵
obj[i].setFrequency(1);↵
}↵
}↵
stable_sort(obj, obj + n, compareByFrequency);↵
for(register int i = n - 1, j = 0; i >= 0; i--) {↵
if(obj[i].getFrequency() != -1) {↵
for(register int k = 0; k < obj[i].getFrequency(); k++) {↵
a[j++] = obj[i].getValue();↵
}↵
}↵
}↵
}↵
↵
bool Solution::compareByValue(Element *a, Element *b) {↵
return (a -> getValue() < b -> getValue());↵
}↵
↵
bool Solution::compareByFrequency(Element *a, Element *b) {↵
if(a -> getFrequency() != b -> getFrequency()) {↵
return (a -> getFrequency() < b -> getFrequency());↵
} else {↵
return (a -> getIndex() > b -> getIndex());↵
}↵
}↵
↵
int main() {↵
int a[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8};↵
int n = sizeof(a)/sizeof(a[0]);↵
Solution obj;↵
obj.sortByFrequency(a, n);↵
for(register int i = 0; i < n; i++) {↵
cout << a[i] << " ";↵
}↵
return 0;↵
}↵
↵
~~~~~
