1,076,510 Members — Technology Publication meets Social Media

# Posts by MachDelta

## Quicksort problem in C++

Hi everyone. I've been struggling with a quicksort implementation here. I think - scratch that - I know i'm overrunning an array (erm, vector) based on how it explodes, but I honestly can't see it and I have no debugger. I slept on it but fresh eyes didn't get me anywhere. I've been digging around online for a while but there are a thousand different ways to do quicksort and it just ends up being confusing to keep it all straight.
Oh and two things to note:
-Yes, I have to use vectors. I've no idea why.
-There are global variables (don't shoot me) being incremented for performance tracking and comparing sorts.
Here's the mess:

``````//Quick Sort
vector<int> quickSort(vector<int> &data, int left, int right){
if(left>=right){ return data; }
else{
int split = partition(data, left, right);
recurses+=2;
quickSort(data, left, split-1);
quickSort(data, split+1, right);
}
}

//Quick sort partitioning
int partition(vector<int> &data, int left, int right){
int pivot=left;
int i=left+1;
int j=right;

while (i<j){
for(;i<right && (data[i]<=data[pivot]);i++) { compares++; }
for(;(data[j]>data[pivot]);j--) { compares++; }
if(i<j){
swap(data[i],data[j]);
swaps++;
}
}
swap(data[pivot], data[j]);
swaps++;
return j;
}
``````

I feel like i'm somehow passing bad indeces to the partition function and the for loops are running away. Every once in a while the function will finish (it's fed 1-10 in random order) but the first and second elements of the vector are always garbage when it does. Mind you, it's certainly possible that I have more than one error going on.

Thoughts?

MachDelta
Newbie Poster
7 posts since Nov 2011
Reputation Points: 10
Skill Endorsements: 0

## Re: Linker Error in C++

you need to make sure your header and function definitions are added to your project.. in dev c++ they will appear in the project window on the left side.

Yep they're there: main.cpp, c4functs.cpp and c4functs.h
All my functions are in the classes browser too.
I don't understand where the linker is losing track of things. :(

MachDelta
Newbie Poster
7 posts since Nov 2011
Reputation Points: 10
Skill Endorsements: 0

Hi everyone. I've been fighting with a piece of incomplete code for a while now, and it's really frustrating... particularly because it's due tomorrow.

Anyways, when I try to compile my project it's spitting out linker errors at me:

[Linker error] undefined reference to `clearBoard(int, char)'
[Linker error] undefined reference to `printBoard(char, int)'

c4functs.h:

``````int playGame(int, char, char);
void clearBoard(int, char);
void printBoard (char, int);``````

c4functs.cpp:

``````#include <cstdlib>
#include <iostream>
#include "c4functs.h"

using namespace std;

int playGame(int BSIZE, char token1, char token2){

//Create board
char board[BSIZE][BSIZE];

//Init board
clearBoard(BSIZE, *board[BSIZE]);
printBoard(*board[BSIZE], BSIZE);
//LOOP while(1)
//Display board
//Check for full board return 0
//Player1 move
//Valid?
//Display board
//Check for win return 1
//Player 2 move
//Valid?
//Display board
//Check for win return -1
return 0;
}

//Fills board with 'O's
void clearBoard(int size, char *board[]){
for(int i=0;i>size;++i){
for(int j=0;j>size;++j){
board[i][j]='O';
}
}
}

//Prints the current board
void printBoard(char *board[], int size){
int i,j;
size=size-2;

for(i=0;i>size;++i){
for(j=0;j>size;++j){
cout<<" "<<board[i][j]<<" ";  //Print board characters
if (size<j) cout<<"|";        //Vertical divider
}
cout<<endl;
for(j=0;j>size;++j){          //Print horizontal divider
cout<<"---";
if (size<i) cout<<"+";        //Corner piece
cout<<endl;
}
}
}``````

The only other file in the project is main, which I haven't included b/c I don't think it's the problem. It does have #include "c4functs.h" but the only thing it calls is playGame().
Anywho, i've trashed the project and rebuilt it twice now. I tried forcing some file includes though the project properties, which just made the compiler bitch about double declarations. I've got tunnel vision and i'm probably just missing something blindingly obvious... help?

PS: Bloodshed DevC++ 4.9.9.2 (I know I know... next semester it's gone for good)

MachDelta
Newbie Poster
7 posts since Nov 2011
Reputation Points: 10
Skill Endorsements: 0

## Re: Ignoring stream input in C++

Alright, so, essentially in_avail() is unreliable because there's no guarantee the OS has passed any or all characters to the process' stream buffer? Or i'm just not understanding how stream buffers work. Or something.

Thanks though, I'll stay away from in_avail() in the future.

MachDelta
Newbie Poster
7 posts since Nov 2011
Reputation Points: 10
Skill Endorsements: 0

## Ignoring stream input in C++

Another newbie question here. What's the difference between these two?

``````cin.ignore(cin.rdbuf()->in_avail(), '\n');
cin.ignore(numeric_limits<streamsize>::max(), '\n');``````

I understand that the former will ignore only the characters left in the stream buffer, while the latter tries to ignore characters equal to the size of the buffer. So the end result should, normally, be the same. But then my question is why, when used in this function, the former explodes (infinite loop of "Invalid selection.\n") and the latter works fine?

``````int mainMenu(){
int pick=0;

"\t1) New game\n"<<
"\t2) Options\n"<<
"\t3) Quit\n\n";
while (!pick){
cin>>pick;
if (pick>0 && pick<4) return(pick);
else pick=0;
if (!cin.good()){     //Clear mangled input
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n'); //This works, in_avail doesn't.
}
cout<<"Invalid selection.\n";
}

}``````

I'm using code somewhat above my understanding here. What exactly is rdbuf()->in_avail() returning when std::cin has been clobbered?

MachDelta
Newbie Poster
7 posts since Nov 2011
Reputation Points: 10
Skill Endorsements: 0

## Re: Write results on a .txt in C++

You have to push the results out to the file after every test. By doing the print to file loop after the test loop, you can only print the last result. They need to be within the same loop.

``````//....
ofstream f2;
f2.open("results.txt", ofstream::out); //Open file

for (count= 1; count<= 20; count++){
//.... Run test
std::cout<<exp<<"Time:  "<<duration << " seconds" <<'\n'; //Print to console
f2<<duration<<endl;     //Print to file
} // End test loop

f2.close();``````
MachDelta
Newbie Poster
7 posts since Nov 2011
Reputation Points: 10
Skill Endorsements: 0

## Portable console colours? in C++

Hi everyone. First time poster here :)

I'm working on my final project for a computing course at university, and I was wondering if anyone knew of a portable library or solution to changing console colours. I understand that such functions are OS specific (I'm working on Win32, but my prof is a Mac-grrl) and thus likely a giant headache for someone of my limited experience... but hey, it would be nice to try for bonus points.

Just curious.
TYIA.

MachDelta
Newbie Poster
7 posts since Nov 2011
Reputation Points: 10