Виды сортировок: список, массив, вектор

«SORTI.CPP» - модуль, в котором находятся подпрограммы 3-х сортировок, подпрограммы выводящие время начала сортировки и время конца сортировки и общее время сортировки, подпрограмма генерирование массива (случайным образом, по убыванию и по возрастанию)

«FILI.CPP» - модуль, в котором находятся подпрограммы записи данных на внешнюю память.

void puzir (int * & kop,int razmer) - даннай функций сортирует переданный массив методом пузырька.

Пример работы алгоритма:

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2

(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах

(8 > 5), алгоритм не меняет их местами.

Второй проход:

(1 4 2 5 8) (1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.

Третий проход:

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)Теперь массив отсортирован и алгоритм может быть завершён.

void protalkivanie (int * & kop,int razmer) - функция сортирующая массив методом выбора.

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.

Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов a [i] ... a [n] и меняем его местами с a [i]. Последовательность шагов при n=5 изображена на рисунке ниже.

Вне зависимости от номера текущего шага i, последовательность a [0]...a [i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a [n] оказывается отсортированной, а a [n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

void vstavka (int * & kop,int razmer) - функция сортирующая массив методом вставки.

Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.

Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале «вырастает» отсортированная последовательность.

Однако в сортировке можно было четко заявить, что на i-м шаге элементы a [0]...a [i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a [0]...a [i] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.

Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a [0]...a [i] и неупорядоченную a [i + 1]...a [n].

На следующем, (i + 1)-м каждом шаге алгоритма берем a [i + 1] и вставляем на нужное место в готовую часть массива.

Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним.

В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется.

Таким образом, в процессе вставки мы «просеиваем» элемент x к началу массива, останавливаясь в случае, когда

- найден элемент, меньший x или

- достигнуто начало последовательности.

void midalina9 (kop,razmer,iter) - функция сортирующая массив.

2.3 Алгоритм сортировки

сортировка множество программа

Листинг программы

Файл МENU.CPP

#include <graphics.h>

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

#include «SORTI.CPP»

#include «FILE.CPP»

int Zadaniemassiva (int midx,int midy,int& metod,long int& razmer,int& p) {

int i=0;

setfillstyle (0,1);

bar (0,0,midx * 2,midy / 2 + 40);

outtextxy (midx / 25, midy / 5, «Vvedite razmer massiva: «);

outtextxy (midx / 25, midy / 5-20, «Massiv ne bolee 24500 elementov!»);

char symbol [6],m [2]={' ','\0'};

while ((i<5) && ((symbol [i]!=13) || (i==0))) {

symbol [i]=getch ();

if ((symbol [0]!='0') && (symbol [i]>='0') && (symbol [i]<='9')) {

m [0]=symbol [i];

i + + ;

outtextxy (midx / 25 + 190 + i * 8, midy / 5, m);

}

else if ((symbol [i]==8) && (i!=0)){

setfillstyle (0,2);

bar (midx / 25 + 190 + i * 8,midy / 5 + 10,midx / 25 + 190 + i * 12 + 50,midy / 5-10);

i--;

}

}

symbol [i]='\0';

if (atol (symbol)>24500) return Zadaniemassiva (midx,midy,metod,razmer,p);

razmer=atoi (symbol);

setfillstyle (1,2);

bar (midx / 25 + 26 * 7,midy / 5 + 15,midx / 25 + 26 * 7 + 16 * 7,midy / 5 + 30);

outtextxy (midx / 25, midy / 5 + 20, «Tip zapolneni9 massiva: Random Po Vozrastaniu Po ubivaniju»);

int x;

metod=1;

while (x!=13) {

x=getch ();

if (x==77) {

setfillstyle (0,1);

bar (midx / 25 + 26 * 7,midy / 5 + 15,midx / 25 + 1000,midy / 5 + 30);

if (metod==3) metod=0;

metod + + ;

setfillstyle (1,2);

bar (midx / 25 + 26 * 7 + (metod-1) * 16 * 7,midy / 5 + 15,midx / 25 + 26 * 7 + metod * 16 * 7,midy / 5 + 30);

outtextxy (midx / 25, midy / 5 + 20, «Tip zapolneni9 massiva: Random Po Vozrastaniu Po ubivaniju»);

if (metod==3) metod=0;

}

if (x==75) {

setfillstyle (0,1);

bar (midx / 25 + 26 * 7,midy / 5 + 15,midx / 25 + 1000,midy / 5 + 30);

if (metod==0) metod=3;

metod--;

if (metod==0) metod=3;

setfillstyle (1,2);

bar (midx / 25 + 26 * 7 + (metod-1) * 16 * 7,midy / 5 + 15,midx / 25 + 26 * 7 + metod * 16 * 7,midy / 5 + 30);

outtextxy (midx / 25, midy / 5 + 20, «Tip zapolneni9 massiva: Random Po Vozrastaniu Po ubivaniju»);

}

}

p=1;

return 0;

}

int Podmenu (int midx,int midy,int h) {

moveto ((midx + 110),midy + h * 30);

outtext («Po Ubivaniju»);

moveto ((midx + 110),midy + h * 30 + 30);

outtext («Po Vozrastaniju»);

return 0;

}

int F1 (int midx,int midy) {

moveto ((midx-7 * 14),midy-30);

outtext («Zadanie parametrov masiva»);

moveto ((midx-7 * 3),midy);

outtext («Puzirek»);

moveto ((midx-7 * 3),midy + 30);

outtext («Vstavki»);

moveto ((midx-7 * 7),midy + 60);

outtext («Protalkivani9»);

moveto ((midx-7 * 7),midy + 90);

outtext («Piramidalina9»);

moveto ((midx-7 * 2),midy + 120);

outtext («Exit»);

return 0;

}

int F (int midx,int midy,int h,int p) {

int y=midy;

for (int i=-30;i<=120;i + =30) {

if (p==0) {

setfillstyle (1,7);

bar (midx-100, y-10 + i, midx + 100,y + 10 + i);

}

if ((p==1) || (-1== (i / 30)) || ((i / 30)==4)) {

setfillstyle (1,2);

bar (midx-100, y-10 + i, midx + 100,y + 10 + i);

}

if (h== (i / 30)) {

setfillstyle (1,3);

bar (midx-100, y-10 + i, midx + 100, (y + 10) + i);

}

}

return F1 (midx,midy);

}

int F2 (int midx,int midy,int h,int k) {

int poly [12];

for (int i=0;i<60;i + =30) {

setfillstyle (1,2);

poly [0]= midx + 100;

poly [1]= midy + h * 30 + i;

poly [2]=midx + 110;

poly [3]=midy + 10 + h * 30 + i;

poly [4]=midx + 230;

poly [5]=midy + 10 + h * 30 + i;

poly [6]=midx + 230;

poly [7]=midy-10 + h * 30 + i;

poly [8]=midx + 110;

poly [9]=midy-10 + h * 30 + i;

poly [10]=midx + 100;

poly [11]=midy + h * 30 + i;

drawpoly (6, poly);

floodfill (midx + 101,midy + h * 30 + i, 15);

if (k== (i / 30)) {

setfillstyle (1,3);

poly [0]= midx + 100;

poly [1]= midy + h * 30 + i;

poly [2]=midx + 110;

poly [3]=midy + 10 + h * 30 + i;

poly [4]=midx + 230;

poly [5]=midy + 10 + h * 30 + i;

poly [6]=midx + 230;

poly [7]=midy-10 + h * 30 + i;

poly [8]=midx + 110;

poly [9]=midy-10 + h * 30 + i;

poly [10]=midx + 100;

poly [11]=midy + h * 30 + i;

drawpoly (6, poly);

floodfill (midx + 101,midy + h * 30 + i, 15);

}

}

Podmenu (midx,midy,h);

return 0;

}

int main (void)

{

int gdriver = DETECT, gmode, errorcode;

int midx, midy, i;

initgraph (&gdriver, &gmode, ««);

midx = getmaxx () / 2;

midy = getmaxy () / 3;

int j=midy-30;

int h=-1,k=0,p=0;

unsigned long int iter=0;

char x;

char * s;

char * d;

int metod,r;

long int razmer;

double time1,s1;

while (x!=113) {

F (midx,midy,h,p);

x=getch ();

if (x==80) {

h + + ;

setfillstyle (0,2);

bar (0,midy / 2,midx / 2 + 60,midy * 2);

bar (0,midy / 2,midx * 2,midy / 2 + 40);

bar (midx / 25,midy + 170,midx,midy + 190);

}

if (x==72) {

h--;

setfillstyle (0,2);

bar (0,midy / 2,midx / 2 + 60,midy * 2);

bar (0,midy / 2,midx * 2,midy / 2 + 40);

bar (midx / 25,midy + 170,midx,midy + 190);

}

if (h==5) h=-1;

if (h==-2)h=4;

if (p==0) {

if (h==0) h=4;

if (h==3) h=-1;

}

F (midx, midy, h, p);

if ((x==13) && (h!=4) && (h!=-1)) { int k=0;

setfillstyle (0,2);

bar (0,midy / 2 + 20,midx / 2 + 60,midy * 2);

bar (0,midy / 2,midx * 2,midy / 2 + 40);

bar (midx / 25,midy + 170,midx,midy + 190);

while (x!=8) {

if (x==80) k + + ;

if (x==72) k--;

if (k==2) k=0;

if (k==-1) k=1;

F2 (midx,midy,h,k);

x=getch ();

if (x==13) {

int * kop=new int [razmer];

massiv (kop,razmer,metod);

moveto (midx / 25,midy / 2);

outtext («Massiv sgenerirovan»);

moveto (midx / 25,midy / 2 + 20);

outtext («i soxranen v»);

moveto (midx / 25,midy / 2 + 40);

outtext («C: / BORLANDC / BIN / 2.BAK»);

File1 (kop,razmer);

if (h==0){

na4alo (time1,r,s1);

puzir (kop,razmer,iter);

konec (time1,r,s1);

}

if (h==1) {

na4alo (time1,r,s1);

vstavka (kop,razmer,iter);

konec (time1,r,s1);

}

if (h==2) {

na4alo (time1,r,s1);

protalkivanie (kop,razmer,iter);

konec (time1,r,s1);

}

if (h==3) {

na4alo (time1,r,s1);

Pirmidalina9 (kop,razmer,iter);

konec (time1,r,s1);

}

File (kop,k,razmer);

x=8;

delete (kop);

moveto (midx / 25,midy);

outtext («Massiv otsortirovan»);

if (h==0) {

moveto (midx / 25,midy + 20);

outtext («metodom puzirika!»);

}

if (h==1) {

moveto (midx / 25,midy + 20);

outtext («Metodom vstavki!»);

}

if (h==2) {

moveto (midx / 25,midy + 20);

outtext («Metodom protalkivani9!»);

}

if (h==3) {

moveto (midx / 25,midy + 20);

outtext («Piramidalinoi sortirovkoi»);

}

moveto (midx / 25,midy + 40);

outtext («Massiv soxranen v»);

moveto (midx / 25,midy + 60);

outtext («C: / BORLANDC / BIN / 1.BAK»);

ultoa (iter,d,10);

outtextxy (midx / 25,midy + 180,»Kolli4estvo itteracii:»);

outtextxy (midx / 25 + 7 * 25,midy + 180,d);

}

}

setfillstyle (1,16);

bar (midx + 100,midy-90,midx + 300,midy + 200);

}

if ((x==13) && (h==4)) x=113;

if ((x==13) && (h==-1)) Zadaniemassiva (midx,midy,metod,razmer,p);

}

closegraph ();

return 0;

}

Файл SORTI.CPP

#include <dos.h>

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

int na4alo (double& time1,int& r,double& s1) {

char min [10];

char sec [10];

char chas [10];

char hund [10];

struct time t;

gettime (&t);

itoa (t.ti_hour,chas,10);

itoa (t.ti_min,min,10);

itoa (t.ti_sec,sec,10);

itoa (t.ti_hund,hund,10);

for (int i=0;min [i];i + + );

if (i==1) {

min [1]=min [0];

min [0]='0';

sec [2]='\0';

}

for (i=0;sec [i];i + + );

if (i==1) {

sec [1]=sec [0];

sec [0]='0';

sec [2]='\0';

}

for (i=0;hund [i];i + + );

if (i==1) {

hund [1]=hund [0];

hund [0]='0';

hund [2]='\0';

}

setfillstyle (1,0);

bar (300,390,300 + 40 * 7,450);

outtextxy (300,400,»Vremia na4ala sortirovki:»);

outtextxy (300 + 29 * 7,400,chas);

outtextxy (300 + 31 * 7,400,»:»);

outtextxy (300 + 32 * 7,400,min);

outtextxy (300 + 34 * 7,400,»:»);

outtextxy (300 + 35 * 7,400,sec);

outtextxy (300 + 37 * 7,400,».»);

outtextxy (300 + 38 * 7,400,hund);

s1=t.ti_hund;

time1=t.ti_min * 60 + t.ti_sec + (s1 / 100);

r=t.ti_hour;

return 0;

}

void konec (double time1,int r,int s1)

{

int r2;

char min [10];

char sec [10];

char chas [10];

char hund [10];

char time [10];

char timer [10];

struct time t2;

gettime (&t2);

itoa (t2.ti_hour,chas,10);

itoa (t2.ti_min,min,10);

itoa (t2.ti_sec,sec,10);

itoa (t2.ti_hund,hund,10);

for (int i=0;min [i];i + + );

if (i==1) {

min [1]=min [0];

min [0]='0';

sec [2]='\0';

}

for (i=0;sec [i];i + + );

if (i==1) {

sec [1]=sec [0];

sec [0]='0';

sec [2]='\0';

}

for (i=0;hund [i];i + + );

if (i==1) {

hund [1]=hund [0];

hund [0]='0';

hund [2]='\0';

}

setfillstyle (1,0);

bar (300 + 29 * 7,410,300 + 40 * 7,430);

outtextxy (300,420,»Vremia konca sortirovki:»);

outtextxy (300 + 29 * 7,420,chas);

outtextxy (300 + 31 * 7,420,»:»);

outtextxy (300 + 32 * 7,420,min);

outtextxy (300 + 34 * 7,420,»:»);

outtextxy (300 + 35 * 7,420,sec);

outtextxy (300 + 37 * 7,420,».»);

outtextxy (300 + 38 * 7,420,hund);

double s2=t2.ti_hund;

r2=t2.ti_hour;

r2=r2-r;

double time2=r2 * 3600 + t2.ti_min * 60 + t2.ti_sec + (s2 / 100);

time2=time2-time1;

itoa (time2,time,10);

if (s1>s2) s2=100 + s2-s1;

else s2=s2-s1;

itoa (s2,timer,10);

for (i=0;timer [i];i + + );

if (i==1) {

timer [1]=timer [0];

timer [0]='0';

timer [2]='\0';

}

outtextxy (300,440,»Vremia sortirovki:»);

outtextxy (300 + 21 * 7,440,time);

outtextxy (300 + 22 * 7,440,».»);

outtextxy (300 + 23 * 7,440,timer);

}

void puzir (int * & kop,int razmer,unsigned long int& iter) {

int temp,a;

iter=0;

for (int i=1;i<razmer;i + + ) { a=i;

while ((a) && (kop [a]<kop [a-1])) {

temp=kop [a-1];

kop [a-1]=kop [a];

kop [a]=temp;

a--;

iter + + ;

}

}

}

void vstavka (int * & kop,int razmer,unsigned long int& iter) {

int min,index,temp;

iter=0;

for (int k=0;k<razmer;k + + ){ min=kop [k]; index=k;

for (int i=k;i<razmer;i + + ) {

if (min>kop [i]) {

min=kop [i];

index=i;

iter + + ;

}

}

temp=kop [k];

kop [k]=kop [index];

kop [index]=temp;

}

}

void protalkivanie (int * & kop,int razmer,unsigned long int& iter) {

int temp;

iter=0;

for (int k=0;k<razmer-1;k + + ) {

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

if (kop [i]>kop [i + 1]) {

temp=kop [i];

kop [i]=kop [i + 1];

kop [i + 1]=temp;

iter + + ;

}

}

}

}

void Pirmidalina9 (int * & kop,int razmer,unsigned long int& iter) {

int temp,b,z,g;

iter=0;

for (long int i=razmer-1;i>=0;i--) {

kop [i]=random (razmer);

}

for (z=0;z<razmer;z + + ) { b=1; i=z;

while ((b) && (i>0)) { iter + + ;

if ((i%2==0) && (kop [i]>kop [i / 2-1])) {

temp=kop [i];

kop [i]=kop [i / 2-1];

kop [i / 2-1]=temp;

i=i / 2-1;

}

else if ((i%2==1) && (kop [i]>kop [i / 2])) {

temp=kop [i];

kop [i]=kop [i / 2];

kop [i / 2]=temp;

i=i / 2;

}

else b=0;

}

}

g=razmer;

while (g>0) {

temp=kop [0];

kop [0]=kop [g-1];

kop [g-1]=temp;

g--;

i=0; b=1;

while ((b) && (i * 2 + 1<g)) { iter + + ;

if ((kop [i]<kop [i * 2 + 1]) && (kop [i]>=kop [i * 2 + 2]) && (i * 2 + 1<g)) {

temp=kop [i];

kop [i]=kop [i * 2 + 1];

kop [i * 2 + 1]=temp;

i=i * 2 + 1;

}

else if ((kop [i]<kop [i * 2 + 2]) && (kop [i]>=kop [i * 2 + 1]) && (i * 2 + 2<g)){

temp=kop [i];

kop [i]=kop [i * 2 + 2];

kop [i * 2 + 2]=temp;

i=i * 2 + 2;

}

else if ((kop [i]<kop [i * 2 + 1]) && (kop [i]<kop [i * 2 + 2])) {

if ((kop [i * 2 + 1]<kop [i * 2 + 2]) && (i * 2 + 2<g)) {

temp=kop [i];

kop [i]=kop [i * 2 + 2];

kop [i * 2 + 2]=temp;

i=i * 2 + 2;

}

else {

temp=kop [i];

kop [i]=kop [i * 2 + 1];

kop [i * 2 + 1]=temp;

i=i * 2 + 1;

}

}

else b=0;

}

}

}

int massiv (int * & kop,int razmer,int metod) {

if (metod==1) {

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

kop [i]=random (razmer);

}

if (metod==2) {

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

kop [i]=i;

}

if (metod==3) {

for (int i=razmer-1;i>=0;i--)

kop [i]=razmer-i-1;

}

return 0;

}

Файл FILE.CPP

#include <iostream.h>

#include <stdio.h>

#include <conio.h>

int File (int * & kop,int k,int razmer) {

FILE * out;

if ((out = fopen («c:\\BORLANDC\\BIN\\1.txt», «w»)) == NULL) {

fprintf (stderr, «Cannot open output file.\n»);

return 1; }

if (k==1) {

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

fprintf (out, «%d «, kop [i] );

}

}

if (k==0) {

for (int i=razmer-1; i>=0; i--) {

fprintf (out, «%d «, kop [i] );

}

}

fclose (out);

return 0;

}

int File1 (int * & kop,int razmer) {

FILE * out;

if ((out = fopen («c:\\BORLANDC\\BIN\\2.txt», «w»)) == NULL) {

fprintf (stderr, «Cannot open output file.\n»);

return 1; }

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

fprintf (out, «%d «, kop [i] );

}

fclose (out);

return 0;

}

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