Sort by frequency and order in a list

angshuman (Angshuman) — Sun, 18 Mar 2007 09:10:26 GMT

// 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 

#include "FreqList.h"

#include 

#include 



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;

}

DZone Snippets: Angshuman's Code Snippets

Sort by frequency and order in a list