Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Application Programming › Sorting and counting distinct variables C++
New Posts  All Forums:Forum Nav:

Sorting and counting distinct variables C++

post #1 of 55
Thread Starter 
EDIT:
Ok so the REAL question here is how do I sort the following......
I have an array a[] of string
I have an array b[] that is like the position of the elements in the string.

E.g a[] = {6,5,4,3,2,1}
b[] = {0,1,2,3,4,5}

How do I then sort this to show the following:

a[] = {1,2,3,4,5,6}
b[] = {5,4,3,2,1,0}
whilst trying to keep nlog(n) complexity

This will RESOLVE my issue entirely!


Hey Guys

I am having some trouble with a function in C++

These are the specifications for the function:
  • modifies b so that all the distinct values are in b[0..k-1] and returns k
  • the distinct values are in the order of their leftmost appearance in original b
  • e.g. 3,6,3,19,6,3,11 with n=7 would be changed to 3,6,19,11,?,? with k=4 returned
  • worstcase complexity is n log(n) or better.

I have started the function, but am feeling pretty lost in where to go next. Also trying to figure out how to ensure the complexity stays nlog(n)
Code:
int listdistinct(string b[], int n) {
string a[];
sort b[];
i=1;
for i=0 , i<k {
   if b[i] == b[i-1] ;
   else { a[n] = b[i-1]; n++;}
}
return n;

Thanks for your help!
Edited by RadMabbit - 9/25/12 at 11:20pm
post #2 of 55
Quote:
Originally Posted by RadMabbit View Post

Hey Guys

I am having some trouble with a function in C++

These are the specifications for the function:
  • modifies b so that all the distinct values are in b[0..k-1] and returns k
  • the distinct values are in the order of their leftmost appearance in original b
  • e.g. 3,6,3,19,6,3,11 with n=7 would be changed to 3,6,19,11,?,? with k=4 returned
  • worstcase complexity is n log(n) or better.

I have started the function, but am feeling pretty lost in where to go next. Also trying to figure out how to ensure the complexity stays nlog(n)
Code:
int listdistinct(string b[], int n) {
string a[];
sort b[];
i=1;
for i=0 , i<k {
   if b[i] == b[i-1] ;
   else { a[n] = b[i-1]; n++;}
}
return n;

Thanks for your help!

Here's a list of sorting algorithms: http://en.wikipedia.org/wiki/Sorting_algorithm
Quicksort, Heapsort, and Mergesort are all O(n log(n)), and they're all fairly common.

They also provide pseudocode for you:
http://en.wikipedia.org/wiki/Heapsort#Pseudocode
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
post #3 of 55
Thread Starter 
It isn't just the sort. It counts like distinct values....so if I had five 4's and three 2's, the array would read [4,4,2,2,4,2,4], then after, the array would simply read [4,2] as there are more 4's than 2's.

That is what I am struggling with! I can just use the sort() function from #include in C++
post #4 of 55
Quote:
Originally Posted by RadMabbit View Post

It isn't just the sort. It counts like distinct values....so if I had five 4's and three 2's, the array would read [4,4,2,2,4,2,4], then after, the array would simply read [4,2] as there are more 4's than 2's.

That is what I am struggling with! I can just use the sort() function from #include in C++

After sorting you could re-iterate through the array, check a value, then check the next index and if it's a match, remove it, otherwise update your current value.
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
post #5 of 55
Thread Starter 
This is the key line here

e.g. 3,6,3,19,6,3,11 with n=7 would be changed to 3,6,19,11,?,? with k=4 returned

See how it keeps numbers in original order if they are not duplicates.
post #6 of 55
Quote:
Originally Posted by RadMabbit View Post

This is the key line here

e.g. 3,6,3,19,6,3,11 with n=7 would be changed to 3,6,19,11,?,? with k=4 returned

See how it keeps numbers in original order if they are not duplicates.

Each time you find a unique value you would just increment the counter, return the counter when you're finished.
Edited by lordikon - 9/25/12 at 5:05pm
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
post #7 of 55
Here's something I whipped up real quick, it may not compile it as I just typed it in here directly, but you get the idea.
Code:
#include <list>
#include <limits.h> // For INT_MAX

void main()
{
    std::list<int> m_values;
    m_values.push_back(3);
    m_values.push_back(6);
    m_values.push_back(3);
    m_values.push_back(19);
    m_values.push_back(6);    
    m_values.push_back(3);
    m_values.push_back(11);

    m_values.sort();

    int uniqueValues = removeDuplicates( m_values );
}

// Returns number of unique values found
int removeDuplicates(std::list<int>& values)
{
    unsigned int uniqueValues = 0;
    int currentValue = -INT_MAX;
    
    std::list<int>::iterator it = values.begin();
    while ( it != values.end() )
    {
        int listValue = (*it);
        if ( listValue != currentValue )
        {
            currentValue = listValue;
            ++uniqueValues;
            ++it;
        }
        else
       {
            // Value was not unique, so we remove it from the list
            it = values.erase(it);
       }
    }
}
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
post #8 of 55
Thread Starter 
Anyway you can do this using arrays and namespace std?

And the numbers I gave are arbitrary. The function will pick the array, which could be 1000 numbers long of totally random numbers!
Code:
int listdistinct(string b[], int n) {
string a[];
sort b[];
i=1;
for i=0 , i<k {
   if b[i] == b[i-1] ;
   else { a[n] = b[i-1]; n++;}
}
return n;

This is the form I have to keep!
post #9 of 55
Quote:
Originally Posted by RadMabbit View Post

Anyway you can do this using arrays and namespace std?

And the numbers I gave are arbitrary. The function will pick the array, which could be 1000 numbers long of totally random numbers!
Code:
int listdistinct(string b[], int n) {
string a[];
sort b[];

for ( i = 1; i < k; ++i )
{
   if ( b[i] != b[i-1] )
   {
        a[n] = b[i-1]; 
        ++n;
   }
}

return n;

This is the form I have to keep!

I'm on my phone right now so I can't post more code, but I edited the code in your quote just above, not sure if that will work but I fixed a could of problems you had.
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
Foldatron
(17 items)
 
Mat
(10 items)
 
Work iMac
(9 items)
 
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275 
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor 
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000 
PowerCase
750W PC P&C Silencer CoolerMaster 690 
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm 
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard 
Mouse
Mac wireless mouse 
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm 
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display 
Monitor
27" Apple thunderbolt display 
  hide details  
Reply
post #10 of 55
Thread Starter 
nah its ok. I dont think I am doing a very good job of getting what I need to have done across!
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Application Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Application Programming › Sorting and counting distinct variables C++