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

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;```
```

Edited by RadMabbit - 9/25/12 at 11:20pm
Quote:

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;```
```

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
 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
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++
Quote:

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
 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
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.
Quote:

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
 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
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
 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
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!
Quote:

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
 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
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
• Sorting and counting distinct variables C++
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Application Programming › Sorting and counting distinct variables C++