Розробка програмного забезпечення для сортування масивів різними способами

int *hoara(int *a,int n,bool amb)

{

return hoara_1(a,0,n-1,amb);

}

int *hoara_1(int *a,int m,int n,bool amb)

{

int c;

int i = m;

int j = n;

int x = a[(m+n)/2];

while (i <= j)

{

while (sravni(a[i],x,amb)) i++;

while (sravni(x,a[j],amb)) j--;

if (i <= j)

{

c = a[i];

a[i] = a[j];

a[j] = c;

i+=1;

j-=1;

}

}

if (j > m) a=hoara_1(a, m, j,amb);

if (i < n) a=hoara_1(a, i, n,amb);

return a;

}

Приклад:

60, 79, 82, 58, 39, 9, 54, 92, 44, 32

60, 79, 82, 58, 39, 9, 54, 92, 44, 32

9, 79, 82, 58, 39, 60, 54, 92, 44, 32

9, 79, 82, 58, 39, 60, 54, 92, 44, 32

9, 32, 82, 58, 39, 60, 54, 92, 44, 79

9, 32, 44, 58, 39, 60, 54, 92, 82, 79

9, 32, 44, 58, 39, 54, 60, 92, 82, 79

9, 32, 44, 58, 39, 92, 60, 54, 82, 79

9, 32, 44, 58, 39, 54, 60, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 44, 58, 60, 39, 54, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 39, 58, 54, 44, 60, 79, 82, 92

9, 32, 39, 58, 54, 44, 60, 79, 82, 92

9, 32, 39, 44, 54, 58, 60, 79, 82, 92

9, 32, 39, 44, 58, 54, 60, 79, 82, 92

9, 32, 39, 44, 54, 58, 60, 79, 82, 92

9, 32, 39, 44, 54, 58, 60, 79, 92, 82

9, 32, 39, 44, 54, 58, 60, 79, 82, 92

"Внутрішній цикл" швидкого сортування складається тільки зі збільшення покажчика і порівняння елементів масиву з фіксованим числом. Саме це і робить швидке сортування швидким. Складно придумати більш простий внутрішній цикл. Позитивні ефекти сторожових ключів також роблять тут свій вплив, оскільки приєднання ще однієї перевірки до внутрішнього циклу зробило би негативний вплив на продуктивність алгоритму.

Характеристики продуктивності швидкого сортування:

Найкраще,що могло б відбутися для алгоритму - це якби кожний з підфайлів ділився б на два рівних по величині підфайла. В результаті кількість порівнянь, яке робить швидке сортування дорівнювало б значенню рекурсивного виразу.

CN = 2CN/2+N - найкращий випадок.

(2CN/2 покриває витрати по сортуванню двох отриманих підфайлів; N - це вартість обробки кожного елемента, використовуючи один чи інший покажчик.) Нам відомо також, що зразкове значення цього вираження дорівнює CN = N lg N.

Хоча ми зустрічаємося з подібною ситуацією не так часто, але в середньому час роботи програми буде відповідати цій формулі. Якщо взяти до уваги ймовірні позиції кожного розділу, то це зробить обчислення більш складними, але кінцевий результат буде аналогічним.

Методи поліпшення швидкого сортування:

1. Невеликі підфайли.

2. Розподіл по медіані з трьох.

3. Нерекурсивна реалізація.

2.4 Визначення інформаційних зв'язків програмних компонентів

Програмний виріб при завантаженні створює головне вікно за допомогою функції WinMain. Після цього повідомлення від головного вінка і його елементів надсилаються в функцію WndProc, яка в свою чергу їх обробляє і за необхідності виводить їх на екран.

Взаємозв'язок між функціями програми показано на рисунку 2.9.

Рисунок 2.11 - Взаємозв'язок функцій програми

2.5 Написання текстів програми

Оскільки програмним середовищем для розробки даної програми вибрано C, то автоматично зменшується трудомісткість та складність створення цього програмного виробу.

В ході розробки спочатку формувалася блок-схема майбутньої програми. Потім відносно неї створювалося головне меню програми і визначалися основні робочі блоки. При написанні програмного коду в даній розробці по можливості спрощувалися алгоритми виконання операцій. Всі основні операції створенні у вигляді функції. Це дозволяє не тільки зменшити основний код програми, а й пришвидшити процес виконання операцій і з економити місце на диску, що надає їй більш компактного і довершеного вигляду.

При написанні програми перевага надавалася використанню локальних змінних, що дозволяє виконувати програму на комп'ютерах з невеликою кількістю оперативної пам'яті.

Під час розробки велика увага приділялася надійності програмного продукту, тому після кожної створеної функції проводилося тестування на наявність помилок.

