You get a bonus - 1 coin for daily activity. Now you have 1 coin

Methodical guide to course work data structures and algorithms

Lecture





Introduction


Course work is performed by students of the specialty 22.04 in the fourth semester.

The Aim of the course work is to consolidate the foundations and deepening of knowledge in the field of structures and algorithms for data processing in computers.

The subject of coursework assignments given in these guidelines can be supplemented, expanded, linked to the solution of actual research tasks performed at the department.


1 Coursework Requirements




1.1 The topic of the course work is given to each student individually. In the collective work in which two or more students take part, the volume and nature of the work of each student are clearly defined. The task formulates the task, the method of its solution.


1.2 Coursework consists of an explanatory note, to which is attached a diskette with debugged programs (an explanatory note can be made in the form of a text file in Microsoft Word format).


1.3 The explanatory note should include:

- title page (Appendix B);

- task for course design (Appendix A);

- abstract (PP, the number of tables, figures, diagrams, application programs, a brief description and results of work);

- content:

a) formulation of the research problem;

b) a brief theory on the topic of the course work;

c) software implementation of the investigated algorithms;

d) the program with which the study was conducted;

e) the results of the study:

f) conclusions;

- list of references;

- signature, date.


1.4 The explanatory note should be issued on A4 sheets that have margins. All sheets should be stitched and numbered.


1.5 The study of algorithms for operations on data structures and methods of sorting and searching should be carried out with the following fixed quantities of elements in the structures: 10, 100, 1000, 10000.


1.6 Additional terms of coursework are issued by the supervisor.

2. Approximate list of coursework



1) Study Stacks.

2) Queue research.

3) The study of ring structures.

4) The study of semi-static structures.

5) The study of linear single and doubly linked lists.

6) Examination of binary search trees.

7) Research on inclusion sorting methods.

8) Exploring sorting methods of choice.

9) Research on exchange sorting methods.

10) Exploring sorting methods using trees.

11) Research on improved sorting methods.

12) The study of linear, index and binary searches.

13) The study of search optimization methods.

14) Research the search tasks on the tree.

3. Example of coursework

3.1 Problem Statement



Carry out a study of direct methods of sorting:

- direct selection method;

- direct insertion method;

- direct exchange method.

The study carried out using arrays of ordered and unordered numbers of 10,100,1000 and 10,000 items.

3.2 Brief Theory



When processing data, it is important to know both the information field of the data and its location in the machine.

There are internal and external sorting:

  • internal sorting - sorting in RAM;

  • external sorting - sorting in external memory.

Sorting is the arrangement of data in memory in a regular form by their keys. Regularity is considered as an increase (decrease) of the key value from the beginning to the end in the array.

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 order as in the source file. This is a stable sort .

The sorting efficiency can be viewed from several criteria:

  • time spent on sorting;

  • the amount of RAM required for sorting;

  • time spent by a programmer to write a program.

Select the first criterion. You can count the number of comparisons when performing sorting or the number of movements.

Let H = 0.01n 2 + 10n be the number of comparisons. 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 will be equal to n 2 , for large n, the order of comparison will be n.

The order of comparison when sorting lies within

from 0 (n log n) to 0 (n 2 ); 0 (n) is an ideal case.

The following sorting methods are distinguished:

  • strict (direct) methods;

  • improved methods.

Strict methods:

1) direct inclusion method;

2) direct selection method;

3) direct exchange method.

The number of movements in these three methods is about the same.


3.2.1 Sort by direct inclusion


Informal algorithm

for i = 2 to n

x = a (i)

find a place among a (1) ... a (i) to include x

next i

Pascal program:

for i: = 2 to n do

begin

x: = a [i];

a [0] = x;

for j: = i - 1 downto 1 do

if x <a [j]

then a [j + 1]: = a [j]

else a [j + 1]: = x;

end;


Algorithm efficiency:

The number of comparisons in the worst case will be equal to
(n - 1) (n - 1).


3.2.2 Sorting by direct selection


Consider the entire array row and choose an element smaller or larger than element a (i), determine its place in the array - k, and then swap element a (i) and element a (k).

Pascal program:

for i: = 1 to n - 1 do

