About Site Map Submit Contact Us Log in | Create an account
Create an account Log In
Average Rating
User Rating:
Visitors Rating:
My rating:

Write review
  • License: Freeware
  • Last update: 6 years ago
  • Total downloads: 121
  • Price: Free |
  • Operating system: Linux, Mac OS X, Win All, BSD, Solaris
  • Publisher: Luigi Giaccari (28 other programs)
See full specifications

scripts default iconTHE FASTEST WAY TO SORT N NUMBERS: sortN library (Scripts) Publisher's description

Last week I wrote a post about the fastest way to sort 3 numbers, this week I show you a tricky way to optimize the sort of N numbers.

Have you ever thought about the fastest way to sort N numbers?

Last week I wrote a post about the fastest way to sort 3 numbers, this week I show you a tricky way to optimize the sort of N numbers.

The problem of sorting an array of numbers is probably the most studied in computer science. The efficiency of a sort algorithm depends essentially on the number of comparisons and swaps it needs to reach the solution. This post contains an optimized sort algorithm for small buckets (to my knowledge the fastest).

Currently most of sorting algorithms uses quick sort for large buckets and insertion sort for smaller ones. Both these algorithms uses an optimized way to swaps and compare numbers. The sortN library is a further optimization of this operations. It does first all the needed comparisons and then, only in the end, it swaps values to reach the sorted solution only in the end. It is in practice an enhanced Insertion sort algorithm.
The sortN library

The library is written in C++, but it can be written in any code, and supports arrays up to 7 elements. It can be applied , in theory, to array of any size but we will see this can not be realized in practice, only small arrays can be sorted.

The sortN libary can be considered enhanced insertion sort algorithm.

It contains a list of optimized function to sort 3,4,5,6,7 values. Each function is optimized to sort an N number of values.

Here is the approach to the solution:

N numbers can be disposed in Nc combinations where Nc is N!.

We may think to write a recursive code that reach the sorted solution in the way algorithms for permutations does.

The permutations represents all the possible solutions, depending on the value of each comparison (between 2 values of the array) a permutation is chosen or refused.

This allows, depending on the results of the comparisons, to build a decisionary tree that unequivocally leads to the permutation that represents the solution. Once we know the solution we can optimize swaps to reach it.

Notice that no swaps must be done done before we know the exact solution. This can be considered an enhanced insertion sort algorithm.

The number of comparisons possible are great even for a relative small array, we can not think about writing by hand the code, we need some function to do job for us. That’s what the sort library does, it prints the enhanced insertion sort algorithm.

There is a small disadvantage: the problem has size N!. It becomes huge for relative small buckets like 8 numbers. The sort8 function requires a 10MB file, I waited10 minutes for the compiler to build it, but no success, then I give up and decide to use the library till sort7 function.
The sortN function

You probably got confused, so here it is the code that I hope will clarify the concept.

The sort N function is a MATLAB script that prints the enhanced insertionsort algorithm for N values.

It recursively finds all the solutions and it prints optimized swaps.

System Requirements:

MATLAB 7.8 (R2009a)
Program Release Status: New Release
Program Install Support: Install and Uninstall

THE FASTEST WAY TO SORT N NUMBERS: sortN library (Scripts) Tags:

Click on a tag to find related softwares

Is THE FASTEST WAY TO SORT N NUMBERS: sortN library (Scripts) your software?

Manage your software

Most Popular

scripts default icon ASK, OOK, FSK, BPSK, QPSK, 8PSK modulation 1.1
ASK, OOK, FSK, BPSK, QPSK, 8PSK modulation contain several functions for digital modulation simulation
scripts default icon Simulink Communication Labs 1.1
Simulink Communication Labs allows you to learn communication systems in greater depth.
scripts default icon M-QAM modulation and demodulation 1.1
M-QAM modulation and demodulation is the QAM modulation and demodulation tech.
scripts default icon LZW Compression/Decompression 1.1
LZW Compression/Decompression - Updated LZW compressor and decompressor with reasonable performance
scripts default icon InSPIRE utility to plot a 2D displacement field (Scripts) 1.0
This program plots the deformation field (displace vectors) contained in vector.txt.