Lecture
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.
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
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.
Comments
To leave a comment
Structures and data processing algorithms.
Terms: Structures and data processing algorithms.