Bertel Lund Hansens hjemmeside

Sorting algorithms

Introduction

I have made two programs with different sorting methods because I found it interesting. The programs show a screen with random characters, which can be sorted by nine different methods. You can "see" on the screen how the methods work. The programs are not useful as such, but they helped me understand how sorting works.

Both programs and code are Freeware. Here is a
download link to a zippackage with everything included.

The methods are:

  1. InsertSort
  2. BubbleSort
  3. ShellSort (Bubble)
  4. ShellSort (Insert)
  5. HeapSort
  6. MergeSort
  7. QuickSort
  8. SelectSort
  9. RadixSort

Practical information

The programs are all compiled for Windows, where sortdemo_old.exe runs under Windows up to XP (and partly under Windows 7, 32 bit). The other version should be able to run on any Windows OS. It has been tested with Windows 7, 8 and 10. If you want to run them under other OS'es, you must compile them yourself. The C-module conio.h is Windows-specific. That may prove to be a problem. Another Windows module is optional and can be deselected by undefining windows.h_available.

The programs will only work in a command box. The display breaks down in a Power Shell box. If you use the Power Shell, you can temporarily disable it here:

  • Options - Personal setup - Process line:
  • At the bottom set "Replace command prompt with Power Shell": No

The size of the sorted area depends on the size of the command box. The dimensions are registered when the program is activated, so you need to change the window before that. The registration of the vertical size unfortunately does not change with the window size, so the number of lines can be adjusted manually. The width is set automatically.

If the module windows.h_available is available, the program con give a sound signal when the sorting is finished. Modern EU-compatible lousy loudspeakers wil enter standby after a long silent period. Therefore you can choose a sound duration of 5 seconds - enough to wake up the speaker and then give a signal.

It is possible to maximize the command box in Windows.

General info

Radixsort, HeapSort and MergeSort need extra memory, and QuickSort needs extra heapsize.

I haven't found a meaningful way to display the operation of Radixsort, because it sorts in the background, and I haven't found a sensible way to introduce delay and interuption, so the results can't be compared to the other results (and are not remembered). I just implemented it for the exercise and the completenes (though I later learned that there are several other sorting routines available).

The source code is in the packet. The routines are more complicated than a pure version, because the operation is made visible, and the routines can be interrupted. There are pages on the net where pure versions of the algorithms can be found.

There are two version of the program. The first one was written in TurboPascal and compiled in 1995. I no longer have a TurboPascal compiler (No, FreePascal is not entirely compatible with TurboPascal). The second one is written in C and needs the conio.h module at compile time. If you use another module, changes must be made in the code.

Notes on speed

Apart from the measuring the time, the number of plots and the number of comparisons are registered. This gives you an idea of how the efficiency of the methods will vary with the conditions. In my C-implementation the plot is 'slow' because I have to go through a gotoxy() and a printf(). That means that selectsort is a clear winner. But if the comparison is slow and the plot is fast, it will be a loser. That is demonstrated in the Pascal version which works directly on the screen memory.

  1. Bubblesort is generally the slowest when it works on randomly sorted data, but it is the fastest if the data are nearly sorted.
  2. Quicksort is compact in the code and normally runs very fast, but it has a slow worst case.
  3. Mergesort does not have this disadvantage. Its runtime is the same no matter how the data you feed, it are sorted. And it is almost as fast as Quicksort.

Notes on sort types

Stable sort

A stable sort is one that keeps the original sequence of elements with identical keys. If you for example first sort a set of names on last name and afterwards on first name, you will need a stable sort for the second operation. Otherwise the first sort order is destroyed. Bubblesort, Insertsort, Radixsort and Mergesort are stable methods.

In-place sort

An in-place sort is one that works directly on the data supplied. All my examples are in-place except Radixsort and Heapsort. With Radixsort it is obvious because nothing happens until the set is suddenly sorted. Heapsort seems to work on the data set, but is uses extra memory in the background.

Tecnical notes

The TurboPascal version was first released in sep. 1995.
That version was compiled using the Borland TurboPascal 5 system.

This package is released in oct, 2017.
The C-version was compiled using the Borland C++-compiler 5.5.1
Both programs and all code are Freeware.

Bertel Lund Hansen - Kolt, Denmark

You can write to me. This address is not a permanent one, but this link will always be updated.