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

post #11 of 55
Thread Starter 
please see EDIT post at top!
post #12 of 55
qsort should be all you need.

Code:
#include <stdio.h>
#include <stdlib.h>

int a[] = {1,2,3,4,5,6};
int b[] = {5,4,3,2,1,0};

int compare(const void* a, const void* b)
{
        return ( *(int*)a - *(int*)b );
}

int compare_rev( const void* a, const void* b )
{
        return ( *(int*)b - *(int*)a ); 
}

int main ()
{
        qsort (a, 6, sizeof(int), compare);
        qsort (b, 6, sizeof(int), compare_rev);
        return 0;
}

Or do you literally need to implement this yourself?
Ol' Sandy
(28 items)
 
"Zeus"
(12 items)
 
Elite Preview
(6 items)
 
CPUMotherboardGraphicsRAM
Intel Xeon E3-1230v3 Gigabyte GA-Z97X-UD5H-BK MSI Gaming GTX 980 Kingston 32GB (4x8) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Samsung EVO 1TB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642 
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B 
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 8 Pro 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2713HM Topre Realforce 87UB | Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Logitech G700 XTRAC Ripper XXL 
AudioAudioAudioAudio
Beyerdynamic DT-770 Pro 250ohm Schiit Bifrost DAC Schiit Asgard 2 HiVi Swan M50W 2.1 
CPUMotherboardRAMHard Drive
Intel Xeon E5-2620 Super Micro X9SRL-F-B 128GB 1333MHz LSI 9271-8i 
OSPowerCase
VMware ESXi 5.5 SeaSonic SS-400FL2 Fractal Define R3 
CPUMotherboardGraphicsRAM
Intel Core i5-3437U HP EliteBook Folio 9470m  Intel HD Graphics 4000  16GB DDR3 SDRAM 
Hard DriveOS
256GB SSD Windows 10 Insider Preview 
  hide details  
Reply
Ol' Sandy
(28 items)
 
"Zeus"
(12 items)
 
Elite Preview
(6 items)
 
CPUMotherboardGraphicsRAM
Intel Xeon E3-1230v3 Gigabyte GA-Z97X-UD5H-BK MSI Gaming GTX 980 Kingston 32GB (4x8) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Samsung EVO 1TB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642 
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B 
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 8 Pro 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2713HM Topre Realforce 87UB | Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Logitech G700 XTRAC Ripper XXL 
AudioAudioAudioAudio
Beyerdynamic DT-770 Pro 250ohm Schiit Bifrost DAC Schiit Asgard 2 HiVi Swan M50W 2.1 
CPUMotherboardRAMHard Drive
Intel Xeon E5-2620 Super Micro X9SRL-F-B 128GB 1333MHz LSI 9271-8i 
OSPowerCase
VMware ESXi 5.5 SeaSonic SS-400FL2 Fractal Define R3 
CPUMotherboardGraphicsRAM
Intel Core i5-3437U HP EliteBook Folio 9470m  Intel HD Graphics 4000  16GB DDR3 SDRAM 
Hard DriveOS
256GB SSD Windows 10 Insider Preview 
  hide details  
Reply
post #13 of 55
Thread Starter 
I need to have everything in one function. As you can see from my original post, I need to delete duplicate entries in an array, but still keep the order on output!

I'm finding it a little tough.
post #14 of 55
Quote:
Originally Posted by RadMabbit View Post

I need to have everything in one function. As you can see from my original post, I need to delete duplicate entries in an array, but still keep the order on output!
I'm finding it a little tough.

Right right. OK I'm at home now, I can actually sit down and freakin' concentrate tongue.gif
Code:
#include "stdafx.h"
#include <iostream>
using namespace std; 

int* array_distinct( const int* in_array, const int length, int* out_length );

int main()
{
        int length;
        int input[] = { 1, 9, 8, 0, 7, 4, 5, 6, 3, 2, 6, 4, 1, 7, 8, 4, 1, 0, 9 };

        int* output = array_distinct( input, 19, &length );

        if ( output != NULL && length )
        {
                int i;
                for ( i = 0; i < length; ++i )
                        cout << output[i] << ",";
        }

        free( output );
        getchar();

        return 0;
}

int* array_distinct( const int* in_array, const int length, int* out_length )
{
        *out_length = 0;

        if ( length <= 1 )
        {
                *out_length = length;
                return ( int* ) in_array;
        }

        int* tmp = ( int* ) malloc( sizeof( int ) * length );
        int i;
        unsigned int distinct = 0;

        for ( i = 0; i < length; ++i )
        {
                if ( distinct & ( 1 << in_array[i] ) )
                        continue;

                distinct |= ( 1 << in_array[i] );
                tmp[i] = in_array[i];
                ++( *out_length );
        }

        tmp = ( int* ) realloc( tmp, sizeof( int ) * ( *out_length ) );
        return tmp;
}

Thus is the magic I have worked... The magic being the use of a lookup "bit array" which is constant size, which technically makes the algorithm O(1).
Ol' Sandy
(28 items)
 
"Zeus"
(12 items)
 
Elite Preview
(6 items)
 
