Сортування методом вставок
Міністерство освіти і науки України
Полтавський національний технічний університет
Імені Юрія Кондратюка
Факультет інформаційних та телекомунікаційних технологій і систем
Кафедра
прикладної математики,
інформатики і
математичного моделювання
з дисципліни «Програмування»
Сортування
методом вставок
101
ТІ 09167
КР
16.03.2010
Горбань
А.Г.
Полтава 2010
ЗМІСТ
- Постановка
задачі…………………………………………………………..
3 - Теоретичне обґрунтування і алгоритм вирішення задачі………………..3
- Код програми
з коментарями……………………………………………..
.3 - Зовнішній вигляд вікна програми………………………………………..10
- Список використаної літератури………………………………………...11
- Постановка задачі
Впорядкувати вибраний випадковим чином масив з десяти цілих чисел за зростанням та за спаданням ( тобто переставити його елементи так, щоб для всіх i виконувалась умова відповідно), використовуючи метод сортування вставками.
- Теоретичне обґрунтування методу і алгоритм вирішення задачі
Метод ґрунтується на наступному: вважається, що перед розглядом елемента попередні елементи вже впорядковані, і вставляється у відповідне місце. Сортування списку починається з другого елементу. Його значення порівнюється зі значенням першого елемента, і, якщо впорядкованість порушена, то елементи та переставляються. Потім значення елемента порівнюється зі значеннями елементів та . Як тільки програма виявляє, що -ший елемент масиву менше (при сортування за зростанням) -того елемента, вона копіює значення цього елемента в буферну змінну і з початку масиву до аналізує, доки значення буферної змінної не буде менше будь-якого елемента X. Потім частина масиву починаючи з X до -того елемента, переміщується на одну комірку в бік зростання, і на місце, яке звільнилося записується значення елемента, який переміщуємо. І так далі до кінця масиву ми порівнюємо -тий та -ший елементи. Наприклад:
41 54 10 66 27 42 80 61 43 37
^ <~~
10 41 54 66 27 42 80 61 43 37
^ <~~
10 27 41 54 66 42 80 61 43 37
^ <~~
10 27 41 42 54 66 80 61 43 37
^ <~~
10 27 41 42 54 61 66 80 43 37
^ <~~
10 27 41 42 43 54 61 66 80 37
^
10 27 37
41 42 43 54 61 66 80
- Код програми з коментарями
#include <windows.h>
#include <fstream.h>
#define IDB_BUTTON1 101
#define IDB_BUTTON2 102
#define IDB_BUTTON3 103
#define IDB_BUTTON4 104
HWND hwnd, hButton1, hButton2, hButton3, hButton4;
HDC hdc;
int a[10],i, m, n;
int seed;
int counter = 1; // Лічильник рядка
int printArray(int a[]);
void genArr();
void ascSort();
void decSort();
void intToStr(int pos);
void intToStr2(int pos);
void CleanGen(void);
void CleanAsc(void);
void CleanDec(void);
char * dep = new char;
ofstream fout("InsertSortOut.txt"); // Файл, у якому
зберігатиметься результат сортування.
/* Declare Windows procedure */
LRESULT CALLBACK WindowProcedure
(HWND, UINT, WPARAM, LPARAM);
/* Make the class name into a global variable */
char szClassName[ ] = "WindowsApp";
int WINAPI WinMain (HINSTANCE
hThisInstance,HINSTANCE hPrevInstance,LPSTR lpszArgument,int nFunsterStil)
{
HWND hwnd; /* This is the handle for our window */
MSG messages; /* Here messages to the application are saved */
WNDCLASSEX
wincl; /*
Data structure for the windowclass */
/* The Window structure */
wincl.hInstance = hThisInstance;
wincl.lpszClassName = szClassName;
wincl.lpfnWndProc = WindowProcedure; /* This function is called by windows */
wincl.style = CS_DBLCLKS; /* Catch double-clicks */
wincl.cbSize
= sizeof (WNDCLASSEX);
/* Use default icon and mouse-pointer */
wincl.hIcon = LoadIcon (NULL, IDI_APPLICATION);
wincl.hIconSm = LoadIcon (NULL, IDI_APPLICATION);
wincl.hCursor = LoadCursor (NULL, IDC_ARROW);
wincl.lpszMenuName = NULL; /* No menu */
wincl.cbClsExtra = 0; /* No extra bytes after the window class */
wincl.cbWndExtra = 0; /* structure or the window instance */
/* Use Windows's default color as the background of the window */
wincl.hbrBackground
= (HBRUSH) COLOR_BACKGROUND;
/* Register the window class, and if it fails quit the program */
if (!RegisterClassEx (&wincl))
return 0;
/* The class is registered, let's create the program*/
hwnd = CreateWindowEx (
0, /* Extended possibilites for variation */
szClassName, /* Classname */
"Сортування методом вставок", /* Title Text */
WS_OVERLAPPEDWINDOW, /* default window */
CW_USEDEFAULT, /* Windows decides the position */
CW_USEDEFAULT, /* where the window ends up on the screen */
535, /* The programs width */
370, /* and height in pixels */
HWND_DESKTOP, /* The window is a child-window to desktop */
NULL, /* No menu */
hThisInstance, /* Program Instance handler */
NULL /* No Window Creation data */
);
/* Make the window visible on the screen */
ShowWindow
(hwnd, nFunsterStil);
HDC hdc = GetDC(hwnd);
SetBkMode
(hdc, TRANSPARENT);
hButton1=CreateWindow("
hButton2=CreateWindow("
hButton3=CreateWindow("
hButton4=CreateWindow("
TextOut(hdc,
150,20,"Згенерований масив", 19);
MoveToEx(hdc,257, 55, NULL);
LineTo(hdc,257,275);
/* Run the message loop. It will run until GetMessage() returns 0 */
while (GetMessage (&messages, NULL, 0, 0))
{
/* Translate virtual-key messages into character messages */
TranslateMessage(&messages);
/* Send message to WindowProcedure */
DispatchMessage(&messages);
}
/* The program return-value is 0 - The value that PostQuitMessage() gave */
return messages.wParam;
}
void genArr() // Функція генерації масиву з десяти випадкових цілих чисел
{
srand(seed);
for (i=0;i<10;i++)
{
a[i]=rand() % 100;
seed++;
}
printArray(a);
}
int printArray(int a[]) // Функція виводу згенерованого масиву
{
for (i=0;i<10;i++)
{
if (a[i]>9)
intToStr(a[
if(a[i]<10)
intToStr2(a[
if(a[i]<10)
if(a[i]>9)
}
return 0;
}
void ascSort() // Функція сортування за зростанням
{
// Починаємо з другого елемента
for (i=1;i<10;i++)
{
// Поточний елемент
n=a[i];
// Номер попереднього елемента
m=i-1;
// Порівнюємо з попереднім елементом
/* Якщо поточний елемент менший від попереднього, то переставляємо його ближче до початку масиву */
/* Повторюємо, доки не дійдемо до початку масиву або доки попередній елемент не виявиться меншим за поточний */
while ((m>=0)&&(a[m]>n)) // Якщо дана умова виконується.
{
a[m+1]=a[m]; // Міняємо місцями поточний і попередній елементи.
m=m-1; // Зміщуємо попередній елемент на одиницю.
a[m+1]=n; // Вставляємо на місце зміщеного елемента поточний елемент.
}
for (int k=0;k<10;k++) // Виведення результатів сортування у вікно програми
{
if (a[k]>9)
intToS
if(a[k]<10)
intToS
if(a[k]<10)
if(a[k]>9) TextOut(hdc, 20 + 20 * k,80 + 20 * counter,dep, 2);
}
counter++;
}
counter=1;
fout << "Сортування за зростанням:\t "; // Збереження результатів сортування у файлі
for (i=0;i<10;i++)
{
fout << a[i] << " ";
}
fout << "\n";
}
void decSort()// Функція сортування за спаданням
{
// Починаємо з другого елемента
for (i=1;i<10;i++)
{
// Поточний елемент
n=a[i];
// Номер попереднього елемента
m=i-1;
// Порівнюємо з попереднім елементом
/* Якщо поточний елемент більший від попереднього, то переставляємо його ближче до початку масиву */
/* Повторюємо, доки не дійдемо до початку масиву або доки попередній елемент не виявиться більшим за поточний*/
while ((m>=0)&&(a[m]<n)) // Якщо дана умова виконується.
{
a[m+1]=a[m]; // Міняємо місцями поточний і попередній елементи.
m=m-1; // Зміщуємо попередній елемент на одиницю.
a[m+1]=n; // Вставляємо на місце зміщеного елемента поточний елемент.
}
for (int k=0;k<10;k++) // Виведення результатів сортування у вікно програми
{
if (a[k]>9)
intToStr(a[
if(a[k]<10)
intToStr2(a[
if(a[k]<10)
if(a[k]>9) TextOut(hdc, 300 + 20 * k,80 + 20 * counter,dep, 2);
}
counter++;
}
counter=1;
fout << "Сортування за спаданням:\t "; // Збереження результатів сортування у файлі
for (i=0;i<10;i++)
{
fout << a[i] << " ";
}
fout
<< "\n";
}
void intToStr(int pos) /* Функція перетворення двоцифрових цілочислових змінних в текстові символи */
{
int inter;
char
c;
for(int i=1; i<3; i++) // Проходимо цикл двічі, оскільки маємо двоцифрове число
{
inter = pos % 10; //
Починаємо перетворення цифри з розряду
одиниць
switch(inter)
{
case 0: c = '0'; break;
case 1: c = '1'; break;
case 2: c = '2'; break;
case 3: c = '3'; break;
case 4: c = '4'; break;
case 5: c = '5'; break;
case 6: c = '6'; break;
case 7: c = '7'; break;
case 8: c = '8'; break;
case 9: c = '9'; break;
}
dep[2-i] = c; // Записуємо результат перетворення в текстову змінну
pos = pos/10; // Переходимо до розряду десятків
}
}
void intToStr2(int pos) /* Функція перетворення одноцифрових цілочислових змінних в текстові символи */
{
int inter;
char
c;
for(int i=1; i<2; i++) // Проходимо цикл тільки 1 раз оскільки маємо одноцифрове число число
{
inter = pos;
switch(inter)
{
case 0: c = '0'; break;
case 1: c = '1'; break;
case 2: c = '2'; break;
case 3: c = '3'; break;
case 4: c = '4'; break;
case 5: c = '5'; break;
case 6: c = '6'; break;
case 7: c = '7'; break;
case 8: c = '8'; break;
case 9: c = '9'; break;
}
dep[1-i] = c; // Записуємо результат перетворення в текстову змінну
}
}
void CleanGen(void) // Функція очищення поля виводу згенерованого масиву
{
Rectangle(hdc,302,17,
}
void CleanAsc(void) // Функція очищення поля виводу матриці сортування за зростанням
{
Rectangle(hdc,15,93,223,
}
void CleanDec(void) // Функція очищення
поля виводу матриці сортування за спаданням
{
Rectangle(hdc,290,93,
}
LRESULT CALLBACK WindowProcedure (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
switch (message) /* handle the messages */
{
case WM_COMMAND:
hdc= GetDC(hwnd);
if(LOWORD(
if(LOWORD(
if(LOWORD(
if(LOWORD(
break;
case WM_DESTROY:
PostQuitMessage (0); /* send a WM_QUIT to the message queue */
break;
default: /* for messages that we don't deal with */
return DefWindowProc (hwnd, message, wParam, lParam);
}
return 0;
}
- Зовнішній вигляд вікна програми
- Список використаної літератури
- Іванов Б.Н. Дискретна математика. Алгоритми і програми. - Москва , 2003. - 288 с.
- Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. - Москва, 1978. - 355 с.
- Страуструп Б. Язык программирования С++. - Санкт - Петербург, 1999. - 991 с.