begin

x: = a [i];

k: = i;

for j: = i + 1 to n do

if x> a [j] then

begin

k: = j;

x: = a [k];

end;

a [k]: = a [i];

a [i]: = x;

end;

Algorithm efficiency:

The number of comparisons M =   Methodical guide to course work data structures and algorithms .

The number of displacements C min = 3 (n - 1), C max = 3 (n - 1)   Methodical guide to course work data structures and algorithms
(order n 2 ).

In the worst case, sorting by direct choice gives the order of n 2 , as for the number of comparisons, and for the number of displacements.


3.2.3 Sort using direct exchange (bubble)

Idea: n - 1 times pass an array from the bottom up. In this case, the keys are compared in pairs. If the lower key in a pair is less than the upper key, then they are swapped.

Pascal program:

for i: = 2 to n do

for j: = n downto i do

if a [j - 1]> a [j] then

begin

x: = a [j - 1];

a [j - 1]: = a [j];

a [j]: = x;

end;


In our case, it turned out one pass “idle”. In order not to rearrange the elements again, you can enter a flag.

The improvement of the bubble method is shaker sorting, where after each pass they change direction within the cycle.


Algorithm efficiency:

number of comparisons M =   Methodical guide to course work data structures and algorithms ,

number of movements C max = 3   Methodical guide to course work data structures and algorithms .

3.3 Research Method



This course work is to study the direct methods of sorting:

- direct selection method;

- direct inclusion method;

- direct exchange method.

The study is as follows:

they take three arrays with the same number of elements, but one of them is ordered in ascending order, the second is in descending order, and the third is random. The data of the arrays is sorted and the number of elements displacements is compared when the first, second and third arrays are sorted, and the number of comparisons is compared.

The above method is applied to arrays consisting of 10, 100, 1000 and 10000 ordered and unordered elements for all sorting methods.

3.4 study results





Sorting 10 items:


- ordered by ascending

method

direct selection

direct insertion

direct exchange

comparisons

45

45

45

displacements

eleven

33

33


- unordered (random)

method

direct selection

direct insertion

direct exchange

comparisons

45

45

45

displacements

27

27

27


- ordered by descending

method

direct selection

direct insertion

direct exchange

comparisons

45

45

45

displacements

0

0

0


Sorting 100 items:


- ordered by ascending

method

direct selection

direct insertion

direct exchange

comparisons

4950

4950

4950

displacements

2643

4862

4862


- unordered (random)

method

direct selection

direct insertion

direct exchange

comparisons

4950

4950

4950

displacements

2558

2558

2558


- ordered by descending

method

direct selection

direct insertion

direct exchange

comparisons

4950

4950

4950

displacements

0

0

0


Sorting 1000 items:


- ordered by ascending

method

direct selection

direct insertion

direct exchange

comparisons

499,500

499,500

499,500

displacements

241901

498442

498442


- unordered (random)

method

direct selection

direct insertion

direct exchange

comparisons

499,500

499,500

499,500

displacements

244009

250366

250366


- ordered by descending

method

direct selection

direct insertion

direct exchange

comparisons

499,500

499,500

499,500

displacements

0

0

0


Sorting 10,000 items:


- ordered by ascending

method

direct selection

direct insertion

direct exchange

comparisons

49995000

49995000

49995000

displacements

25003189

49984768

49984768


- unordered (random)

method

direct selection

direct insertion

direct exchange

comparisons

49995000

49995000

49995000

displacements

18392665

24986578

24986578


- ordered by descending

method

direct selection

direct bet

direct exchange

comparisons

49995000

49995000

49995000

displacements

0

0

0



3.5 Test Case



The task:

A list containing the names of the students and their corresponding rating points is given. It is necessary to sort this list by descending rating points.

Sort by direct inclusion:

Before sorting

After sorting

Arkady

nineteen

Arthur

20

Before sorting

After sorting

Murat

17

Arkady

nineteen

Ruslan

9

Alexander

18

Arthur

20

Vladimir

18

Eugene

7

Murat

17

Michael

15

Kazbek

sixteen

Alexander

18

Michael

15

Vitali

14

Boris

15

Sidor

eight

