Сортировка массивов

Сортировка - это процесс упорядочения некоторой последовательности нумерованных объектов в соответствии с заданным признаком. Цель сортировки - облегчить последующий поиск элементов в отсортированной последовательности.

При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, т.е. в частности, недопустимость применения дополнительных массивов. Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя: количество присваиваний и количество сравнений.

Все методы сортировки можно разделить на две большие группы: прямые методы сортировки и улучшенные методы сортировки. Прямые методы сортировки по принципу, лежащему в основе метода, подразделяются на три подгруппы:

- сортировка обменом («пузырьковая» сортировка);

- сортировка вставкой (включением);

- сортировка выбором (выделением).

Прямые методы на практике используются довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов. В то же время, в некоторых случаях (как правило, при небольшой длине массива и/или особом исходном расположении элементов массива) некоторые из прямых методов могут даже превзойти улучшенные методы). Улучшенные методы сортировки, основываясь на тех же принципах, что и прямые, используют некоторые оригинальные идеи для ускорения процесса сортировки. С точки зрения программиста наибольший интерес представляют сортировки массивов, строк, файлов.

Методы вставки и выбора оказываются в среднем приблизительно эквивалентными и в несколько раз (в зависимости от длины массива) лучше, чем метод обмена («пузырька).

Исследования алгоритмов прямых методов сортировки показали, что как по числу сравнений, так и по числу присваиваний они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.

8.2 Практическая часть

Задание 8.2.1

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <conio.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{int p,j,i;

const int N=6;

static int arr [N][N] = { { 1, 2, 3, 4, 5, 6},

{20, 21, 22, 23, 24, 7},

{19, 32, 33, 34, 25, 8},

{18, 31, 36, 35, 26, 9},

{17, 30, 29, 28, 27, 10},

{16, 15, 14, 13, 12, 11} };

for (p=0; p<N/2; p++)

{for (j=p; j<=N-p-1; j++)

cout << setw(4) << arr[p][j];

for (i=p+1; i<N-p; i++)

<< setw(4) << arr[i][N-p-1];

for (j=N-p-2; j>=p; j--)

cout << setw(4) << arr[N-p-1][j];

for (i=N-p-2; i>=p+1; i--)

cout << setw(4) << arr[i][p];}

_getch();

return 0;}

Задание 8.2.2

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <conio.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{void bsort (int*, int);

const int N = 10;

static int arr [N] = {37, 84, 62, 91, 11, 65, 57, 28, 19, 49};

bsort (arr, N);

for (int j=0; j<N; j++)

cout << arr[j] <<" ";

cout << endl;

return 0;}

//------------------------------------

void bsort (int* x, int n)

{int i,j;

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

{for (j=0; j<n;j++)

if (x[j]>x[j+1])

{int r=x[j];

x[j]=x[j+1];

x[j+1]=r;}

for (j=0;j<n; j++)

cout << x[j] << " ";

cout << endl;}}

Задание 8.2.3

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <conio.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{void bsort (int*, int);

const int N=10;

static int arr [N] = {37, 84, 62, 91, 11, 65, 57, 28, 19, 49};

bsort (arr, N);

for (int j=0; j<N; j++)

cout << arr [j] << " ";

cout << endl;

return 0;}

//--------------------------------------

void bsort (int* x, int n)

{int flag = 1, k = n;

while (flag)

{k--;

flag = 0;

for (int j=0; j<k; j++)

if (x[j]>x[j+1])

{int r = x[j];

x[j]=x[j+1];

x[j+1]=r;

flag=1;}}}

Задание 8.2.4

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <conio.h>

#include <stdlib.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{const int n = 10;

int x[n], D[n], i, j;

cout << "x[i]" << endl;

for (i=0; i<n; i++) x[i]=rand();

for (i=0; i<n; i++) cout << x[i] << " ";

cout << endl;

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

D[i]=x[i]%10;

cout << "D[i]" << endl;

for (i=0; i<n; i++) cout <<D[i] << " ";

cout << endl;

int flag = 1, k=n;

while (flag)

