Laboratory work number 6. "SORTING BY DIRECT INCLUSION METHOD"

Objective: to investigate and study the methods of sorting by inclusion.


The task of the work: to master the skills of writing programs for sorting by direct inclusion in the programming language PASCAL.


Operating procedure :

• 
  study the description of the laboratory work;

• 
  according to the task given by the teacher, to develop an algorithm for the program for solving the problem;

• 
  write a program in PASCAL;

• 
  debug the program;

• 
  to solve a task;

• 
  issue a report.

Brief theory

When processing data in a computer, it is important to know both the information field of the element and its placement in the memory of the machine. For these purposes sorting is used. So, sorting is the location of data in memory in a regular form by their keys. Regularity is considered as increasing the key value from the beginning to the end in the array.

There are the following types of sorts:

• 
  internal sorting is the sorting that takes place in the memory of the machine

• 
  external sorting - sorting in external memory.

If the sorted records occupy a large amount of memory, then their movement is expensive. In order to reduce them, the sorting is performed in the table of key addresses, the permutation of pointers is performed, i.e. the array itself does not move. This is a method to sort the address table.

When sorting can meet the same keys. In this case, when sorting, it is desirable to arrange after sorting the same keys in the same location as in the source file. This is a stable sort.

The sorting efficiency can be viewed from several criteria:

• 
  time spent on sorting

• 
  amount of RAM required for sorting

• 
  time spent by a programmer to write a program

Consider the second criterion in more detail: we can calculate the number of comparisons when performing sorting or the number of movements.

Suppose that the number of comparisons is determined by the formula:

C = 0.01n ² + 10n

If n <1000, then the second term is greater.

If n> 1000, then the first term is greater.

That is, for small n the order of comparison is equal, and for large n it is equal to n.

The following sorting methods are distinguished:

• 
  strict (direct) methods

• 
  improved methods

Consider the advantages of direct methods:

1. The programs of these methods are easy to understand, and they are short. Recall that the programs themselves also take up memory.

2. Direct methods are particularly convenient for explaining the characteristic features of the basic principles of most sorts.

3. Complicated methods require a small number of operations, but these operations are usually more complex themselves, and therefore for sufficiently small n the direct methods turn out to be faster, although for large n they, of course, should not be used.


Sorting methods "in the same place" can be divided according to their defining principles into 3 categories:

1. Sorting by means of inclusion (by insertion)

2. Sorting by selection (by selection)

3. Sorting using exchanges (by exchange)


Sort by direct inclusion


This method is widely used when playing cards. The elements (maps) are mentally divided into the already “ready” sequence a (1), ..., a (i-1) and the initial sequence. At each step, starting with i = 2 and increasing i each time by one, the i-th element is extracted from the initial sequence and transferred to the finished sequence, and it is inserted into the right place.

Algorithm

The direct-sorting algorithm is as follows:

for x: = 2 to n do

x: = a [i]

including x in the appropriate place among a [1] ... a [i]

end

In the real process of finding a suitable place is convenient, alternating comparison

it is compared with the next element a (j), and then either x is inserted into the free space, or a (j) is shifted (transmitted) to the right and the process “leaves” to the left. Please note that the screening process may end when one of the following two different conditions is met:

1. Found the element a (j) with a key smaller than the key y x.

2. Reached the left end of the finished sequence.


Procedure StraightInsertion

Var

i, j: index; x: item;

begin

for i: = 2 to n do

x: = a [i]; a [0]: = x; j: = 1;

while x <a [j-1] do = "" a [j-1]: = "a [j-1];" j: = "j-1;" end; <br = "">
a [j]: = x

end

end StraightInsertion

Tasks

There are several (N) machines in the repair shop. The following information is available about them: number, brand, name of the owner, date of last repair (day, month, year), day to which the car should be repaired (day, month, year).

Required (according to option):

1.Plan alphabetically the names of the owners and, accordingly, display information about their machines.

2. Based on the fact that the car, the repair completion date of which is earlier, should be repaired in the first place, remove the order of car repairs.

3. To output in descending order the number of all previous repairs of Zhiguli cars.

4. To output in descending order the numbers of those machines, the number of previous repairs of which is 2

5. Output ascending the date of the end of repair of all machines that have not previously been repaired.

6. Alphabetically reverse the owners of cars of the brand "Mercedes"

7. Alphabetically output the brand of cars that should be repaired before anyone else (the end date of the repair is less than 01/08/96).

8. Output ascending the number of Zhiguli cars.

9. Alphabetically print the names of the owners, whose cars have not been repaired since last year.

10. To withdraw the cars that need to be repaired by the next month by increasing the date of their last repair.

11. Write in alphabetical order in the reverse order the names of the owners, the number of previous repairs of machines which are more than three.

12. To output, in descending order, the number of Mercedes cars.