Dec 162017

## Full Description of File

List-based MergSort Example

(Bryan Flamig; $0) is the C++ source

code that shows a way to sort

singly-linked lists, using a

non-recursive merge sort algorithm.

(Bryan Flamig; $0) is the C++ source

code that shows a way to sort

singly-linked lists, using a

non-recursive merge sort algorithm.

List-based MergeSort Example from the upcoming book Practical Algorithms in C++. | |||
---|---|---|---|

File Name | File Size | Zip Size | Zip Type |

FILE_ID.DIZ | 176 | 140 | deflated |

MERGSORT.CPP | 8220 | 2697 | deflated |

MERGSORT.PRJ | 5051 | 1054 | deflated |

README | 10283 | 4435 | deflated |

# Download File MERGSORT.ZIP Here

## Contents of the README file

List-based MergSort Example

(Bryan Flamig; $0) is the C++ source

code that shows a way to sort

singly-linked lists, using a

non-recursive merge sort algorithm.

List-based MergeSort Example

from the upcoming book

Practical Algorithms in C++

README FILE

Copyright(c) 1993 Azarona Software

All rights reserved.

August 28, 1993

INTRODUCTION

============

The included files show a way to sort singly-linked lists, using a

non-recursive merge sort algorithm. The code is part of the upcoming

book "Practical Algorithms in C++", by Bryan Flamig.

The algorithm used is reminiscent of external sorting algorithms

normally used to sort files. The basic idea is to first split the

list in half, and then merge-sort the nodes in blocks, first with

block sizes of 1, then 2, then 4, and so on until the list is sorted.

To do this, 4 working lists are used, divided into two groups. At

any one time, one of the groups will be used for input, the other

two for output. The sorting is finished when there is only one output

list. Here is an example:

Original list: [DOGZILLAGOESTOTHEMOUNTAINS]

Split list in half, alternating between two output lists:

list 1: [DGILGETTEONAN]

list 2: [OZLAOSOHMUTIS]

1st pass: Merge 1-blocks into 2-blocks, sort in process

list 3: [DO IL GO OT EM NT NS]

list 4: [GZ AL ES HT OU AI]

2nd pass: Merge 2-blocks into 4-blocks, sort in process

list 1: [DOGZ GEOS EMOU NS]

list 2: [AILL HOTT AINT]

3rd pass: Merge 4-blocks into 8-blocks, sort in process

list 3: [ADGILLOZ AEIMNOTU]

list 4: [EGHOOSTT NS]

4th pass: Merge 8-blocks into 16-blocks, sort in process

list 1: [ADEGGHILLOOOSTTZ]

list 2: [AEIMNNOSTU]

5th pass: Merge 16-blocks into 32-blocks

list 3: [AADEEGGHIILLMNNOOOOSSTTTUZ]

list 4: []

We're done! List 3 contains the result.

Each pass does approximately n/2 comparisons, (sometimes less)

where n is the length of the list, and there will be logn passes,

thus this is a O(nlogn) sort. Also, this sort is stable as well,

(meaning that if two keys are identical, they will have the same

relative positions in the sorted list as they had in the unsorted

list.)

On a 33Mhz 486 machine, this routine can sort a list of 30,000

integer nodes in 1 second!

OTHER MERGE SORT ALGORITHMS

===========================

There are other books that show the merge sort algorithm for

linked lists, both recursively and non-recursively. However, in

all of the books this author has seen, the process of splitting

the list into two in order to do the merging is done in a rather

naive way, scanning down the list looking for the "middle" in

order to split the list in two. This is quite wasteful.

Surprisingly, some of these same books show, in later chapters,

techniques for doing external sorting, that if applied to linked

lists, would do away with the wasteful scanning to find the

midpoint! The technique used for external sorting is what I used

to implement the linked-list merge sort algorithm given here.

TYPE OF LISTS SORTED

====================

The code as given here sorts singly-linked lists that are

null-terminated and have no headers. I did this because

most people will understand that type of list. The nodes

of the list are assumed to hold data of type Item, and

Item is assumed to have the appropriate comparison operators

defined. (For ascending sorts, we use <=, for descending,

>= is used.) NOTE THAT YOU MUST USE <= or >= and not < or >,

otherwise, the sort will not be stable.

This sort routine can be templated quite easily, as you might

surmise. Also, it's possible to make slight modifications to

the routine to make it work for circular singly-linked lists

that have dummy headers, for example, the Slist template class

as given in the companion book "Practical Data Structures in

C++". Here is a sketch of the necessary changes. (We show the

code here in template form):

template

void MergeSort(Slist &v)

