Laboratory work number 8. "SORTING BY DIRECT EXCHANGE"

Objective: to investigate and study the methods of sorting using direct exchange.


The task of the work: to master the skills of writing programs for sorting using direct exchange 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

Bubble Sort

Idea: (N-1) once the array is traversed from bottom to top (from top to bottom), the elements are compared in pairs, if the lower element is less than the upper one, the elements are rearranged.

Example: array - 4, 3, 7, 2, 1, 6.





You can improve the "bubble" method, if you pass the array of elements and up and down simultaneously.

Number of comparisons:



Number of movements:




An example of calculating the "bubble" method





The example shows an array of five elements, which means that the array is traversed from bottom to top (top to bottom) 5-1 = 4 times. It is also clear from the example that the “empty” algorithm processes the array starting from the third step of the internal loop, and the 4th step can no longer be performed.

The advantages of this method:

1) The easiest algorithm

2) Easy to implement

3) No need for additional variables

Disadvantages:

1) Long processes large arrays

2) In any case, the number of passes does not decrease.


Quiksort - quick sort method

Idea : This method is based on the method of splitting keys in relation to the selected one.

Example:





After the first pass, the selected item falls into place.


Improved bubble method.

1) If you pass an array not only from the top down, but also from the bottom up at the same time, then not only the “light” elements will “float”, but also the “heavy” “sink”.

2. 
   To cancel an “in vain” pass of an array, you need to insert into the external loop a check on the array sortedness.

Algorithm

Bubble Method Algorithm

(Pseudocode)

for i = 2 to n

for j = n to i step -1

if A (j-1)> A (j) then

x = A (j-1)

A (j-1) = A (j)

A (j) = x

end if

next j

next i

Quiksort Method Algorithm

(Pseudocode)

Sub Sort (L, R)

i = l

j = r

x = A ((l + r) div 2)

while A (i) <x do

i = i + 1

end while

while A (j)> x do

j = j-1

end while

if i <= j then

Y = A (i)

A (i) = A (j)

A (j) = Y

while i> j do

if l
sort (l, j)

end if

if i
sort (i, r)

end if

return

sub quiksort

sort (1, n)

return


The number of permutations and comparisons: (n * log (n)).

Tasks

Options:

1. Create a program for displaying the largest (smallest) element of array A.

2. Create a program to sort the array A in descending order of the values ​​of its elements.


3. In array A there are elements. Create a program that will form an array B, in which the elements of array B are arranged in descending order.


4. An ordered array A is given - numbers arranged in ascending order, and the number a to be inserted into array A, so that the ordering of the array is preserved.


5. Create a program for the rapid restructuring of the array A, in which the elements are arranged in ascending order, so that after the restructuring, these same elements are located in descending order.


6. Given array A, containing both negative and positive numbers. Create a program to eliminate from it all negative numbers, and the remaining positive in the order of increasing.


7. Create a program that will take one number after another from array A and form array B from them, arranging the numbers in ascending order.


8. A list of authors is given in the form of an array A. Compile a program for forming the index of authors in alphabetical order and display it on the screen.


9. There are n telephone exchange subscribers. Create a program in which the list is formed by the form: phone number, last name (numbers are in ascending order).


10. There are n words of various lengths, all of them are listed in array A. Create a program for ordering words by increasing their lengths.


11. Create a program for sorting array A in ascending and descending order of the modules of its elements.


12. In a sorted array A between each neighboring pair of elements, insert a number greater than the left and less than the right element in the array and display the resulting array on the screen.