Denis

14

Vladimir

18

Vitali

14

Alexey

6

Vasiliy

13

Kazbek

sixteen

Peter

ten

Marat

five

Ruslan

9

Boris

15

Ivan

eight

Gennady

2

Sidor

eight

Denis

14

Eugene

7

Vasiliy

13

Alexey

6

Sidor

3

Marat

five

Peter

ten

Sidor

3

Ivan

eight

Gennady

2



3.6 Conclusions



According to the results of the research, it can be argued that the best of the direct sorting methods is the direct selection method, since it gives the least amount of comparisons and movements, regardless of the number of elements being sorted and their relative position in the array.

3.7 Description of the procedures used in the program





UPOR

the procedure generates an ascending array of numbers

NOTUPOR

the procedure generates an unordered (random) array of numbers

PR_CHOOSE

procedure performs sorting by direct selection

PR_INS

the procedure performs the direct insert sorting

PR_OBM

procedure performs the direct exchange sorting

MAKE

the procedure carries out research of direct methods of sorting

EXAMPLE

the procedure performs a test case (live sorting)

Text of the program


{$ M 65000.65000.65000}

{Memory allocation is carried out in order to make it possible to study an array containing 10,000 elements.

************************************************** *********

This program is a course work on discipline.

'Structures and Data Processing Algorithms'

on the topic 'Direct sorting methods'

In work methods are investigated:

- direct selection;

- direct exchange;

- direct insertion.

For research, arrays of 10,100,100,10000 elements are used.

************************************************** ********}

{using modules for displaying}

uses crt, crtext, dcrt; ******************************************* ********}

{** procedure that generates an ordered array of numbers **}

{************************************************* ********}

procedure upor (a: array of integer; var a1: array of integer);

var

{i - counter in cycles}

i: integer;

begin

{the first element takes the value 1}

a [0]: = 1;

for i: = 1 to high (a) do

begin

{each subsequent element takes the value

equal to the value of the previous element + random number}

a [i]: = a [i-1] + random (2);

end;

for i: = 0 to high (a) do

a1 [i]: = a [i];

end;

{************************************************* ********}

{** procedure generating an unordered (random) array of numbers **}

{************************************************* ********}

procedure notupor (a: array of integer; var a1: array of integer);

var

{i - counter in cycles}

i: integer;

begin

for i: = 0 to high (a) do

begin {array element takes a random value from the range 0 <= a [i] <9999}

a [i]: = random (9999);

end;

for i: = 0 to high (a) do

a1 [i]: = a [i];

end;

{************************************************* ********}

{***** procedure that performs sorting by direct selection ***}

{************************************************* ********}

procedure pr_choose (a: array of integer; var a1: array of integer; var k, k1: longint);

var

{i, j - counters in cycles}

i, j: integer;

{x - variable for exchanging between a [i] and a [j]}

x: integer;

begin

{k1 - variable to count the number of comparisons

k - variable to count the number of displacements}

k: = 0; k1: = 0;

{high (a) - a function that returns the number of the last element of the array}

for i: = 0 to high (a) - 1 do

begin

for j: = i + 1 to high (a) do

begin

k1: = k1 + 1;

if a [i] <a [j] then

begin

k: = k + 1;

{interchanging the ith with the jth element using the variable x}

x: = a [i];

a [i]: = a [j];

a [j]: = x;

end;

end;

end;

for i: = 0 to high (a) do

a1 [i]: = a [i];

end;

{************************************************* *********

***** Direct Sorting Procedure *

*************** exchange (bubble method) *********************

************************************************** ********}

procedure pr_obm (a: array of integer; var a1: array of integer; var k, k1: longint);

var

{i, j - counters in cycles}

i, j: integer;

{x - variable to exchange between a [j-1] and a [j]}

x: integer;

begin

{k1 - variable to count the number of comparisons

k - variable to count the number of displacements}

k: = 0; k1: = 0;

for i: = 1 to high (a) do

begin

for j: = high (a) downto i do

begin

k1: = k1 + 1;

if a [j - 1] <a [j] then

begin

k: = k + 1;

{exchange the contents of the elements of the array a [j-1] and a [j]

using the variable x}

