Здравствуйте, Dima Fedorov!
Вот примерная программа.
Без потери общности принято, что всего чисел 200, каждое в диапазоне от 1 до 100
Алгоритм далеко не самый оптимальный, но вполне работоспособный.
Сложность можно оценить, как О(n
2+n), т.к. приходится сравнивать каждого с каждым,
а потом формировать окончательный массив.
[code h=200]/*
В методе подсчета сравнений используется вспомогательный массив,
который обнуляется. Организуется цикл, в котором происходит подсчет
для каждого элемента исходного массива количество элементов,
в которые меньше данного и это число записывается в вспомогательный массив
(если сортировка по возрастанию).
Затем берутся элементы из вспомогательного массива
и уже упорядоченный массив образуется путем постановки на
k место упорядоченного массива элементов исходного массива.
*/
#include "stdafx.h"
#include "resource.h"
HINSTANCE hInst;
char *szTitle = "Sort of compare"; //заголовок окна
char *szWindowClass = "Sort_Compare";//имя класса окна
int const n = 200; //количество разных чисел
int const max = 100; //верхний предел чисел
int const min = 1; //нижний предел чисел
//указатели на массивы чисел
int *a; //исходный
int *b; //вспомогательный
int *c; //отсортированный
BOOL fData = FALSE; //признак заполненности данных
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
void SortCmp(int *, int *, int *, int const);
int APIENTRY WinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR lpCmdLine,
int nCmdShow)
{
MSG msg;
MyRegisterClass(hInstance);
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
while (GetMessage(&msg, NULL, 0, 0))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
return msg.wParam;
}
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = (WNDPROC)WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = LoadIcon(hInstance, (LPCTSTR)IDI_SORT_CMP);
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = (LPCSTR)IDC_SORT_CMP;
wcex.lpszClassName = szWindowClass;
wcex.hIconSm = LoadIcon(wcex.hInstance, (LPCTSTR)IDI_SMALL);
return RegisterClassEx(&wcex);
}
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
HWND hWnd;
hInst = hInstance; // Store instance handle in our global variable
hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
if (!hWnd)
{
return FALSE;
}
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
return TRUE;
}
//подпрограмма сортировки методом сравнения
//параметры: адреса исходного, вспомогательного, отсортированного и количество элементов
//исходный заполнен случайными числами в диапазоне [min=1,max=100]
//вспомогательный и отсортированный массивы обнулены
void SortCmp(int *a, int *b, int *c, int const n)
{
int i, j;
//сравниваем каждый с каждым и подсчитываем, когда каждый элемент больше всех остальных
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
if (a[j]>a[i])
b[j]++;
}
}
//заполняем отсортированный массив в соответствии с полученными количествами
//учитываем, что могут быть одинаковые числа,
//для которых будет одинаковое количество сравнений
for (i=0; i<n; i++)
{
j = b[i]; //количество сравнений будет индексом, куда вставляем значение
while(c[j]!=0) //если уже записано (встретились одинаковые числа!)
j++; // то найдем индекс, где еще не занято! Одинаковые числа будут рядом!
c[j] = a[i]; //запоминаем исходное число на соответствующем месте
}
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
HBRUSH hBrush, hOldBrush;
PAINTSTRUCT ps;
HDC hdc;
int i;
switch (message)
{
case WM_CREATE:
srand( (unsigned)time( NULL ) ); //инициируем последовательность псевдослучайных чисел
a = (int*)malloc(n*sizeof(int)); //запросим память под массивы чисел
b = (int*)malloc(n*sizeof(int));
c = (int*)malloc(n*sizeof(int));
//создадим кнопку для запуска нового расчета
CreateWindow("button", "Start", WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,
430, 10, 100, 25, hWnd, (HMENU)IDM_START, hInst, NULL);
break;
case WM_COMMAND:
switch (LOWORD(wParam))
{
case IDM_START: //новый расчет!
for(i=0; i<n; i++)
{ //генерируем n новых случайных чисел
a[i] = rand()%(max-min+1)+min; //в диапозоне [min,max]
c[i] = b[i] = 0; //обнуляем вспомогательный и отсортированные массивы
}
SortCmp(a, b, c, n); //сортируем
fData = TRUE; //помечаем, что еть данные для отображения
InvalidateRect(hWnd, NULL, TRUE); //даем команду на перерисовку
break;
case IDM_EXIT: //выход
free(a); //освобждаем память
free(b);
free(c);
DestroyWindow(hWnd);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
break;
case WM_PAINT: //рисуем на окне
hdc = BeginPaint(hWnd, &ps);
hBrush = CreateSolidBrush(GetSysColor(COLOR_BTNFACE)); //создаем серую кисть
hOldBrush = (HBRUSH)SelectObject(hdc, hBrush); //выберем
Rectangle(hdc, 10, 10, 410, 210); //рисуем два прямоугольника, первый - исходные числа
Rectangle(hdc, 10, 220, 410, 420); //второй - отсортированные
if (fData) //данные есть?
{
for(i=0; i<n; i++) //рисуем массив черных точек
{ //точки в один пиксель отделяем друг от друга одним пикселем
SetPixel(hdc, 11+i*2, 11+(100-a[i])*2, RGB(0,0,0));
SetPixel(hdc, 11+i*2, 221+(100-c[i])*2, RGB(0,0,0));
}
}
SelectObject(hdc, hOldBrush); //вернем старую кисть
DeleteObject(hBrush); //удалим созданную серую кисть
EndPaint(hWnd, &ps);
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}[/code]
Все файлы, необходимые для проекта, который создайте в своей студии
sort_cmp.rar (20.1 кб)