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 3

post #21 of 55
Quote:
Originally Posted by RadMabbit View Post

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

So what is the second array needed for? Or do you keep the original, and make a copy of it that doesn't have dupes?
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 #22 of 55
Quote:
Originally Posted by lordikon View Post

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.

They never say in the OP what they can and can't do tongue.gif
When I did a prelim course in C++ a very long time a go (which I got bored of, go figure) the first thing they taught was basic C (which I already knew) and the use of C memory allocators. headscratch.gif
Quote:
Originally Posted by RadMabbit View Post

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

I got no problem explaining how it works wink.gif
Quote:
Originally Posted by lordikon View Post

So what is the second array needed for? Or do you keep the original, and make a copy of it that doesn't have dupes?

Second array... I am asking the same question....

--

So basically you need to sort an array and remove duplicates? It becomes easier when the array is sorted... although not much point if the order has to remain the same anyway tongue.gif
Edited by tompsonn - 9/26/12 at 5:43pm
My System
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB 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 7 Ultimate 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz 
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool 
  hide details  
Reply
My System
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB 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 7 Ultimate 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz 
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool 
  hide details  
Reply
post #23 of 55
Thread Starter 
The second array was a suggestion by the teacher for a way to keep the order.....so then after you have deleted the duplicates, you can put the array back into it's original order.

My teacher suggested today that there is another option by using a merge sort, by modifying it so that during the merge step, I can disregard duplicate values. This would combine the sorting/duplication together. However, this has really put me in a whole other world.

Also one thing to note, I believe the variable n, is passed into the function is the number of values in the array.

I apologize for this guys. Have not been clear at all.
post #24 of 55
Quote:
Originally Posted by RadMabbit View Post

The second array was a suggestion by the teacher for a way to keep the order.....so then after you have deleted the duplicates, you can put the array back into it's original order.
My teacher suggested today that there is another option by using a merge sort, by modifying it so that during the merge step, I can disregard duplicate values. This would combine the sorting/duplication together. However, this has really put me in a whole other world.
Also one thing to note, I believe the variable n, is passed into the function is the number of values in the array.
I apologize for this guys. Have not been clear at all.

Why bother sorting if you want to keep the order? It makes no sense to me....
My System
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB 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 7 Ultimate 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz 
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool 
  hide details  
Reply
My System
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB 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 7 Ultimate 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz 
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool 
  hide details  
Reply
post #25 of 55
Thread Starter 
I have no idea.....this is my dilemma. If there is a simpler way to do it, I would love to know, I just don't truly understand your method....driving me INSANE!
post #26 of 55
Quote:
Originally Posted by RadMabbit View Post

I have no idea.....this is my dilemma. If there is a simpler way to do it, I would love to know, I just don't truly understand your method....driving me INSANE!

The simpler way would be my way, or lordikon's way smile.gif
My way works by using a bit-array. When we loop over each number in the array, I set a bit in the bit-array to 1 that corresponds to the number. For example, if there was the number 10 in the array, I would turn on (set to 1) bit 10 in the bit array.

In the loop, if the bit has already been set then it is a duplicate so I skip over it.
All the distinct values go into a new array which gets returned at the end of the function.
My System
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB 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 7 Ultimate 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz 
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool 
  hide details  
Reply
My System
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB 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 7 Ultimate 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz 
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool 
  hide details  
Reply
post #27 of 55
Thread Starter 
Nope not getting it. He was very adamant about using arrays! So lordikon's method might put me in a bad place. The teacher seems to despise C and any relation too C will receive a penalty worse then death....I was really enjoying all aspects of Computer Science until THIS guy showed up. Never had so many issues....making me question how to create an int variable.......

Im working on something now....this could be a solution, Ill post it in a moment!
post #28 of 55
Thread Starter 
AHAHAHAHAHAHAHAAH YES

I am a GENIUS!!!! All praise my simplistic solution to this easy problem. tompsonn you can take you awesomely complicated code and give it to someone who is a lot smarter than me, as can you lordikon. Who needs you guys......nah im joking, but check this out...it really is a pretty cool little idea!!!
Code:
//
//  main.cpp
//  4. List Distinct
//
//  Created by Adam Thoseby on 25/09/2012.
//  Copyright (c) 2012 Adam Thoseby. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int listdistinct(string b[], int n);

int main(int argc, const char * argv[])
{
    int n=4;
    string b[4] = {"4","1","4","4"};
    n = listdistinct( b, n);
}

int listdistinct(string b[], int n) {
    int i, j;
    
    /* new length of modified array */
    int nLength = 1;
    
    for(i=1; i< n; i++){
        
        for(j=0; j< nLength ; j++)
        {
            
            if(b[i] == b[j])
                break;
        }
        
        /* if none of the values in index[0..j] of array is not same as array[i],
         then copy the current value to corresponding new position in array */
        
        if (j==nLength )
            b[nLength++] = b[i];
    }
    
    for (int t=0; t<nLength; t++) {
        cout<<b[t]<<endl;
    }
    return nLength;
}

Piece of artwork right?

One thing though, is this complexity still n log(n)?
post #29 of 55
It is technically O(n^2) because of the nested loop.
My System
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB 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 7 Ultimate 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz 
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool 
  hide details  
Reply
My System
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB 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 7 Ultimate 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz 
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool 
  hide details  
Reply
post #30 of 55
Thread Starter 
Quote:
Originally Posted by tompsonn View Post

It is technically O(n^2) because of the nested loop.

Awesome.....why wont this 5th story window open.

Can you see what I was trying to do now? I want to be able to do something like that but have a worst case complexity of nlogn...
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++