Bertel Lund Hansens hjemmeside

Sorting algorithms

Introduction

I have made two nearly identical programs with different sorting methods because I found it interesting. The programs show a screen with random characters which can be sorted by thirteen 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.

One version is a C-program, the other is a Python script. Both programs and code are Freeware. Here are download links to two zip-packages:

C-version, code and exe-file

Python-version

The methods are:

  1. Odd-EvenSort
  2. InsertSort
  3. BubbleSort
  4. CocktailSort
  5. ShellSort (Bubble)
  6. HeapSort
  7. ShellSort (Insert)
  8. MergeSort
  9. QuickSort
  10. RadixSort
  11. SelectSort
  12. CycleSort
  13. CountSort

P.S. I have later found out that a (relatively) new method is the professional choice (Google, Python). It is called TimSort. It's based on Mergesort and Insertsort, and it is stable. I haven't implemented it yet.

Practical information

The C version

The C source code is available, but I have compiled a Windows version that should run on any Windows. It has been tested on Windows 7, 8 and 10. If you want to run it under other OS'es, you must compile it yourself.

The C version requires the conio.h which 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 is available, the program can 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.

The Python version

The Python version requires the curses module. It can read the window dimensions but unfortunately only once, and this is done at startup. Therefore it starts with a pause where you can change the window and then press a key.

I haven't tried the program in a Power Shell box.

Inspired by the C-version I have made it possible to reduce the number of lines dynamically though the same result could be achieved when resizing the window at start.

General info

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

The C source code is in the packet. The routines are slightly 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.

I wrote the first version of the program in 1995 using Turbo Pascal. The C and Python version came later, and I made the last changes in June 2020.

From the menu screen it is possible to choose a presort condition - ascending or decending. This has a huge influence on the running speed.

You may also choose to delay the display so it becomes easier to follow the sorting moves. With no delay it isn't possible to pause or quit the sorting. Otherwise [P] and [Home] respectively will take effect.

Notes on speed

Apart from the measuring of time, the number of plots and 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(). In contrast the comparison is fast.

In Python it is the other way around, and this makes it interesting to compare the two versions. Selectsort is very much affected by this difference and moves from one of the fastest routines in C to a more mediocre one in Python. The same is true of Cyclesort which by the way is interesting because is is the sorting routine that requires the fewest plots - usually even less than the number of bytes. This makes it the primary choice with media that are worn down by frequent writes.

  1. Insertsort, Bubblesort and DoubleBubblesort (also called Cocktailsort) are generally among the slowest when they work on randomly sorted data, but they are among 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 making it useless for critical routines.
  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.
  4. Odd-Even-sort is included just for fun. It compares and writes a horrible lot of times and is completely useless.

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 Heapsort, Mergesort and Radixsort. With Radixsort it is obvious because nothing happens until the set is sorted in three runs. Mergesort and Heapsort seem to work on the data set, but they use extra memory in the background.

Tecnical notes

A TurboPascal version was first released in September 1995.
That version was compiled using the Borland TurboPascal 5 system.

The C-version was compiled using the Borland C++-compiler 5.5.1

The Python version is written for Python 3.

This package is released in July 2020.
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.