Після створення програми проводилося також тестування на правильність виконання алгоритму дій, введення і виведення даних.

2.6 Тестування та налагодження програм

Тестування програми проводилось на базі ПК такої конфігурації апаратного та програмного забезпечення:

· встановлена операційна система: Windows 7;

· процесор: Процесор: AMD-A4-4300;

· оперативна пам'ять: 4 ГБ;

· відеокарта ATI Radeon HD Graphics, 1024 Mb.

Вводилися допустимі і не допустимі дні. При допустимих даних програма працювала стабільно. При введені не допустимих даних виводилася помилка.

3 СПЕЦІАЛЬНИЙ РОЗДІЛ

3.1 Інструкція по встановленню та використанню програми

При запуску програми появиться головне вікно, яке зображене на рисунку 3.1

Рисунок 3.1 - Головне вікно програми

Натиснувши «Сортувати», у робочому полі ви отримаєте відсортовний масив, попередньо його ввівши, та задавши метод та спосіб сортування

ВИСНОВКИ

При написанні даного програмного продукту я ознайомився з мовою програмування С. А зокрема з робою з функціями WinApi.

У даній курсовій роботі описано та створено програму для сортування масивів різними способами. Програма написана на мові програмування C, що робить програмний код зрозумілим навіть для початківця.

ПЕРЕЛІК ПОСИЛАНЬ

1) Методичні вказівки до виконання курсової роботи з системного програмування / Марціяш Г.Я. - Тернопіль.: ТКТНТУ імені Івана Пулюя, 2011.

2) Методичні вказівки для лабораторних робіт з дисципліни „Системне програмування”./Марціяш Г.Я. - Тернопіль.:ТКНТУ імені Івана Пулюя, 2011.

3) М.Уэйт, С.Прата, Д.Мартин Язык Си: Пер с англ.-М.: Мир, 1988.-463 с.,ил.

4) Глинський Я. М., Ахонін В.Є. Ряжська В. А. С++, 2004.- 192 с., іл.

5) http://www.rsdn.ru/article/baseserv/api32.xml

ДОДАТКИ

Додаток А

Код програми:

#include "windows.h"

#include "windowsx.h"

#include "commctrl.h"

#include "mbstring.h"

#include "stdio.h"

#include "stdlib.h"

#include "conio.h"

#include "string.h"

#include "time.h"

#include "stddef.h"

// ідентифікатори випадаючих списків

#define ID_COMBBOX1 4001

#define ID_COMBBOX2 4002

#define ID_EDIT1 4012

#define ID_EDIT2 4013

#define ID_BUTTON1 4015

#define t 10

//static HWND hStatic;

static HWND hStatic;

static HWND window;

static HWND hButton1;

static HWND hCombBox1;

static HWND hCombBox2;

static HWND hEdit1;

static HWND hEdit2;

HINSTANCE hInstance;

HWND hwnd;

LRESULT CALLBACK WndProc(HWND hwnd, UINT Message, WPARAM wparam,LPARAM lparam, HINSTANCE hInstance);

VOID *bubble(INT *a, INT n, BOOL amb);

BOOL sravni(INT a,INT b,BOOL amb);

VOID *bininsert(INT *a,INT n,BOOL amb);

VOID *selectt(INT *a,INT n,BOOL amb);

INT *hoara_1(INT *a,INT m,INT n,BOOL amb);

VOID *hoara(INT *a,INT n,BOOL amb);

VOID *shell(INT *a,INT n,BOOL amb);

VOID *piramida(INT *a,INT n,BOOL amb);

INT *down(INT *a, INT k, INT n,BOOL amb);

INT APIENTRY WinMain(//головна програма

HINSTANCE hInstance,

HINSTANCE hPrevInstance,

LPSTR lpCmdLine,

INT nCmdShow)

{

MSG msg;

WNDCLASS w;

memset(&w,0,sizeof(WNDCLASS));

w.style = CS_HREDRAW | CS_VREDRAW | CS_SAVEBITS;

w.lpfnWndProc = (WNDPROC)WndProc;

w.hInstance = hInstance;

w.hbrBackground = CreateSolidBrush(RGB(0,0,100));

w.lpszClassName = "Windows";

w.hbrBackground = (HBRUSH)( COLOR_WINDOW+1);

RegisterClass(&w);

hwnd = CreateWindow ("Windows","Методи сортування масивів", WS_OVERLAPPED | WS_CAPTION | WS_SYSMENU | WS_MINIMIZEBOX,10,10,400,300,NULL,NULL,hInstance,NULL);

ShowWindow(hwnd,nCmdShow);

UpdateWindow(hwnd);

while(GetMessage(&msg,NULL,0,0))

{

TranslateMessage(&msg);

DispatchMessage(&msg);

}

return msg.wParam;

}