{k--;

flag=0;

for (j=0; j<k; j++)

if ((D[j]>D[j+1]) || (D[j] == D[j+1] && x[j]>x[j+1]))

{int r=x[j];

int r1=D[j];

x[j]=x[j+1]; D[j]=D[j+1];

x[j+1]=r; D[j+1] = r1;

flag=1;}}

cout << endl;

for (i=0; i<n; i++) cout << x[i] <<" ";

cout << endl;

for (i=0; i<n; i++) cout << D[i] <<" ";

cout << endl;

return 0;}

Задание 8.2.5

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <conio.h>

#include <stdlib.h>

using namespace std;

int main()

{const int n =10;

int x[n];

int i, j, temp;

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

x[i] = rand();

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

cout << setw(6) << x[i];

cout << endl <<endl;

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

{temp = x[i];

j = i-1;

while ((temp<x[j]) && (j>=0))

{ x[j+1] = x[j];

j--;}

x[j+1] = temp;}

for (i=0; i<n; i++) cout << setw(6) << x[i];

cout << endl;

return 0;}

Задание 8.2.6

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <conio.h>

#include <stdlib.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{const int n = 10;

int x[n];

int i, j;

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

x[i] = rand();

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

cout << setw(6) << x[i];

cout <<endl<<endl;

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

{ int min = x[i];

int i_min = 1;

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

if (x[j] < min)

{ min = x[j];

i_min = j;}

x[i_min] = x[i];

x[i] = min;}

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

cout <<setw(6) << x[i];

cout << endl;

return 0;}

Задание 8.2.7

Текст программы:

Рисунок 8.109 - Скриншот работы программы 8.2.7

Задание 8.2.8

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <conio.h>

#include <stdlib.h>

using namespace std;

const int n=3;

const int m=5;

int _tmain(int argc, _TCHAR* argv[])

{int a [n][m], i, j, x;

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

{for (j=0; j<n; j++)

{a[i][j] = rand();

cout << setw(10)<< a[i][j]<<" ";}

cout << endl;}

cout << endl << endl;

for (j=0; j<m/2; j++)

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

{x=a[i][j];

a[i][j] = a [i][m-(j+1)];

a[i][m-(j+1)]=x;}

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

{for (j=0; j<n; j++)

cout << setw(10) << a[i][j] << " ";

cout << endl; }

_getch();

return 0;}

Задание 8.2.9

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <conio.h>

#include <iomanip>

using namespace std;

const int NROW = 100;

const int NCOL = 40;

void vvod_ar (int arra[NROW][NCOL], int m, int n);

void vyvod_ar (int arra[NROW][NCOL], int m, int n);

void poisk_min (int arra[NROW][NCOL], int m, int n, int &imin, int &jmin);

void del_min (int arra[NROW][NCOL], int m, int n, int imin, int jmin);

int main()

{ int m=10;

int n=9;

int imin, jmin;

int arra [NROW][NCOL] = { {1}, {2}, {3}, {4}, {5} };

int arra1 [][NCOL] = { {1}, {2}, {3}, {4}, {5} };

vvod_ar(arra, m, n);

vyvod_ar(arra, m, n);

poisk_min(arra, m, n, imin, jmin);

cout << "imin = " << imin+1 << endl;

cout << "jmin = " << jmin+1 << endl;

del_min (arra, m, n, imin, jmin);

vyvod_ar(arra, m-1, n-1);

_getch();

return 0;}

void vyvod_ar(int arra[NROW][NCOL], int m, int n)

{for (int i=0; i<m; i++)

{for (int j=0; j<n; j++)

cout << setw(3) << arra[i][j];

cout << endl;}

cout << endl;}

void vvod_ar(int arra [NROW][NCOL], int m, int n)

{for (int i=0; i<m; i++)

for (int j=0; j<n; j++)

arra[i][j] = 1 + rand()%10;}

void poisk_min(int a[NROW][NCOL], int m, int n, int &imin, int &jmin)

{imin = jmin = 0;

int min = a[0][0];

for (int i=0; i<n; i++)

for (int j=0; j<n; j++)

if (a[i][j] <= min) {

min = a[i][j];

imin=i;

jmin=j;}}