{

// Check for empty or one-node list

if (v.IsHeader(v.Front()) || v.IsHeader(v.Front()->Next())) return;

v.CircularToNullTerm(); // Convert to null-terminated form

// Rest of merge-sort algorithm up to last statement as before,

// except use Snode.

// At this point, p points to first node of sorted list, r

// points to the last node. Convert back to circular list.

v.NullTermToCircular(p, r);

}

If you examine the MergeSort() routine, you'll notice there is only

one statement that relies on the type of data in the node: the single

comparison during merging. If you use the Slist class, along with

it's dataless Slistb base class, it's possible to write the MergeSort()

routine as a non-templated class that works for the whole family of

Slist classes. Simply use Slistb and Snodeb (these are dataless),

instead of Slist and Snode. Then pass in a pointer to

the function to use for comparison, for your type of nodes. For

example:

void MergeSort(Slistb &sl, int (*Compare)(Snodeb *a, Snodeb *b))

{

... Use Slistb and Snodeb throughout ...

}

For lists holding integers, the Compare() function might be coded

as follows:

int IntLessThan(Snodeb *a, Snodeb *b)

{

return ((Snode *)a)->info - ((Snode *)b)->info;

}

Slist sl;

...

MergeSort(sl, IntLessThan);

Although this elegantly reuses the MergeSort() code for all

Slist list's, having to use a pointer to the Compare()

function rather than doing a simple comparison operator may

slow down the algorithm by as much as 50% for lists holding

simple integers. Of course, if you have to use an overloaded

comparison operator function for your type of data anyway,

then you may not see much performance drop.

COPYRIGHTED SOFTWARE

====================

The source code is copyrighted by Azarona Software, but I'm

providing it to you free of charge. You are free to experiment

with the code, include compiled versions of it in your own

applications, personal or commercial. HOWEVER, YOU MAY NOT

DISTRIBUTE THE SOURCE CODE FOR A PROFIT OR FEE OF ANY KIND

WITHOUT THE EXPRESS WRITTEN PERMISSION OF AZARONA SOFTWARE.

You are granted permission to give away the source code to

friends, upload the files to a BBS, etc., AS LONG AS NO FEE

IS CHARGED FOR THE SOFTWARE, AND AS LONG AS THE FILES ARE

DISTRIBUTED EXACTLY AS GIVEN HERE, WITH THE SAME FILE NAMES,

THE SAME NUMBER OF FILES, AND THE COPYRIGHT NOTICES INTACT.

You may "zip" the files into a single-file archive, if you wish.

PRACTICAL ALGORITHMS IN C++ BOOK

================================

This is the companion volume to the "Practical Data Structures in

C++" book, due in the Spring of 1994. While I can't say for certain

exactly what will be covered in this book, here is a list of

possible candidate topics:

* Sorting (insertion, shell, heap, quick, merge, external)

* Hashing (closed and open), creating symbol tables

* Priority queues as heaps

* Graphs, including algorithms for depth-first, breadth-first,

best-first, (A*-algorithms), topological sorting, etc.

* Randon number generation, including array shuffling, and

taking random samples from known and unknown population sizes

* String searching, such as Boyer-Moore-Horspool, and others

* Finite automata machines

* Recursive descent parsing

* Regular expression matching

* Compression, including huffman and sliding-window dictionaries

* Simultaneous equation solving using LU matrix decomposition

PRACTICAL DATA STRUCTURES IN C++ BOOK

=====================================

Practical Data Structures in C++

Author: Bryan Flamig

Publisher: John Wiley & Sons

ISBN 0-471-55863-X

This book retails for $42.95, and includes a code disk, packed with

over a megabyte of source code. Subjects covered are dynamic arrays,

smart pointers, reference counting, strings, vectors, matrices,

linked lists, stacks, queues, binary trees, splay trees, red-black

trees, file-based objects, caching, and B-trees. The book is based

heavily on templates, and includes some useful C++ tricks. The

book is for intermediate to advanced C++ programmers.

Unlike most data structures books, this book focuses on giving

you complete code, and complete techniques. For instance, many

books talk about red-black trees and splay trees, but very few

show you how to delete nodes from these trees! This book does.

Also, many books give lip service to B-trees, but few books

actually give you the code for them, and amazingly, few books

implement them for disk-based trees, which is curious, since

B-trees were designed with disk-based trees in mind!

Also, most data structures books currently on the market were

written for Pascal, or worse, written in pseudo-code. This

book, in contrast, was written specifically for C++, and exploits

the capabilities of C++ to the fullest. You won't find any vague

pseudo-code here.

COMPILER USED

=============

This code was developed using BC++ 3.1, and hasn't been tried

with other compilers, although I don't anticipate any troubles.

PACKING LIST

============

MERGSORT.CPP Merge sort testing program

MERGSORT.PRJ BC++ 3.1 project file for testing program

README This readme file

ABOUT THE AUTHOR

================

