Сортування методом вставок

Міністерство  освіти і науки  України

   Полтавський національний технічний  університет

   Імені Юрія Кондратюка

   Факультет інформаційних та телекомунікаційних технологій і систем

   Кафедра прикладної математики, інформатики і  математичного моделювання 
 
 
 
 
 
 
 
 

                                    КУРСОВА РОБОТА

   з дисципліни «Програмування»

   Сортування  методом вставок 
 
 
 
 
 

   101 ТІ   09167    КР 
 
 
 
 
 
 

                                                                                                Розробив студент гр.101-ТІ

                                                                                                  Бондаренко Є.В.

  16.03.2010 

                                                                                                     Керівник роботи

  Горбань А.Г. 
 
 
 
 

Полтава 2010

ЗМІСТ

1. Постановка задачі…………………………………………………………..3
2. Теоретичне обґрунтування і алгоритм вирішення задачі………………..3
3. Код програми з коментарями……………………………………………...3
4. Зовнішній вигляд вікна програми………………………………………..10
5. Список використаної літератури………………………………………...11

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. Постановка  задачі

  Впорядкувати  вибраний випадковим чином масив  з десяти цілих чисел за зростанням та за спаданням ( тобто переставити його елементи так, щоб для всіх i виконувалась умова відповідно), використовуючи   метод сортування вставками.

2. Теоретичне обґрунтування методу і алгоритм вирішення задачі

   Метод ґрунтується на наступному: вважається, що перед розглядом елемента попередні елементи вже впорядковані, і вставляється у відповідне місце. Сортування списку починається з другого елементу. Його значення порівнюється зі значенням першого елемента, і, якщо впорядкованість порушена, то елементи та переставляються. Потім значення елемента порівнюється зі значеннями елементів та . Як тільки програма виявляє, що -ший елемент масиву менше (при сортування за зростанням) -того елемента, вона копіює значення цього елемента в буферну змінну і з початку масиву до аналізує, доки значення буферної змінної не буде менше будь-якого елемента 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 
 

3. Код програми з коментарями

#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("BUTTON", "Заповнити масив", WS_VISIBLE|WS_CHILD,15,15,130,30,hwnd,(HMENU) IDB_BUTTON1, hThisInstance, NULL);

      hButton2=CreateWindow("BUTTON", "Сортувати за зростанням", WS_VISIBLE|WS_CHILD,15,55,210,30,hwnd,(HMENU) IDB_BUTTON2, hThisInstance, NULL);

      hButton3=CreateWindow("BUTTON", "Сортувати за спаданням", WS_VISIBLE|WS_CHILD,290,55,215,30,hwnd,(HMENU) IDB_BUTTON3, hThisInstance, NULL);

      hButton4=CreateWindow("BUTTON", "Записати результат у файл і вийти", WS_VISIBLE|WS_CHILD,55,290,400,30,hwnd,(HMENU) IDB_BUTTON4, hThisInstance, NULL); 

      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[i]);

            if(a[i]<10)

                  intToStr2(a[i]); 

            if(a[i]<10) TextOut(hdc, 305+20*i,20,dep, 1);

            if(a[i]>9) TextOut(hdc, 305+20*i,20,dep, 2);

    }

    return 0;

} 

void ascSort() // Функція сортування за зростанням

{

    // Починаємо з другого елемента

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

      {

         // Поточний елемент