x: = a [j - 1];

a [j - 1]: = a [j];

a [j]: = x;

end;

end;

end;

for i: = 1 to high (a) do

a1 [i]: = a [i];

end;

{************************************************* ********}

{*** procedure that performs the sorting method by direct inclusion **}

{************************************************* ********}

procedure pr_ins (a: array of integer; var a1: array of integer; var k, k1: longint);

var

{i, j - counters in cycles}

i, j: integer;

{x - variable for exchanging between a [i] and a [j]}

x: integer;

begin

{k1 - variable to count the number of comparisons

k - variable to count the number of displacements}

k: = 0; k1: = 0;

for i: = 1 to high (a) do

begin

x: = a [i];

for j: = i - 1 downto 0 do

begin

k1: = k1 + 1;

if x> a [j] then

begin

k: = k + 1;

{exchange the contents of the elements of the array a [j + 1] and a [j]

using the variable x}

a [j + 1]: = a [j];

a [j]: = x;

end;

end;

end;

for i: = 0 to high (a) do

a1 [i]: = a [i];

end;

{************************************************* *********

procedure that investigates sorting methods for

*********** a given array of numbers ***********************

************************************************** ********}

procedure make (x1, n: integer; a, a1: array of integer; k: byte);

var

{number of permutations}

kol_pr_ins, kol_pr_obm, kol_pr_choose: longint;

{number of comparisons}

kol_sr_ins, kol_sr_obm, kol_sr_choose: longint;

s: string;

begin

case k of

1: s: = 'sorted in ascending order';

2: s: = 'unordered (random)';

3: s: = 'ordered descending';

end;

{-------- direct inclusion method --------}

pr_ins (a, a1, kol_pr_ins, kol_sr_ins);

{-------- direct exchange method (bubble method) --------}

pr_obm (a, a1, kol_pr_obm, kol_sr_obm);

{--------- direct selection method ----------}

pr_choose (a, a1, kol_pr_choose, kol_sr_choose);

{** output research result **}

{output table header}

gotoxy (3, x1); textcolor (cyan); textbackground (1);

writeln ('For', high (a) +1, '', s, 'elements:');

gotoxy (3, x1 + 1); textcolor (lightgreen); textbackground (1);

writeln ('Methods: direct inclusion direct exchange direct selection');

{output of the data obtained during the study}

gotoxy (3, x1 + 2); textcolor (white); write ('overwrite');

gotoxy (17, wherey); write (kol_pr_ins);

gotoxy (37, wherey); write (kol_pr_obm);

gotoxy (58, wherey); writeln (kol_pr_choose);

gotoxy (3, x1 + 3); write ('compare.');

gotoxy (17, wherey); write (kol_sr_ins);

gotoxy (37, wherey); write (kol_sr_obm);

gotoxy (58, wherey); writeln (kol_sr_choose);

str (high (a) + 1, s); box (1,19,80,24,1,15, double, s + 'elements');

gotoxy (4,20); write ('Sort', s, 'items descending');

gotoxy (4,21); write ('Sorted', s, 'ordered (by ascending) elements');

gotoxy (4.22); write ('Sorted', s, 'unordered (random) elements');

textbackground (lightgray);

textcolor (red); gotoxy (3.25); write ('Esc - main menu');

end;

{*********************************************

Live Sorting Example

An array of entries is given containing:

-name of the student;

-kol points (rating).

You must sort the array by

a decrease in the number of points from the student.

**********************************************}

procedure example;

type

{rec is a record containing:

name - the name of the student;

num - number of points (rating).}

rec = record

name: string;

num: byte;

end;

var

{mas - array of rec records}

mas: array [1..20] of rec;

{counters in cycles}

i, j: integer;

x: rec;

{variables for counting the number of comparisons and movements

during sorting}

k_sr, k_p: integer;

key: char;

begin

{variables for counting the number of comparisons and movements

during sorting}

k_sr: = 0; k_p: = 0;

randomize;

{This array containing the names of the students}

mas [1] .name: = 'Ivan'; mas [2] .name: = 'Peter'; mas [3] .name: = 'Sydor';;

