Sort by frequency and order in a list (See related posts)

// You have an array. For eg [23,12,45,23,9,23,45]. Now you have to print the elements in the order of decreasing frequency, and the same no of times as it is coming in the imput aray. The output for this eg would be 23[3]45[2]12[1]9[1].If frequency of two elements is equal, they should come in the same order as they are coming in the input array.

struct Node
{
    int element;
    int frequency;
    int order;
    struct Node *next;
    struct Node *prev;
};

class FreqList {

 public:
    FreqList();
    virtual ~FreqList();
    virtual void addElement(int newEl);
    virtual void Print();
    virtual void createSorted();
    virtual void printSorted();

 private:
    void addAtEnd(int val, int freq, int order);
    Node* findElement(int val); 
    Node* partition(Node *head, Node *tail, int pivot);
    bool  deleteAfter(Node *p, int &val, int &freq, int &order);
    void insertSorted(int val, int freq, int order);
    void addAfter(Node *p, int val, int freq, int order);
    bool deleteFirst(int &val,int &freq, int &order);
    int orderOfElement;
    int numElements;

    Node *dummy;
    Node *dummySorted;
    Node *tail;

};


#include <stdio.h>
#include "FreqList.h"
#include <time.h>
#include <stdlib.h>

FreqList::FreqList() {
    dummy = new Node;
    dummy->next = NULL;
    tail = dummy;
    dummySorted = new Node;
    dummySorted->next = NULL;
    numElements = 0;
    orderOfElement = 0;
}

FreqList::~FreqList() {
    //lot of cleanup to be done
}

void FreqList::addAtEnd(int val, int freq, int order) {
    Node *temp = new Node;
    temp->element = val;
    temp->frequency = freq;
    temp->order = order;
    temp->next = NULL;

    if(tail != NULL) {
	tail->next = temp;
	tail = temp;
    }
    else
	printf("Oooops!\n");
}

/* This will return a pointer whose next is the desired node */
Node * FreqList::findElement(int val) {
    Node *temp = dummy;
    while(temp->next != NULL) {
	if(temp->next->element == val)
	    return temp;
	else
	    temp=temp->next;
    }
    return NULL;
}

void FreqList::addElement(int newEl) {
    Node *temp;
    ++numElements;
    temp = findElement(newEl);
    if(temp == NULL) {
	//element not found. New element to be added
	addAtEnd(newEl, 1, ++orderOfElement);
	return;
    }
    else {
	if(temp->next != NULL) {
	    temp->next->frequency += 1;
	}
	else
	    printf("Hmmph!\n");
	return;
    }
}

void FreqList::insertSorted(int val, int freq, int order) {
    Node *p = dummySorted;
    while(p->next != NULL) {
	if(freq < p->next->frequency ) {
	    p = p->next;
	}
	else if(freq == p->next->frequency) {
	    if(order > p->next->order) {
		p = p->next;
	    }
	    else {
		break;
	    }
	}
	else {
	    break;
	}
    }
    addAfter(p, val, freq, order);
}

void FreqList::createSorted() {
    int val, freq, order;
    Node *temp = dummy;
    while(temp->next != NULL) {
	val = temp->next->element;
	freq = temp->next->frequency;
	order = temp->next->order;
	insertSorted(val, freq, order);
	temp = temp->next;
    }
}

void FreqList::printSorted() {
    Node *temp = dummySorted;
    while(temp->next != NULL) {
	printf("%d[%d]{%d} ", temp->next->element, temp->next->frequency, \
	       temp->next->order);
	temp = temp->next;	
    }
    printf("\n");
}


void FreqList::addAfter(Node *p, int val, int freq, int order) {
    Node *temp = new Node;
    temp->element = val;
    temp->frequency = freq;
    temp->order = order;

    temp->next = p->next;
    p->next = temp;
}

void FreqList::Print() {
    Node *temp = dummy;
    while(temp->next != NULL) {
	printf("%d[%d]{%d} ", temp->next->element, temp->next->frequency, \
	       temp->next->order);
	temp = temp->next;
    }
    printf("\n");
} 

int main()
{
    int arr[] = {12,12,23,45,23,9,23,45};
    int num;
    FreqList *freqList = new FreqList();

    srand((unsigned)time(0));


    for(int i=0; i<8000; i++)
    {   
        num = (rand()%10)+1;
        //printf("Step: %d El: %d ", i, arr[i] );
        freqList->addElement(num);
    }   
    freqList->Print();
    freqList->createSorted();
    freqList->printSorted();
    return 0;
}