Mironchuk T. S., Sokolova N. O., Osadcha O. V.

Oles Honchar Dnipropetrovsk National University


Today there is a wide variety of problems, attached to processing and searching some information, which are solved faster, easier and more effectively, if data saves in computer memory as sequences. Perhaps, there is no one other task, which has given birth to so multitude of different ways of solving the same problem, as sorting. Is there any “universal”, the best algorithm? No, there is not. Though, if you have an approximate description of input data, you can match the optimal method.

The methods of sorting are appreciated by the following criteria:

1. Time of sorting – it is main parameter, that characterize the speed of algorithm.

2. Memory. Some algorithms require additional memory for temporary storage of data.

3. Stability – stable sorting does not change the relative position of equal elements. This feature can be very useful if they are made up of several fields.

4. Natural behavior – the method effectiveness in processing already sorted, or partially sorted data. The algorithm works naturally and better, if input sequence supports this feature.

Another important property of the algorithm is its scope. Here, two basic positions:

· internal sorting works with the data in RAM;

· external sorting arranges the information located on external storage. It imposes some additional restrictions on the algorithm:

-  Access to the storage is carried out sequentially: at any time it can be read or written only one element that stays after the current;

-  Data capacity does not allow elements to stay in RAM

Furthermore, access to the data on the storage is much slower than memory operations.

This class of algorithms is divided into two main sub-classes:

– Internal sorting operates with arrays, small enough to fit entirely in RAM. Data is usually sorted right away without any additional cost.

– External sorting operates with storage devices with high data capacity, but access is sequential (e.g. file sorting), it means that at the moment we 'see' only one element and the time required for rewind is unnecessarily large compared to memory. For this reason there are special methods of sorting that use extra disk space.

Basic methods of sorting linear data structures include:

· selection sort,

· bubble sort,

· insertion sort,

· bucket sort,

· Shell sort.

 Here are the most effective and most commonly used in practice methods among all ways of sorting.

· Quicksort, was designed by the English informatic Charles Hoare at MSU in 1960, one of the fastest in practice internal sorting algorithms general purpose, simple in implementation;

· Heapsort, was proposed by J. Williams in 1964, the algorithm is stable and works effectively for sufficiently large size of data;

· Merge sort, was invented by John von Neumann in 1945, this sorting method is a good example of the principle of "divide and rule".

Certainly, it is obviously to use very fast sorting algorithm. Simple sorting algorithms do not provide the desired performance of the program. However, developers always have to remember that every fast sorting algorithm may contain some drawbacks along with their advantages. So, young professionals of computer science have to understand that all variety of modern sorting methods allows programmer not to get hung up on only one and to choose the most optimal, related to his problem.