Re: Re: Quick Sort for a Struct - MYCPLUS - C and C++ Programming Resources

January 6, 2009 at 11:56 pm #3499

Participant

Heres a way to do this with a doubly linked list with quicksort. This version of quicksort uses the last item in the
list as a pivot element when partitioning.

<br />
<br />
/****************************************************************<br />
* File Name : c:programstempCG.cpp<br />
* Date : January,6,2008<br />
* Comments : new project<br />
* Compiler/Assembler :<br />
* Modifications :<br />
*<br />
*<br />
*<br />
*<br />
*<br />
* Program Shell Generated At: 3:51:46 p.m.<br />
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/<br />
<br />
<br />
#include < iostream ><br />
#include < fstream ><br />
//#include < string.h ><br />
//#include < conio.h ><br />
//#include < math.h ><br />
#include < iomanip ><br />
#include < ctype.h ><br />
<br />
using namespace std;<br />
<br />
//>>>>>>>>>>>>>>>>>>>>>>>> GLOBAL DATA <<<<<<<<<<<<<<<<<<<<<<<<<<br />
<br />
const int MAX_NAME = 50;<br />
const int MAX_FILE_NAME = 50;<br />
const char STOP_SYMBOL = '*';<br />
enum keys { firstName , lastName , idNumber };<br />
keys sortKey ;<br />
#define OUTPUT_SPACES 15<br />
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<br />
<br />
<br />
<br />
struct person<br />
{<br />
<br />
char firstName [ MAX_NAME ] ;<br />
char lastName [ MAX_NAME ] ;<br />
char idNumber [ MAX_NAME ] ;<br />
person * prior;<br />
person * next;<br />
};<br />
<br />
<br />
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@<br />
<br />
bool readInputFile ( char * fileName , person *&#038; frontList , person *&#038; backList , int &#038; itemsRead );<br />
void quickSort ( person ** front , person ** last , int numberItems );<br />
void swap ( person ** first , person ** last , person ** front , person ** back );<br />
void print ( person * list );<br />
void insertionSort ( person * list , int numberOfItems );<br />
void destroyList ( person * list );<br />
char * key ( person * node );<br />
<br />
//##################################################################################<br />
<br />
<br />
//main function ******************************<br />
<br />
int main ( )<br />
{<br />
<br />
person * front , * back;<br />
int items;<br />
<br />
sortKey = firstName;<br />
readInputFile ( "c:\programs\data.txt" , front , back , items );<br />
print ( front );<br />
quickSort ( &#038; front , &#038; back , items );<br />
cout << endl << endl;<br />
cout << "final ************************" << endl;<br />
print ( front );<br />
destroyList ( front );<br />
return 0 ;<br />
}<br />
<br />
<br />
/******************************* FUNCTION DEFINITION ******************************<br />
<br />
Name : readInputFile<br />
Parameters :<br />
<br />
fileName a(n) char * ,<br />
frontList a(n) person *&#038; ( person *&#038; )  ,<br />
backList a(n) person *&#038; ( person *&#038; )  ,<br />
itemsRead a(n) int &#038;<br />
<br />
<br />
Returns: bool type<br />
Comments:<br />
<br />
<br />
<br />
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/<br />
bool readInputFile ( char * fileName , person *&#038; frontList , person *&#038; backList , int &#038; itemsRead )<br />
{<br />
<br />
<br />
fstream inputFile;<br />
person * temp;<br />
char ch;<br />
inputFile.open ( fileName ); //open input file<br />
if ( inputFile.fail () )<br />
{<br />
cout << "input file did not open! " << endl;<br />
return false;<br />
}<br />
temp = new person; //make new node in list<br />
if ( temp == 0 ) //if allocation error<br />
{<br />
cout << "allocation error! " << endl;<br />
return false;<br />
}<br />
itemsRead = 1; //start count at 1<br />
frontList = backList = temp; //set front and back pointers to new node<br />
temp -> prior = 0; //set new nodes prior to empty<br />
inputFile >> temp -> firstName; //get nodes data from file<br />
inputFile >> temp -> lastName;<br />
inputFile >> temp -> idNumber;<br />
ch = inputFile.peek(); //check for end of file character<br />
while ( isspace ( ch ) ) //skip white space<br />
{<br />
inputFile.get();<br />
ch = inputFile.peek();<br />
}<br />
while ( ch != STOP_SYMBOL ) //while not at end of file<br />
{<br />
temp -> next = new person; //make new item in the list<br />
if ( temp -> next == 0 ) //check allocation<br />
{<br />
cout << "allocation error! " << endl;<br />
destroyList ( frontList );<br />
return false;<br />
}<br />
temp -> next -> prior = temp; //set temp to point to new node<br />
temp -> next -> next = 0; //set next to empty<br />
temp = temp -> next;//move list pointer to next node<br />
backList = temp; //make new node the back of list<br />
inputFile >> temp -> firstName; //get data<br />
inputFile >> temp -> lastName;<br />
inputFile >> temp -> idNumber;<br />
ch = inputFile.peek(); //get white space<br />
while ( isspace ( ch ) )<br />
{<br />
inputFile.get();<br />
ch = inputFile.peek();<br />
}<br />
itemsRead ++;//count items read<br />
}<br />
<br />
return true;<br />
}<br />
/******************************* FUNCTION DEFINITION ******************************<br />
<br />
Name : quickSort<br />
Parameters :<br />
<br />
front a(n) person *&#038; ( person *&#038; )  ,<br />
last a(n) person *&#038; ( person *&#038; )  ,<br />
numberItems a(n) int ( int )<br />
<br />
<br />
Returns: Void type<br />
Comments:<br />
<br />
<br />
<br />
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/<br />
void quickSort ( person ** low , person ** high , int numberItems )<br />
{<br />
<br />
<br />
person * savedLow = * low; //lowt<br />
person * savedHigh = * high;//hight<br />
person * tempLow , * tempHigh;<br />
person * pivot; //pivot for sorting<br />
<br />
if ( numberItems <= 1 ) //nothing to sort<br />
return;<br />
if ( numberItems == 2  ) //if 2 items then swap if needed<br />
{<br />
tempLow = * low;<br />
tempHigh = * high;<br />
if ( strcmp ( key ( tempLow ) , key (  tempHigh ) ) > 0 ) //swap items if out of order<br />
swap ( &#038; tempLow , &#038; tempHigh , &#038; savedLow , &#038; savedHigh );<br />
* low = tempLow; //reset low and high pointers<br />
* high = tempHigh;<br />
return ; //end function<br />
}<br />
<br />
<br />
<br />
pivot =  savedHigh; //make the highest element in the array the pivot<br />
tempLow = savedLow; //start sorting at the lowest item in the list<br />
tempHigh = ( * savedHigh ).prior; //start sorting at the second to last item<br />
int lowCount = 1; //start counting at the first item for the low pointer<br />
int highCount = numberItems - 1; //start counting at the second to last item for high count<br />
<br />
do<br />
{<br />
<br />
//while items are less than the pivot move right<br />
while ( lowCount <= highCount  &#038;&#038;  ( strcmp ( key ( tempLow ) , key ( pivot ) ) < 0 || strcmp ( key ( tempLow ) , key ( pivot ) ) == 0 )  )<br />
{<br />
<br />
<br />
tempLow = tempLow -> next;<br />
lowCount ++; //increase count of items behind pointer<br />
if ( ! tempLow )<br />
break;<br />
}<br />
//while items are greater than the pivot move right<br />
while (  lowCount <= highCount &#038;&#038; ( strcmp ( key ( tempHigh ) , key ( pivot ) ) > 0 || strcmp ( key ( tempLow ) , key ( pivot ) ) == 0  ) )<br />
{<br />
<br />
<br />
tempHigh = tempHigh -> prior;<br />
highCount --; //decrease count of items before pointer<br />
if ( ! tempHigh )<br />
break;<br />
}<br />
<br />
if ( tempHigh ) //if top pointer has not crossed end of list , swap items<br />
swap ( &#038; tempLow , &#038; tempHigh ,  &#038; savedLow , &#038;  savedHigh );<br />
<br />
} while (  lowCount <= highCount &#038;&#038; tempHigh -> prior &#038;& tempLow -> next );<br />
<br />
if ( tempHigh ) //if high pointer has not passed the end to the list , exchange high and low pointers<br />
swap ( &#038; tempLow , &#038; tempHigh ,  &#038; savedLow , &#038;  savedHigh );<br />
<br />
//put pivot in middle of large item and small item lists<br />
tempHigh = savedHigh;<br />
swap ( &#038; tempLow ,  &#038; tempHigh , &#038;  savedLow , &#038;  savedHigh );<br />
//sort list of small items<br />
quickSort ( &#038; savedLow , &#038; tempLow -> prior , lowCount - 1  );<br />
//sort list of large items<br />
quickSort ( &#038; tempLow -> next , &#038; savedHigh , numberItems - lowCount  );<br />
//reset low and high pointers<br />
* low = savedLow;<br />
* high = savedHigh;<br />
<br />
return;<br />
}<br />
/******************************* FUNCTION DEFINITION ******************************<br />
<br />
Name : swap<br />
Parameters :<br />
<br />
first a(n) person *&#038; ( person *&#038; )  ,<br />
last a(n) person *&#038; ( person *&#038; )<br />
<br />
<br />
Returns: Void type<br />
Comments:  first<br />
<br />
<br />
<br />
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/<br />
void swap ( person ** left , person ** right , person ** front , person ** back )<br />
{<br />
<br />
<br />
if ( ! * left || !* right ) //if left or right pointer is null , stop<br />
return;<br />
if ( * left == * right )<br />
return;<br />
//reset the front and back pointers<br />
if ( ( * front ) == ( * left ) ) //if left == front<br />
{<br />
<br />
* front =  * right; //right is new front after swap<br />
}<br />
else if ( ( * front ) == ( * right ) ) //if right == front<br />
{<br />
<br />
* front = * left; //left is new front after swap<br />
}<br />
if ( ( * back ) == ( * left ) ) //if left == back<br />
{<br />
<br />
* back = * right; //right is back after swap<br />
}<br />
else if ( ( * back ) == ( * right ) ) //if right is back<br />
{<br />
<br />
* back =  * left; //left is back after swap<br />
}<br />
<br />
<br />
<br />
person * tempN , * tempP;<br />
<br />
tempN = ( * left ) -> next; //save left's next and prior node setting<br />
tempP = ( * left ) -> prior;<br />
<br />
//case 1: right node follows left in list<br />
if ( ( * right ) -> prior == * left )<br />
{<br />
( * left ) -> prior = ( * right ); //right is left's new prior node<br />
( * left ) -> next = ( * right ) -> next; //left's next node is right's old prior node<br />
if ( ( * left ) -> next ) //if left had a next node<br />
( * left ) -> next -> prior = ( * right ); //set that nodes prior to right<br />
( * right ) -> next = ( * left ); //right's next now is left<br />
( * right ) -> prior = tempP; //right's new prior is left's old prior<br />
if ( tempP ) //if left's old prior is not null<br />
tempP -> next = ( * right ); //left's old prior's next is right<br />
}<br />
//case 2: left follows right in the list<br />
else if ( ( * left) -> prior == ( * right ) )<br />
{<br />
( * left ) -> prior = ( * right ) -> prior; //left's prior is now right's prior<br />
( * left ) -> next = ( * right ); //left's next is now right<br />
if ( ( * right ) -> prior ) //if right's prior is not null<br />
( * right ) -> prior -> next = ( * left ); //set its next to left<br />
( * right ) -> prior = ( * left ); //right comes after left node now<br />
( * right ) -> next = tempN; //right's next is left's old next<br />
if ( tempN ) //if left's old next is non-null<br />
tempN -> prior = ( * right ); //set its prior to right<br />
}<br />
//case 3: the two nodes are seperated by other nodes<br />
else<br />
{<br />
( * left ) -> prior = ( * right ) -> prior; //left's prior equal's right's<br />
( * left ) -> next =  ( * right ) -> next; //left's next equal's right's<br />
<br />
if ( ( * right ) -> next ) //if right's next is non-null<br />
( * right ) -> next -> prior = ( * left ); //set it's prior to left<br />
if ( ( * right ) -> prior )//if right's prior is non-null<br />
( * right ) -> prior -> next = ( * left ); //it's next now equals left<br />
( * right ) -> prior = tempP; //right's prior now == left's<br />
( * right ) -> next = tempN;  //right's next now == left's<br />
if ( tempP ) //if left's prior was non-null<br />
tempP -> next = ( * right ); //set its next to right<br />
if ( tempN ) //if left's next was non-null<br />
tempN -> prior = ( * right );//set its prior to right<br />
}<br />
<br />
<br />
person * temp = ( * left ); //swap left and right pointers to save<br />
person * temp2 = ( * right );//position of pointers in the list<br />
( * left ) = temp2;<br />
( * right ) = temp;<br />
<br />
return;<br />
}<br />
/******************************* FUNCTION DEFINITION ******************************<br />
<br />
Name : print<br />
Parameters :<br />
<br />
list a(n) person * ( person * )<br />
<br />
<br />
Returns: Void type<br />
Comments:<br />
<br />
<br />
<br />
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/<br />
void print ( person * list )<br />
{<br />
<br />
cout << endl;<br />
<br />
cout << setiosflags ( ios::left );<br />
cout << setw ( OUTPUT_SPACES ) << "first name"<br />
<< setw ( OUTPUT_SPACES ) << "last name"<br />
<< setw ( OUTPUT_SPACES ) << "id number" << endl << endl;<br />
while ( list ) //while not at the end of the list<br />
{<br />
//output name ect....<br />
cout << setw ( OUTPUT_SPACES ) << list -> firstName << " " << setw ( OUTPUT_SPACES ) << list -> lastName << " " << setw ( OUTPUT_SPACES ) << list -> idNumber << endl;<br />
list = list -> next;<br />
<br />
}<br />
<br />
return;<br />
}<br />
<br />
/******************************* FUNCTION DEFINITION ******************************<br />
<br />
Name : destroyList<br />
Parameters :<br />
<br />
list a(n) person * ( person * )<br />
<br />
<br />
Returns: Void type<br />
Comments:<br />
<br />
<br />
<br />
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/<br />
void destroyList ( person * list )<br />
{<br />
<br />
person * temp;<br />
<br />
while ( list ) //for each item in the list , destroy the list<br />
{<br />
temp = list;<br />
list = list -> next;<br />
delete temp;<br />
}<br />
<br />
<br />
return;<br />
}<br />
/******************************* FUNCTION DEFINITION ******************************<br />
<br />
Name : key<br />
Parameters :<br />
<br />
first a(n) person * ( person * )  ,<br />
second a(n) person * ( person * )<br />
<br />
<br />
Returns: char type<br />
Comments: use a macro for this......<br />
<br />
<br />
<br />
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/<br />
char * key ( person * node )<br />
{<br />
<br />
switch ( sortKey )<br />
{<br />
case firstName:<br />
return node -> firstName;<br />
case lastName:<br />
return node -> lastName;<br />
case idNumber:<br />
return node -> idNumber;<br />
<br />
};<br />
<br />
<br />
}<br />

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

/****************************************************************

* File Name : c:programstempCG.cpp

* Date : January,6,2008

* Comments : new project

* Compiler/Assembler :

* Modifications :

*

* Program Shell Generated At: 3:51:46 p.m.

=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/

#include < iostream >

#include < fstream >

//#include < string.h >

//#include < conio.h >

//#include < math.h >

#include < iomanip >

#include < ctype.h >

using namespace std;

//>>>>>>>>>>>>>>>>>>>>>>>> GLOBAL DATA <<<<<<<<<<<<<<<<<<<<<<<<<

const int MAX_NAME = 50;

const int MAX_FILE_NAME = 50;

const char STOP_SYMBOL = '*';

enum keys { firstName , lastName , idNumber };

keys sortKey ;

#define OUTPUT_SPACES 15

//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

struct person

{

char firstName [ MAX_NAME ] ;

char lastName [ MAX_NAME ] ;

char idNumber [ MAX_NAME ] ;

person * prior;

person * next;

};

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@

bool readInputFile ( char * fileName , person *& frontList , person *& backList , int & itemsRead );

void quickSort ( person ** front , person ** last , int numberItems );

void swap ( person ** first , person ** last , person ** front , person ** back );

void print ( person * list );

void insertionSort ( person * list , int numberOfItems );

void destroyList ( person * list );

char * key ( person * node );

//##################################################################################

//main function ******************************

int main ( )

{

person * front , * back;

int items;

sortKey = firstName;

readInputFile ( "c:\programs\data.txt" , front , back , items );

print ( front );

quickSort ( & front , & back , items );

cout << endl << endl;

cout << "final ************************" << endl;

print ( front );

destroyList ( front );

return 0 ;

}

/******************************* FUNCTION DEFINITION ******************************

Name : readInputFile

Parameters :

fileName a(n) char * ,

frontList a(n) person *& ( person *& ) ,

backList a(n) person *& ( person *& ) ,

itemsRead a(n) int &

Returns: bool type

Comments:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

bool readInputFile ( char * fileName , person *& frontList , person *& backList , int & itemsRead )

{

fstream inputFile;

person * temp;

char ch;

inputFile.open ( fileName ); //open input file

if ( inputFile.fail () )

{

cout << "input file did not open! " << endl;

return false;

}

temp = new person; //make new node in list

if ( temp == 0 ) //if allocation error

{

cout << "allocation error! " << endl;

return false;

}

itemsRead = 1; //start count at 1

frontList = backList = temp; //set front and back pointers to new node

temp -> prior = 0; //set new nodes prior to empty

inputFile >> temp -> firstName; //get nodes data from file

inputFile >> temp -> lastName;

inputFile >> temp -> idNumber;

ch = inputFile.peek(); //check for end of file character

while ( isspace ( ch ) ) //skip white space

{

inputFile.get();

ch = inputFile.peek();

}

while ( ch != STOP_SYMBOL ) //while not at end of file

{

temp -> next = new person; //make new item in the list

if ( temp -> next == 0 ) //check allocation

{

cout << "allocation error! " << endl;

destroyList ( frontList );

return false;

}

temp -> next -> prior = temp; //set temp to point to new node

temp -> next -> next = 0; //set next to empty

temp = temp -> next;//move list pointer to next node

backList = temp; //make new node the back of list

inputFile >> temp -> firstName; //get data

inputFile >> temp -> lastName;

inputFile >> temp -> idNumber;

ch = inputFile.peek(); //get white space

while ( isspace ( ch ) )

{

inputFile.get();

ch = inputFile.peek();

}

itemsRead ++;//count items read

}

return true;

}

/******************************* FUNCTION DEFINITION ******************************

Name : quickSort

Parameters :

front a(n) person *& ( person *& ) ,

last a(n) person *& ( person *& ) ,

numberItems a(n) int ( int )

Returns: Void type

Comments:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void quickSort ( person ** low , person ** high , int numberItems )

{

person * savedLow = * low; //lowt

person * savedHigh = * high;//hight

person * tempLow , * tempHigh;

person * pivot; //pivot for sorting

if ( numberItems <= 1 ) //nothing to sort

return;

if ( numberItems == 2 ) //if 2 items then swap if needed

{

tempLow = * low;

tempHigh = * high;

if ( strcmp ( key ( tempLow ) , key ( tempHigh ) ) > 0 ) //swap items if out of order

swap ( & tempLow , & tempHigh , & savedLow , & savedHigh );

* low = tempLow; //reset low and high pointers

* high = tempHigh;

return ; //end function

}

pivot = savedHigh; //make the highest element in the array the pivot

tempLow = savedLow; //start sorting at the lowest item in the list

tempHigh = ( * savedHigh ).prior; //start sorting at the second to last item

int lowCount = 1; //start counting at the first item for the low pointer

int highCount = numberItems - 1; //start counting at the second to last item for high count

do

{

//while items are less than the pivot move right

while ( lowCount <= highCount && ( strcmp ( key ( tempLow ) , key ( pivot ) ) < 0 || strcmp ( key ( tempLow ) , key ( pivot ) ) == 0 ) )

{

tempLow = tempLow -> next;

lowCount ++; //increase count of items behind pointer

if ( ! tempLow )

break;

}

//while items are greater than the pivot move right

while ( lowCount <= highCount && ( strcmp ( key ( tempHigh ) , key ( pivot ) ) > 0 || strcmp ( key ( tempLow ) , key ( pivot ) ) == 0 ) )

{

tempHigh = tempHigh -> prior;

highCount --; //decrease count of items before pointer

if ( ! tempHigh )

break;

}

if ( tempHigh ) //if top pointer has not crossed end of list , swap items

swap ( & tempLow , & tempHigh , & savedLow , & savedHigh );

} while ( lowCount <= highCount && tempHigh -> prior && tempLow -> next );

if ( tempHigh ) //if high pointer has not passed the end to the list , exchange high and low pointers

swap ( & tempLow , & tempHigh , & savedLow , & savedHigh );

//put pivot in middle of large item and small item lists

tempHigh = savedHigh;

swap ( & tempLow , & tempHigh , & savedLow , & savedHigh );

//sort list of small items

quickSort ( & savedLow , & tempLow -> prior , lowCount - 1 );

//sort list of large items

quickSort ( & tempLow -> next , & savedHigh , numberItems - lowCount );

//reset low and high pointers

* low = savedLow;

* high = savedHigh;

return;

}

/******************************* FUNCTION DEFINITION ******************************

Name : swap

Parameters :

first a(n) person *& ( person *& ) ,

last a(n) person *& ( person *& )

Returns: Void type

Comments: first

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void swap ( person ** left , person ** right , person ** front , person ** back )

{

if ( ! * left || !* right ) //if left or right pointer is null , stop

return;

if ( * left == * right )

return;

//reset the front and back pointers

if ( ( * front ) == ( * left ) ) //if left == front

{

* front = * right; //right is new front after swap

}

else if ( ( * front ) == ( * right ) ) //if right == front

{

* front = * left; //left is new front after swap

}

if ( ( * back ) == ( * left ) ) //if left == back

{

* back = * right; //right is back after swap

}

else if ( ( * back ) == ( * right ) ) //if right is back

{

* back = * left; //left is back after swap

}

person * tempN , * tempP;

tempN = ( * left ) -> next; //save left's next and prior node setting

tempP = ( * left ) -> prior;

//case 1: right node follows left in list

if ( ( * right ) -> prior == * left )

{

( * left ) -> prior = ( * right ); //right is left's new prior node

( * left ) -> next = ( * right ) -> next; //left's next node is right's old prior node

if ( ( * left ) -> next ) //if left had a next node

( * left ) -> next -> prior = ( * right ); //set that nodes prior to right

( * right ) -> next = ( * left ); //right's next now is left

( * right ) -> prior = tempP; //right's new prior is left's old prior

if ( tempP ) //if left's old prior is not null

tempP -> next = ( * right ); //left's old prior's next is right

}

//case 2: left follows right in the list

else if ( ( * left) -> prior == ( * right ) )

{

( * left ) -> prior = ( * right ) -> prior; //left's prior is now right's prior

( * left ) -> next = ( * right ); //left's next is now right

if ( ( * right ) -> prior ) //if right's prior is not null

( * right ) -> prior -> next = ( * left ); //set its next to left

( * right ) -> prior = ( * left ); //right comes after left node now

( * right ) -> next = tempN; //right's next is left's old next

if ( tempN ) //if left's old next is non-null

tempN -> prior = ( * right ); //set its prior to right

}

//case 3: the two nodes are seperated by other nodes

else

{

( * left ) -> prior = ( * right ) -> prior; //left's prior equal's right's

( * left ) -> next = ( * right ) -> next; //left's next equal's right's

if ( ( * right ) -> next ) //if right's next is non-null

( * right ) -> next -> prior = ( * left ); //set it's prior to left

if ( ( * right ) -> prior )//if right's prior is non-null

( * right ) -> prior -> next = ( * left ); //it's next now equals left

( * right ) -> prior = tempP; //right's prior now == left's

( * right ) -> next = tempN; //right's next now == left's

if ( tempP ) //if left's prior was non-null

tempP -> next = ( * right ); //set its next to right

if ( tempN ) //if left's next was non-null

tempN -> prior = ( * right );//set its prior to right

}

person * temp = ( * left ); //swap left and right pointers to save

person * temp2 = ( * right );//position of pointers in the list

( * left ) = temp2;

( * right ) = temp;

return;

}

/******************************* FUNCTION DEFINITION ******************************

Name : print

Parameters :

list a(n) person * ( person * )

Returns: Void type

Comments:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void print ( person * list )

{

cout << endl;

cout << setiosflags ( ios::left );

cout << setw ( OUTPUT_SPACES ) << "first name"

<< setw ( OUTPUT_SPACES ) << "last name"

<< setw ( OUTPUT_SPACES ) << "id number" << endl << endl;

while ( list ) //while not at the end of the list

{

//output name ect....

cout << setw ( OUTPUT_SPACES ) << list -> firstName << " " << setw ( OUTPUT_SPACES ) << list -> lastName << " " << setw ( OUTPUT_SPACES ) << list -> idNumber << endl;

list = list -> next;

}

return;

}

/******************************* FUNCTION DEFINITION ******************************

Name : destroyList

Parameters :

list a(n) person * ( person * )

Returns: Void type

Comments:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void destroyList ( person * list )

{

person * temp;

while ( list ) //for each item in the list , destroy the list

{

temp = list;

list = list -> next;

delete temp;

}

return;

}

/******************************* FUNCTION DEFINITION ******************************

Name : key

Parameters :

first a(n) person * ( person * ) ,

second a(n) person * ( person * )

Returns: char type

Comments: use a macro for this......

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

char * key ( person * node )

{

switch ( sortKey )

{

case firstName:

return node -> firstName;

case lastName:

return node -> lastName;

case idNumber:

return node -> idNumber;

};

}

input:

<br />
bob johns 222<br />
suzie barker 333<br />
adam west 555<br />
zack wilde 111<br />
janet woods 444<br />
qubert johns 666<br />
barak obama 777<br />
carly simon 888<br />
curt cobain 999<br />
tom gadja 1010<br />
larry bear 1111<br />
pilar nuffer 1212<br />
mikey scalcee 1313<br />
old puff      1414<br />
charolette phifer 1515<br />
don dokken 46464<br />
adam ant 555<br />
willodean mcqueen 222<br />
*<br />

bob johns 222

suzie barker 333

adam west 555

zack wilde 111

janet woods 444

qubert johns 666

barak obama 777

carly simon 888

curt cobain 999

tom gadja 1010

larry bear 1111

pilar nuffer 1212

mikey scalcee 1313

old puff 1414

charolette phifer 1515

don dokken 46464

adam ant 555

willodean mcqueen 222

*

output ( sorting with first name as key ):

<br />
first name     last name      id number<br />
<br />
adam            ant             555<br />
adam            west            555<br />
barak           obama           777<br />
bob             johns           222<br />
carly           simon           888<br />
charolette      phifer          1515<br />
curt            cobain          999<br />
don             dokken          46464<br />
janet           woods           444<br />
larry           bear            1111<br />
mikey           scalcee         1313<br />
old             puff            1414<br />
pilar           nuffer          1212<br />
qubert          johns           666<br />
suzie           barker          333<br />
tom             gadja           1010<br />
willodean       mcqueen         222<br />
zack            wilde           111<br />
Press any key to continue<br />

first name last name id number

adam ant 555

adam west 555

barak obama 777

bob johns 222

carly simon 888

charolette phifer 1515

curt cobain 999

don dokken 46464

janet woods 444

larry bear 1111

mikey scalcee 1313

old puff 1414

pilar nuffer 1212

qubert johns 666

suzie barker 333

tom gadja 1010

willodean mcqueen 222

zack wilde 111

Press any key to continue