Bryan Flamig is a software developer and consultant specializing in

C++ programming. He is the author of numerous books, including the

popular "Turbo C++: Step by Step", and coauthor of "Object-Oriented

Programming with Turbo C++", and of course, the author of "Practical

Data Structures in C++", all published by John Wiley & Sons.

Besides consulting and writing books, Bryan also gives training

seminars focusing on C++. You may reach Bryan at:

Azarona Software

P.O. Box 768

Conifer, CO 80433

(303) 697-1728 Fax

73057,3172 CompuServe

(Bryan Flamig; $0) is the C++ source

code that shows a way to sort

singly-linked lists, using a

non-recursive merge sort algorithm.

List-based MergeSort Example

from the upcoming book

Practical Algorithms in C++

README FILE

Copyright(c) 1993 Azarona Software

All rights reserved.

August 28, 1993

INTRODUCTION

============

The included files show a way to sort singly-linked lists, using a

non-recursive merge sort algorithm. The code is part of the upcoming

book "Practical Algorithms in C++", by Bryan Flamig.

The algorithm used is reminiscent of external sorting algorithms

normally used to sort files. The basic idea is to first split the

list in half, and then merge-sort the nodes in blocks, first with

block sizes of 1, then 2, then 4, and so on until the list is sorted.

To do this, 4 working lists are used, divided into two groups. At

any one time, one of the groups will be used for input, the other

two for output. The sorting is finished when there is only one output

list. Here is an example:

Original list: [DOGZILLAGOESTOTHEMOUNTAINS]

Split list in half, alternating between two output lists:

list 1: [DGILGETTEONAN]

list 2: [OZLAOSOHMUTIS]

1st pass: Merge 1-blocks into 2-blocks, sort in process

list 3: [DO IL GO OT EM NT NS]

list 4: [GZ AL ES HT OU AI]

2nd pass: Merge 2-blocks into 4-blocks, sort in process

list 1: [DOGZ GEOS EMOU NS]

list 2: [AILL HOTT AINT]

3rd pass: Merge 4-blocks into 8-blocks, sort in process

list 3: [ADGILLOZ AEIMNOTU]

list 4: [EGHOOSTT NS]

4th pass: Merge 8-blocks into 16-blocks, sort in process

list 1: [ADEGGHILLOOOSTTZ]

list 2: [AEIMNNOSTU]

5th pass: Merge 16-blocks into 32-blocks

list 3: [AADEEGGHIILLMNNOOOOSSTTTUZ]

list 4: []

We're done! List 3 contains the result.

Each pass does approximately n/2 comparisons, (sometimes less)

where n is the length of the list, and there will be logn passes,

thus this is a O(nlogn) sort. Also, this sort is stable as well,

(meaning that if two keys are identical, they will have the same

relative positions in the sorted list as they had in the unsorted

list.)

On a 33Mhz 486 machine, this routine can sort a list of 30,000

integer nodes in 1 second!

OTHER MERGE SORT ALGORITHMS

===========================

There are other books that show the merge sort algorithm for

linked lists, both recursively and non-recursively. However, in

all of the books this author has seen, the process of splitting

the list into two in order to do the merging is done in a rather

naive way, scanning down the list looking for the "middle" in

order to split the list in two. This is quite wasteful.

Surprisingly, some of these same books show, in later chapters,

techniques for doing external sorting, that if applied to linked

lists, would do away with the wasteful scanning to find the

midpoint! The technique used for external sorting is what I used

to implement the linked-list merge sort algorithm given here.

TYPE OF LISTS SORTED

====================

The code as given here sorts singly-linked lists that are

null-terminated and have no headers. I did this because

most people will understand that type of list. The nodes

of the list are assumed to hold data of type Item, and

Item is assumed to have the appropriate comparison operators

defined. (For ascending sorts, we use <=, for descending,

>= is used.) NOTE THAT YOU MUST USE <= or >= and not < or >,

otherwise, the sort will not be stable.

This sort routine can be templated quite easily, as you might

surmise. Also, it's possible to make slight modifications to

the routine to make it work for circular singly-linked lists

that have dummy headers, for example, the Slist template class

as given in the companion book "Practical Data Structures in

C++". Here is a sketch of the necessary changes. (We show the

code here in template form):

template