mas [4] .name: = 'Basil'; mas [5] .name: = 'Denis'; mas [6] .name: = 'Gennady';;

mas [7] .name: = 'Boris'; mas [8] .name: = 'Marat'; mas [9] .name: = 'Kazbek';

mas [10] .name: = 'Aleksey'; mas [11] .name: = 'Vladimir'; mas [12] .name: = 'Sydor';;

mas [13] .name: = 'Vitaly'; mas [14] .name: = 'Alexander'; mas [15] .name: = 'Michael';

mas [16] .name: = 'Eugene'; mas [17] .name: = 'Arthur'; mas [18] .name: = 'Ruslan';;

mas [19] .name: = 'Murat'; mas [20] .name: = 'Arkady';

{setting the number of points for a student at random}

for i: = 1 to 20 do

mas [i] .num: = random (19) +1;

{conclusion of explanations}

getshadow;

textbackground (lightgray);

textcolor (red); gotoxy (15,1); write ('Example of sorting in descending order by direct inclusion');

textbackground (lightgray);

textcolor (red); gotoxy (3.25); write ('Esc - main menu');

textcolor (red); gotoxy (65.25); write ('F1 - task');

box (58,0,80,25,1,15, double, 'Statistics');

textcolor (lightmagenta);

gotoxy (59.3); write ('Sort method');

gotoxy (61,4); write ('live.');

textcolor (white); gotoxy (59.5); write ('---------------------');

box (31,0,57,25,1,15, double, 'After sorting');

textcolor (lightmagenta); gotoxy (32.3); write ('n name score');

box (1,0,30,25,1,15, double, 'Before sorting');

textcolor (lightmagenta); gotoxy (3.3); write ('n name score');

{output to the screen of the original array}

for i: = 1 to 20 do

begin

textcolor (lightcyan); gotoxy (3, i + 3); write (i);

textcolor (yellow); gotoxy (7, i + 3); write (mas [i] .name);

textcolor (lightred); gotoxy (25, i + 3); writeln (mas [i] .num);

end;

{sort by descending number of points}

for i: = 2 to 20 do

begin

x: = mas [i];

for j: = i - 1 downto 1 do

begin

{k_sr - number of comparisons}

k_sr: = k_sr + 1;

if x.num> mas [j] .num then

begin

{k_p - the number of displacements}

k_p: = k_p + 1;

{sharing the contents of the elements of the mas [j + 1] and mas [j] array

using the variable x}

mas [j + 1]: = mas [j];

mas [j]: = x;

end;

end;

end;


{display of sorted array}

for i: = 1 to 20 do

begin

textcolor (lightcyan); gotoxy (33, i + 3); write (i);

textcolor (yellow); gotoxy (37, i + 3); write (mas [i] .name);

textcolor (lightred); gotoxy (52, i + 3); writeln (mas [i] .num);

end;

{display the number of comparisons and permutations

in an array, implemented during sorting}

textcolor (lightgreen); gotoxy (61.6); write ('Comparisons:');

textcolor (lightgray); gotoxy (75.6); write (k_sr);

textcolor (lightgreen); gotoxy (61.8); write ('Permutations:');

textcolor (lightgray); gotoxy (75.8); write (k_p);

repeat

key: = ''; if keypressed then key: = readkey;

case key of