void del_min(int a[NROW][NCOL], int m, int n, int imin, int jmin)

{int ii, jj;

for (int i=0; i<m-1; i++)

for (int j=0; j<n-1; j++)

{ if (i >=imin) ii=i+i; else ii=i;

if (j >=jmin) jj=j+j; else jj=j;

a[i][j] = a[ii][jj];}}

Задание 8.2.10

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <conio.h>

#include <stdlib.h>

using namespace std;

const int N = 100;

void vvod_ar(int arra [N][N], int n);

void vyvod_ar(int arra [N][N], int n);

void sun_diag(int arra [N][N], int n);

int _tmain(int argc, _TCHAR* argv[])

{int n=5;

int arra [N][N];

vvod_ar (arra, n);

vyvod_ar (arra, n);

sun_diag (arra, n);

_getch();

return 0;}

void vyvod_ar (int arra[N][N], int n)

{for (int i=0; i<n; i++)

{ for (int j=0; j<n; j++)

cout << setw(3) << arra [i][j];

cout << endl;}

cout << endl;}

void vvod_ar (int arra [N][N], int n)

{for (int i=0; i<n; i++)

for (int j=0; j<n; j++)

arra [i][j] = rand()%2;}

void sun_diag (int a[N][N], int n)

{ int s=0, s1, s2;

for (int i=0; i<n; i++)

s+=a[i][i];

cout << "glav: " << s << endl << endl;

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

{ s1=0; s2=0;

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

{ s1+=a[j][i+j+1];

s2+=a[i+j+1][j];}

cout << "verx: " << s1 << endl;

cout << "nijn: " << s2 << endl;}}

9 ИСПОЛЬЗОВАНИЕ ГРАФИЧЕСКИХ СРЕДСТВ

9.1 Практическая часть

Задание 9.1.1

Текст программы:

void CMFCApplication1Dlg::OnPaint()

{CPaintDC dc(this);

CRect rect;

GetClientRect(&rect);

for (int line = 0; line < 50; line++){

dc.MoveTo(rand() % rect.right, rand() % rect.bottom);

dc.LineTo(rand() % rect.right, rand() % rect.bottom);}}

Задание 9.1.2

Текст программы:

void CMFCApplication9Dlg::OnPaint()

{CPaintDC dc(this);//создаем контекст устройства

int maxX,maxY,stepX,stepY;

CRect rect;

GetClientRect(&rect);//определяем размеры клиентской части окна

maxX=rect.right;

maxY=rect.bottom;

stepX=maxX/8;

stepY=maxY/8;

CPen pen1,pen2;//создаем два пера

pen1.CreatePen(PS_SOLID,2,RGB(0,255,0));

pen2.CreatePen(PS_SOLID,1,RGB(255,0,0));

CBrush brush1,brush2;//создаем две кисти

brush1.CreateSolidBrush(RGB(100,100,100));

brush2.CreateSolidBrush(RGB(255,255,255));

dc.SelectObject(&pen2); //выбрали перо

dc.SelectObject(&brush1); //выбрали кисть

dc.Ellipse(0,0,maxX,maxY); //нарисовали фигуру

dc.SelectObject(&brush2); //выбрали кисть

dc.Ellipse(stepX*1,stepY*1,maxX-stepX*1,maxY-stepY*1); //нарисовали фигуру

dc.SelectObject(&brush1); //выбрали кисть

dc.Ellipse(stepX*2,stepY*2,maxX-stepX*2,maxY-stepY*2); //нарисовали фигуру

dc.SelectObject(&brush2); //выбрали кисть

dc.Ellipse(stepX*3,stepY*3,maxX-stepX*3,maxY-stepY*3); //нарисовали фигуру

dc.SelectObject(&pen1); //выбрали перо и рисуем две линии

dc.MoveTo(0,maxY / 2); dc.LineTo(maxX,maxY /2);

dc.MoveTo(maxX / 2,0); dc.LineTo(maxX /2,maxY);}

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

...