LRESULT CALLBACK WndProc(HWND hwnd, UINT Message, WPARAM wparam,LPARAM lparam, HINSTANCE hInstance) //програма обробки повідомлень

{

INT a[256];

INT metod; //містить номер методу сортування

INT TUP;

CHAR buf[10];

BOOL type;

BOOL flag=TRUE;

INT kil,i,nol,q= -1,kur=0;

//CHAR buf[50];

CHAR c[15];

CHAR h[]=" ";

char ner[]="\r\n";

switch (Message)

{

case WM_CREATE:{//створення елементів вікна

hCombBox1=CreateWindow ("combobox", NULL, WS_CHILD| ES_WANTRETURN | WS_VISIBLE | WS_VSCROLL| CBS_DROPDOWN,10,20,180,200, hwnd, (HMENU) ID_COMBBOX1, hInstance, NULL);

hCombBox2=CreateWindow ("combobox", NULL, WS_CHILD | WS_VISIBLE | WS_VSCROLL| CBS_DROPDOWN,10,50,180,200, hwnd, (HMENU) ID_COMBBOX2, hInstance, NULL);

hEdit1=CreateWindow ("edit", "Введіть масив",WS_VSCROLL| WS_CHILD | ES_NOHIDESEL |WS_VISIBLE| ES_WANTRETURN |ES_AUTOVSCROLL | ES_NUMBER | WS_BORDER | WS_EX_LEFT| ES_MULTILINE | ES_AUTOHSCROLL,10,80,180,180, hwnd, (HMENU) ID_EDIT1, hInstance, NULL);

hEdit2=CreateWindow ("edit", NULL,WS_VSCROLL|WS_CHILD | ES_NOHIDESEL |WS_VISIBLE| ES_WANTRETURN |ES_AUTOVSCROLL | ES_NUMBER | WS_BORDER | WS_EX_LEFT| ES_MULTILINE | ES_AUTOHSCROLL,200,80,180,180, hwnd, (HMENU) ID_EDIT2, hInstance, NULL);

hButton1=CreateWindow ("button","Сортувати", WS_CHILD | WS_VISIBLE | BS_DEFPUSHBUTTON,200,22,180,50,hwnd,(HMENU)ID_BUTTON1, hInstance, NULL);

//вибір методу

SendMessage(hCombBox1,CB_ADDSTRING,0,(LPARAM)"Метод Бульбашки");

SendMessage(hCombBox1,CB_ADDSTRING,0,(LPARAM)"Метод Вибірки");

SendMessage(hCombBox1,CB_ADDSTRING,0,(LPARAM)"Метод Вставки");

SendMessage(hCombBox1,CB_ADDSTRING,0,(LPARAM)"Метод Пірамід");

SendMessage(hCombBox1,CB_ADDSTRING,0,(LPARAM)"Метод Шела");

SendMessage(hCombBox1,CB_ADDSTRING,0,(LPARAM)"Швидке сортування Хора");

//вибір сособу зростання / спадання

SendMessage(hCombBox2,CB_ADDSTRING,0,(LPARAM)"Зростання");

SendMessage(hCombBox2,CB_ADDSTRING,0,(LPARAM)"Спадання");

return 0;

}

case WM_COMMAND:

{

switch (LOWORD(wparam))

{

case ID_BUTTON1:{// натискання кнопки "Сортувати"

//зчитування параметрів

//memset(a,NULL,sizeof(a));

metod=(INT)SendMessage(hCombBox1,CB_GETCURSEL,0,0L); // визначаэ номер строки (обраний метод)

TUP=(INT)SendMessage(hCombBox2,CB_GETCURSEL,0,0L); //визначення типу сортування

kil=(INT)SendMessage(hEdit1,EM_GETLINECOUNT,0,0L);//зчитування номеру строки едіда;

if(metod!=q&&TUP!=q&&kil!=q)

{

if(TUP) type=FALSE;

else type=TRUE;

for(i=0;i<kil;i++)

{

SendMessage(hEdit1,EM_GETLINE,(WPARAM)i,(LPARAM)c);

nol=atoi(c);

if(c!=h) a[i]=atoi(c);

memset(c,' ',sizeof(c));

}

switch(metod){

case 0: {

bubble(a,kil,type);

break;}

case 1:{

bininsert(a,kil,type);

break;}

case 2:{

selectt(a,kil,type);

break;}

case 3:{

shell(a,kil,type);

break;}

case 4:{

piramida(a,kil,type);

break;}

case 5:{

hoara(a,kil,type);

break;}

}

//вивід в едіт

DestroyWindow(hEdit2);

hEdit2=CreateWindow ("edit", NULL,WS_VSCROLL|WS_CHILD | ES_NOHIDESEL |WS_VISIBLE| ES_WANTRETURN |ES_AUTOVSCROLL | ES_NUMBER | WS_BORDER | WS_EX_LEFT| ES_MULTILINE | ES_AUTOHSCROLL,200,80,180,180, hwnd, (HMENU) ID_EDIT2, hInstance, NULL);

UpdateWindow(hwnd);

for(i=0;i<kil;i++)

{

itoa(a[i],c,10);

strcat(c,ner);

SendMessage(hEdit2,EM_REPLACESEL, TRUE,(LPARAM)c);

}

}

else{MessageBox(hwnd,"Заповніть всі поля",NULL,MB_OK);}

return 0;

}}

default:

{

break;

}

return 0;

}

case WM_DESTROY:

{

switch (LOWORD(wparam)){

case 1001:return 0;

case ID_COMBBOX1:return 0;

case ID_COMBBOX2:return 0;

default:{

PostQuitMessage(0);

return 0;

}

}}

}// End switch

return DefWindowProc(hwnd,Message,wparam,lparam);

} // End WndProc