CPUMotherboardGraphicsRAM
Intel Xeon E3-1230v3 Gigabyte GA-Z97X-UD5H-BK MSI Gaming GTX 980 Kingston 32GB (4x8) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Samsung EVO 1TB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642 
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B 
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 8 Pro 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2713HM Topre Realforce 87UB | Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Logitech G700 XTRAC Ripper XXL 
AudioAudioAudioAudio
Beyerdynamic DT-770 Pro 250ohm Schiit Bifrost DAC Schiit Asgard 2 HiVi Swan M50W 2.1 
CPUMotherboardRAMHard Drive
Intel Xeon E5-2620 Super Micro X9SRL-F-B 128GB 1333MHz LSI 9271-8i 
OSPowerCase
VMware ESXi 5.5 SeaSonic SS-400FL2 Fractal Define R3 
CPUMotherboardGraphicsRAM
Intel Core i5-3437U HP EliteBook Folio 9470m  Intel HD Graphics 4000  16GB DDR3 SDRAM 
Hard DriveOS
256GB SSD Windows 10 Insider Preview 
  hide details  
Reply
Ol' Sandy
(28 items)
 
"Zeus"
(12 items)
 
Elite Preview
(6 items)
 
CPUMotherboardGraphicsRAM
Intel Xeon E3-1230v3 Gigabyte GA-Z97X-UD5H-BK MSI Gaming GTX 980 Kingston 32GB (4x8) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Samsung EVO 1TB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642 
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B 
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 8 Pro 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2713HM Topre Realforce 87UB | Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Logitech G700 XTRAC Ripper XXL 
AudioAudioAudioAudio
Beyerdynamic DT-770 Pro 250ohm Schiit Bifrost DAC Schiit Asgard 2 HiVi Swan M50W 2.1 
CPUMotherboardRAMHard Drive
Intel Xeon E5-2620 Super Micro X9SRL-F-B 128GB 1333MHz LSI 9271-8i 
OSPowerCase
VMware ESXi 5.5 SeaSonic SS-400FL2 Fractal Define R3 
CPUMotherboardGraphicsRAM
Intel Core i5-3437U HP EliteBook Folio 9470m  Intel HD Graphics 4000  16GB DDR3 SDRAM 
Hard DriveOS
256GB SSD Windows 10 Insider Preview 
  hide details  
Reply
post #15 of 55
Quote:
Originally Posted by tompsonn View Post

Quote:
Originally Posted by RadMabbit View Post

I need to have everything in one function. As you can see from my original post, I need to delete duplicate entries in an array, but still keep the order on output!
I'm finding it a little tough.

Right right. OK I'm at home now, I can actually sit down and freakin' concentrate tongue.gif
Code:
#include "stdafx.h"
#include <iostream>
using namespace std; 

int* array_distinct( const int* in_array, const int length, int* out_length );

int main()
{
        int length;
        int input[] = { 1, 9, 8, 0, 7, 4, 5, 6, 3, 2, 6, 4, 1, 7, 8, 4, 1, 0, 9 };

        int* output = array_distinct( input, 19, &length );

        if ( output != NULL && length )
        {
                int i;
                for ( i = 0; i < length; ++i )
                        cout << output[i] << ",";
        }

        free( output );
        getchar();

        return 0;
}

int* array_distinct( const int* in_array, const int length, int* out_length )
{
        *out_length = 0;

        if ( length <= 1 )
        {
                *out_length = length;
                return ( int* ) in_array;
        }

        int* tmp = ( int* ) malloc( sizeof( int ) * length );
        int i;
        unsigned int distinct = 0;

        for ( i = 0; i < length; ++i )
        {
                if ( distinct & ( 1 << in_array[i] ) )
                        continue;

                distinct |= ( 1 << in_array[i] );
                tmp[i] = in_array[i];
                ++( *out_length );
        }

        tmp = ( int* ) realloc( tmp, sizeof( int ) * ( *out_length ) );
        return tmp;
}

Thus is the magic I have worked... The magic being the use of a lookup "bit array" which is constant size, which technically makes the algorithm O(1).

Nice. I'd like to see him explain how that code works to his teacher though. Bit shifting, pointer creation/passing/arithmetic are probably things he hasn't learned yet. smile.gif

Also, since he's able to use C++, not sure he should be using malloc/free/realloc, and he may not have learned that stuff yet either.
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 #16 of 55
Thread Starter 
You got it, none of that stuff made any sense! Managed to delete the duplicates, but doing that meant I had to sort, then I lose the original order. That was the only thing I was left with....

Stupid C++
post #17 of 55
Quote:
Originally Posted by RadMabbit View Post

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!

This seems entirely different than what you were originally talking about.

All I'm seeing here is that you're reversing the order of these two arrays. Is that what you trying to accomplish?

And you said this all needs to be done in one function?
Edited by lordikon - 9/26/12 at 8:58am
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 #18 of 55
Thread Starter 
It just is a part. To be honest, I think the question has confused me pretty heavily!

Our teacher said to use a second array to keep the order......
post #19 of 55
Quote:
Originally Posted by RadMabbit View Post

It just is a part. To be honest, I think the question has confused me pretty heavily!

Our teacher said to use a second array to keep the order......

Yea I'm pretty confused as well now. smile.gif

I've gathered what I think are part of your requirements:
1.) Sorting an array
2.) Removing duplicates from an array
3.) Possibly using another array to keep track of something from the first array.
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 #20 of 55
Thread Starter 
Quote:
Originally Posted by lordikon View Post

Yea I'm pretty confused as well now. smile.gif
I've gathered what I think are part of your requirements:
1.) Sorting an array
2.) Removing duplicates from an array
3.) Possibly using another array to keep track of something from the first array.

Yea just about, except I need to keep the order of the original array. So say I have this one
2,3,4,5,5,1,1,1
I need to remove duplicates AND keep the order from left to right, so I would get
2,3,4,5,1
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++