§ 18. Сартаванне аднамернага масіву

Практыкаванні

    

1. Дадзены лінейны масіў (вектар) з цэлых лікаў. Напісаць праграму сартавання масіву. Даныя згенерыраваць выпадковым чынам.

    1. Так, каб усе кратныя тром стаялі ў пачатку масіву, а не кратныя ў канцы.
    2. У парадку ўзрастання сумы лічбаў ліку.
    3. У парядку спадання колькасці дзельнікаў ліку.

2. Дадзены лінейны масіў (вектар) са слоў. Напісаць праграму сартавання масіву. Даныя чытаць з файла.

    1. Па колькасці літар у слове, у парадку ўзрастання.
    2. Па колькасці зычных літар у слове, у парадку спадання.
    3. Па колькасці розных літар у слове, у парадку ўзрастання.

3. Дадзены лінейны масіў (вектар) са структур. Напісаць праграму сартавання масіву. Даныя чытаць з файла. Можна выкарыстоўваць файлы, створаныя для практыкавання 6 пасля § 17.

1. У файле захоўваюцца: назва краіны, сталіца, плошча (тыс. км2) і колькасць насельніцтва (млн чал.).

Беларусь    Мінск         208       9.41

Расія       Масква        17075     143.3

ЗША         Вашынгтон     9373      310.2

Канада      Атава         9985      34.2

Францыя     Парыж         547       65.4

І г.д.

Адсартаваць даныя ў парадку ўзрастання плошчы.

2. У файле захоўваюцца: назва вытворцы пральнай машыны, яе мадэль, магутнасць і максімальная загрузка бялізны (кг).

Samsung      WW65K52E69S       2400      6.5

Bosch        WLT24440OE        2300      7

Haier        HW70-BP12758S     1900      7

LG           F12M7NDS0         1700      6

И т.д.

Адсартаваць даныя ў алфавітным парадку па назве вытворцы.

3. У файле захоўваюцца: назва возера, вобласць, у якой яно размешчана, яго аб’ем (млн м3), плошча (км2), максімальная глыбіня (м) і празрыстасць (м).

Нарач     Мінская       710      79.6     24.8     7.4

Снуды     Віцебская     107      22       16.5     6.6

Рычы      Віцебская     131.5    12.9     51.9     5.5

Свіцязь   Гродзенская   7.76     25.2     15       5.2

І г.д.

Адсартаваць даныя ў парадку спадання празрыстасці.

4*. Правесці даследаванне метадаў сартавання (выбарам, абменам і ўстаўкамі). Падрыхтаваць справаздачу ў электронных табліцах (можна выкарыстоўваць сумесны доступ да табліцы). Праграмы для кожнага сартавання скампіляваць у рэжыме release. Запускаць адкампіляваныя праграмы з аперацыйнай сістэмы, выкарыстоўваючы файлавы менеджар.

Для вымярэння часу можна выкарыстоўваць  int t1 = clock(); з бібліятэкі  ctime, (выдае час у мілісекундах). Час замяраць да пачатку работы алгарытму і пасля заканчэння работы алгарытму (розніца — час работы алгарытму).

Для выканання работы кіравацца наступным планам (для кожнага алгарытму):

    1. Згенерыраваць тэкставы файл з 20 000 цэлых лікаў (дыяпазон лікаў: –10000..10000).
    2. Змераць і запісаць час работы праграм для атрыманага файла.
    3. Згенерыраваць тэкставы файл з 20 000 цэлых лікаў (дыяпазон лікаў: –100..100).
    4. Змераць і запісаць час работы праграм.
    5. Павялічыць колькасць элементаў у пунктах 1 і 3 у два разы (да 40 000). Як зменіцца час выканання праграмы?
    6. Пункты 1—5 выканаць 10 разоў.
    7. Адсартаваць у адваротным парадку ўжо адсартаваны масіў для:

7.1. 20000цэлых лікаў (дыяпазон лікаў –10000..10000). 
7.2.  20000 цэлых лікаў (дыяпазон лікаў –100..100);
7.3. 40000 цэлых лікаў (дыяпазон лікаў –10000..10000;
7.4. 40000 цэлых лікаў (дыяпазон лікаў –100..100).

8. Знайсці сярэдняе значэнне часу па ўсіх відах сартаванняў (ад сумы адняць мінімальны, максімальны і падзяліць на 8).
9. Вызначыць мінімальную колькасць элементаў, пры якіх кожная праграма будзе працаваць больш за 30 секунд.

5. Вызначыць час работы алгарытму хуткага сартавання для тых жа файлаў, якія выкарыстоўваліся ў практыкаванні 4. Зрабіць вывады.