{# 59 - F1 key code}

# 59: begin

{output of task window for test case}

{putshadow + box - output window with shadow}

putshadow (15,7,65,15); box (15,7,65,15, lightgray, 0, double, 'Task');

textcolor (red);

gotoxy (21.9); write ('There is a list containing the names of the students');

gotoxy (21,10); write ('and their rating points. Necessary from-');

gotoxy (21.11); write ('sort the list in descending order');

gotoxy (21,12); write ('rating points.');

textcolor (yellow); gotoxy (50,15); write ('Enter - cancel');

end;

{# 13 - Enter key code}

# 13: getshadow;

end;

{# 27 - Esc key code}

until key = # 27;

end;

{************************************************* *********

************************ Main program ***************

************************************************** ********}

const

{array of strings - main menu items}

menu: array [1..7] of string = ('Example sorting', 'Research (10 items)',

'Research (100 el-com)',

'Research (1000 email)',

'Research (10,000 email)',

' About the program '

,' Output ');

var

{arrays of numbers used for research}

a, a1: array [0..9] of integer; {10 - numbers}

b, b1: array [0..99] of integer; {100 - numbers}

c, c1: array [0..999] of integer; {1000 - numbers}

d, d1: array [0..9999] of integer; {10,000 - numbers}

f: byte; {indicator of which array

enters the procedure for

descending:

1 - unordered (case

tea);

2 - ordered by opportunity

sprawl;

3 - ordered by decrease

to

k: char;

item: byte;

begin

clrscr; cursoroff; {cursor blanking}

repeat

textbackground (0); clrscr;

{fill - a procedure that fills a specified area of ​​the screen with specified characters of a given color}

fill (lightgray, 1,1,2,80,25, '');

{menuv - procedure that displays the vertical menu}

menuv (25,10, menu, lightgray, black, red, lightgreen, yellow, 'Sort', item, double);

{item - a variable containing the number of the selected menu item}

case item of

1: example;

2: begin

{getshadow - procedure that removes the shadow from the menu}

getshadow;

{** 10 elements in ascending order are examined **}

{box - procedure that displays the window}

box (1,0,80,18,1,15, double, '10 elements');

{call upor, generating an ascending order

array of numbers}

upor (a, a);

{call to the make procedure that investigates sorting methods}

make (3,10, a, a1,1);

{** 10 unordered (random) elements are investigated **}

{call the notupor procedure that generates an unordered (random) array of numbers}

notupor (a, a);

{call to the make procedure that investigates sorting methods}

make (8.10, a, a1,2);

{** 10 descending ordered elements descending **}

{call to the make procedure that investigates sorting methods}

make (13,10, a1, a1,3);

{waiting for Esc key press}

repeat

k: = readkey;

until k = # 27;

end;

3: begin

{getshadow - a procedure that removes the shadow from the menu}

getshadow;

{box - a procedure that displays a window}

box (1,0,80,18,1,15, double, '100 elements');

{100 ordered ascending elements are

examined } upor (b, b);

make (3,100, b, b1,1);

{100 unordered (random) elements are

investigated } notupor (b, b);

make (8,100, b, b1,2);

{100 ordered elements descending are examined}

make (13,100, b1, b1,3);

repeat k: = readkey; until k = # 27;

end;

4: begin

{getshadow - a procedure that removes the shadow from the menu}

getshadow;

box (1,0,80,18,1,15, double, '1000 elements');

{1000 ordered ascending elements are

examined } upor (c, c);

make (3,1000, c, c1,1);

{1000 unordered (random) elements are

investigated } notupor (c, c);

make (8,1000, c, c1,2);

{1000 ordered by descending elements are examined}

make (13,1000, c1, c, 3);

repeat

k: = readkey;

until k = # 27;

end;

5: begin

getshadow;

box (1,0.80,18,1,15, double, '10,000 items');

{10,000 elements in ascending order are examined}

upor (d, d);

make (3.10000, d, d1,1);

{10,000 unordered (random) elements are

investigated } notupor (d, d);

make (8,10000, d, d1,2);

{10,000 ordered elements descending are investigated}

make (13,10000, d1, d, 3);

repeat

k: = readkey;

until k = # 27;

end;

6: begin

{getshadow - a procedure that removes the shadow from the menu}

getshadow;

{enter the window with the topic of the course work}

box (10,5,70,15, lightgray, 0, double, 'About the program');

putshadow (10,5,70,15);

textcolor (brown);

gotoxy (12,7); write ('This program is a term paper on the discipline');

gotoxy (21,8); write ('"Algorithms and data processing structures"');

gotoxy (30,9); write ('Theme of the course work:');

gotoxy (18,10); write ('"Investigating direct sorting methods"');

gotoxy (17,11); write ('Course work was completed by students of group 95-OA-21');

textcolor (red); gotoxy (3.25); write ('Esc - main menu');

repeat

k: = readkey;

until k = # 27;

end;

end;

until item = 7;

end.

{********************* end of program ********************}

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Structures and data processing algorithms.

Terms: Structures and data processing algorithms.