//Функції сортування

//Спосіб сортування

BOOL sravni(INT a,INT b,BOOL amb)

{

if(amb)

return (a<b);

else

return (a>b);

}

//метод бульбашки

VOID *bubble(INT *a,INT n,BOOL amb)

{

INT c,x,i;

for(x=(n-1); x>=1; x-=1)

for(i=1; i<=x; i+=1)

if (sravni(a[i],a[i-1],amb))

{

c=a[i];

a[i]=a[i-1];

a[i-1]=c;

}

}

//метод вставки

VOID *bininsert(INT *a,INT n,BOOL amb)

{

INT x,left,right,sred,i,j;

for( i=1;i<n;i+=1)

if(sravni(a[i-1],a[i],!amb))

{x=a[i];

left=0;

right=i+1;

while(left<=right){

sred=left;

if(sravni(a[sred],x,amb)) left=sred+1;

else right=sred-1;

}

for(j=i-1;j>=left;j-=1) a[j+1]=a[j];

a[left]=x;

}

//return(a);

}

//метод вибірки

VOID *selectt(INT *a,INT n,BOOL amb)

{

INT min, c,i,j;

for(i=0;i<n-1;i+=1)

{

min=i;

for(j=i;j<n;j+=1)

if(sravni(a[j],a[min],amb))min=j;

if(min!=i)

{

c=a[i];

a[i]=a[min];

a[min]=c;

}

}

//return a;

}

//метод Хора

VOID *hoara(INT *a,INT n,BOOL amb)

{

return hoara_1(a,0,n-1,amb);

}

INT *hoara_1(INT *a,INT m,INT n,BOOL amb)

{

INT c;

INT i = m;

INT j = n;

INT x = a[(m+n)/2];

while (i <= j)

{

while (sravni(a[i],x,amb)) i++;

while (sravni(x,a[j],amb)) j--;

if (i <= j)

{

c = a[i];

a[i] = a[j];

a[j] = c;

i+=1;

j-=1;

}

}

if (j > m) a=hoara_1(a, m, j,amb);

if (i < n) a=hoara_1(a, i, n,amb);

return a;

}

//Метод Шела

VOID *shell(INT *a,INT n,BOOL amb)

{

BOOL c;

INT e,g,i,j,tmp;

n = n-1;

g = (n+1)/2;

do

{

i = g;

do

{

j = i-g;

c = TRUE;

do

{

if(sravni(a[j]-1,a[j+g],amb))

{

c = FALSE;

}

else

{

tmp = a[j];

a[j] = a[j+g];

a[j+g] = tmp;

}

j = j-1;

}

while(j>=0&&c);

i = i+1;

}

while(i<=n);

g = g/2;

}

while(g>0);

//return a;

}

//метод Пірамід

INT *down(INT *a, INT k, INT n,BOOL amb) {

INT new_elem;

INT child;

new_elem=a[k];

while(k<=n/2) {

child=2*k;

if(child<n && sravni(a[child],a[child+1],amb))child++;

if(sravni(a[child],new_elem+(1^amb-1^!amb),amb)) break;

a[k]=a[child];

k=child;

}

a[k]=new_elem;

return a;

}

VOID *piramida(INT *a, INT n,BOOL amb)

{

INT i,c;

for(i=n/2+1;i>=0;i-=1) a=down(a,i,n-1,amb);

for(i=n-1;i>0;i-=1) {

c=a[i];

a[i]=a[0];

a[0]=c;

a=down(a,0,i-1,amb);

}

//return a;

}

Размещено на Allbest.ru

...