void MergeSort(Slist

{

// Check for empty or one-node list

if (v.IsHeader(v.Front()) || v.IsHeader(v.Front()->Next())) return;

v.CircularToNullTerm(); // Convert to null-terminated form

// Rest of merge-sort algorithm up to last statement as before,

// except use Snode

// At this point, p points to first node of sorted list, r

// points to the last node. Convert back to circular list.

v.NullTermToCircular(p, r);

}

If you examine the MergeSort() routine, you'll notice there is only

one statement that relies on the type of data in the node: the single

comparison during merging. If you use the Slist class, along with

it's dataless Slistb base class, it's possible to write the MergeSort()

routine as a non-templated class that works for the whole family of

Slist

instead of Slist

the function to use for comparison, for your type of nodes. For

example:

void MergeSort(Slistb &sl, int (*Compare)(Snodeb *a, Snodeb *b))

{

... Use Slistb and Snodeb throughout ...

}

For lists holding integers, the Compare() function might be coded

as follows:

int IntLessThan(Snodeb *a, Snodeb *b)

{

return ((Snode

}

Slist

...

MergeSort(sl, IntLessThan);

Although this elegantly reuses the MergeSort() code for all

Slist

function rather than doing a simple comparison operator may

slow down the algorithm by as much as 50% for lists holding

simple integers. Of course, if you have to use an overloaded

comparison operator function for your type of data anyway,

then you may not see much performance drop.

COPYRIGHTED SOFTWARE

====================

The source code is copyrighted by Azarona Software, but I'm

providing it to you free of charge. You are free to experiment

with the code, include compiled versions of it in your own

applications, personal or commercial. HOWEVER, YOU MAY NOT

DISTRIBUTE THE SOURCE CODE FOR A PROFIT OR FEE OF ANY KIND

WITHOUT THE EXPRESS WRITTEN PERMISSION OF AZARONA SOFTWARE.

You are granted permission to give away the source code to

friends, upload the files to a BBS, etc., AS LONG AS NO FEE

IS CHARGED FOR THE SOFTWARE, AND AS LONG AS THE FILES ARE

DISTRIBUTED EXACTLY AS GIVEN HERE, WITH THE SAME FILE NAMES,

THE SAME NUMBER OF FILES, AND THE COPYRIGHT NOTICES INTACT.

You may "zip" the files into a single-file archive, if you wish.

PRACTICAL ALGORITHMS IN C++ BOOK

================================

This is the companion volume to the "Practical Data Structures in

C++" book, due in the Spring of 1994. While I can't say for certain

exactly what will be covered in this book, here is a list of

possible candidate topics:

* Sorting (insertion, shell, heap, quick, merge, external)

* Hashing (closed and open), creating symbol tables

* Priority queues as heaps

* Graphs, including algorithms for depth-first, breadth-first,

best-first, (A*-algorithms), topological sorting, etc.

* Randon number generation, including array shuffling, and

taking random samples from known and unknown population sizes

* String searching, such as Boyer-Moore-Horspool, and others

* Finite automata machines

* Recursive descent parsing

* Regular expression matching

* Compression, including huffman and sliding-window dictionaries

* Simultaneous equation solving using LU matrix decomposition

PRACTICAL DATA STRUCTURES IN C++ BOOK

=====================================

Practical Data Structures in C++

Author: Bryan Flamig

Publisher: John Wiley & Sons

ISBN 0-471-55863-X

This book retails for $42.95, and includes a code disk, packed with

over a megabyte of source code. Subjects covered are dynamic arrays,

smart pointers, reference counting, strings, vectors, matrices,

linked lists, stacks, queues, binary trees, splay trees, red-black

trees, file-based objects, caching, and B-trees. The book is based

heavily on templates, and includes some useful C++ tricks. The

book is for intermediate to advanced C++ programmers.

Unlike most data structures books, this book focuses on giving

you complete code, and complete techniques. For instance, many

books talk about red-black trees and splay trees, but very few

show you how to delete nodes from these trees! This book does.

Also, many books give lip service to B-trees, but few books

actually give you the code for them, and amazingly, few books

implement them for disk-based trees, which is curious, since

B-trees were designed with disk-based trees in mind!

Also, most data structures books currently on the market were

written for Pascal, or worse, written in pseudo-code. This

book, in contrast, was written specifically for C++, and exploits

the capabilities of C++ to the fullest. You won't find any vague

pseudo-code here.

COMPILER USED

=============

This code was developed using BC++ 3.1, and hasn't been tried

with other compilers, although I don't anticipate any troubles.

PACKING LIST

============

MERGSORT.CPP Merge sort testing program

MERGSORT.PRJ BC++ 3.1 project file for testing program

README This readme file

ABOUT THE AUTHOR

================

Bryan Flamig is a software developer and consultant specializing in

C++ programming. He is the author of numerous books, including the

popular "Turbo C++: Step by Step", and coauthor of "Object-Oriented

Programming with Turbo C++", and of course, the author of "Practical

Data Structures in C++", all published by John Wiley & Sons.

Besides consulting and writing books, Bryan also gives training

seminars focusing on C++. You may reach Bryan at:

Azarona Software

P.O. Box 768

Conifer, CO 80433

(303) 697-1728 Fax

73057,3172 CompuServe

December 16, 2017
Add comments