Сортировка

// search.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <windows.h>
#include <stdio.h>
#include <math.h>
using namespace std;
struct sadov
{char name[35];
int stag;
char zvanie[35];
}base[15];
int n = 15;
sadov sad[15];
char temp[25];
int count = 0;
int p = 0;
//==============================
void open_file()
{
FILE *f;
f=fopen("tabl.txt","r");
if(f==NULL)
{
printf("Fajl s dannimi povrezhden libo otsytstvyet\n");
}
for (int i = 0; i<n; i++)
{
fscanf(f,"%s",sad[i].name);
fscanf(f,"%s",temp);
sad[i].stag=atoi(temp);
fscanf(f,"%s",sad[i].zvanie);
}}
void vvod()
{
for (int i=0; i<n; i++)
{cout<<i<< ". Vvedite FIO: "<<endl;
cin>>sad[i].name;
do
{cout<<i<<". Vvedite u4enoe zvanie: "<<endl;
cin>> temp;
sad[i].stag = atoi (temp);
if (sad[i].stag<=0)
{cout<<"Znachenie ne mozhet bit menshe nylya.Povtorite vvod"<<endl;
}
}while (sad[i].stag<=0);
cout<<i<<". vvedite stag raboti: "<<endl;
cin>> sad[i].zvanie;
}
} void vuvod_tabl()
{cout<<"Tablica: "<<endl;
for(int i=0; i<n; i++)
{cout<<"FIO : "<<sad[i].name<<"\t u4enoe zvanie: "<<sad[i].stag<<"\t stag raboti: "<<sad[i].zvanie<<endl;
}
system("pause");
}
void line_search(int stag){
int kol=0;
int min=abs(stag-base[0].stag);
cout<<"stag\tzvanie\tname\n";
for(int i=1;i<15;i++){
kol++;
if(min>abs(stag-base[i].stag))
min=abs(stag-base[i].stag);
}
for(int i=0;i<15;i++)
if(min==abs(stag-base[i].stag)){
cout<<base[i].stag<<'\t';
cout<<base[i].zvanie<<'\t';
cout<<base[i].name<<"\t\n";
}
cout<<"\nKol-vo sravneniy="<<kol<<'\n';
system("PAUSE");
}void bin_search(int stag){
int head,tail,mid,min,kol=0;
head=0;
tail=14;
while(head<tail){
kol++;
mid=(head+tail)/2+1;
min=abs(stag-base[mid].stag);
if(stag>base[mid].stag)
head=mid+1;
else tail=mid-1;
} if(head==0){
min=abs(stag-base[head].stag);
cout<<"stag\tzvanie\tname\n";
while(min==abs(stag-base[head].stag)){
cout<<base[head].stag<<'\t';
cout<<base[head].zvanie<<'\t';
cout<<base[head].name<<"\t\n";
head++;
} system("PAUSE");
return;
}
while(min==abs(stag-base[head-1].stag)){
head--;
}
cout<<"stag\tzvanie\tname\n";
while(min==abs(stag-base[head].stag)){
cout<<base[head].stag<<'\t';
cout<<base[head].zvanie<<'\t';
cout<<base[head].name<<"\t\n";
head++;
}
cout<<"\nKol-vo sravneniy="<<kol<<'\n';
system("PAUSE");
}void KV_VIBORKA()
{
count = p = 0;
float n = 15.0;
int k,bi=0,min_i,i,j,ck,min,del_i=-1;
bool fl = false;
sadov sort[15];
int min_arr[100];
k=sqrt(n);
while(bi < n)
{ if(del_i!=-1)
{
i=del_i*k;
} else
{ i=0;
min_i=0;}
while(i < n)
{
j=i ;
min=j ;
while(j<(i+k)&&(j<n))
{
if(fl)
{count++;
if((sad[j].stag>ck)&&((sad[min].stag==ck)||(sad[j].stag < sad[min].stag)))
{ min=j;
}
}//if
else
{ count++;
if(sad[j].stag < sad[min].stag)
{ min=j;
}
}//else
j=j+1;
}//3w
if(del_i!=-1)
{min_arr[del_i]=min;
i = n;}
else
{ min_arr[min_i]=min;
min_i++;}
i+=k; }//2w
min=min_arr[0];
for(i=0;i<min_i;i++)
{
//if(th[min_arr[i]].seasn<=th[min].seasn)
if(fl)
{ count++;
if((sad[min_arr[i]].stag>ck) && ((sad[min].stag==ck)||(sad[min_arr[i]].stag<=sad[min].stag)) )
{del_i=i;
min=min_arr[i];}}
else
{count++;
if(sad[min_arr[i]].stag<=sad[min].stag)
{ del_i=i;
min=min_arr[i];}
} }//for
strcpy(sort[bi].name,sad[min].name);
sort[bi].stag = sad[min].stag;
strcpy(sort[bi].zvanie, sad[min].zvanie);
p++;
if(!fl)
{ck=sort[bi].stag-1;
fl=true;
}sad[min].stag=ck;
bi=bi+1;
}//1w
for(i=0;i<n;i++)
{strcpy(sad[i].name,sort[i].name);
sad[i].stag = sort[i].stag;
strcpy(sad[i].zvanie, sort[i].zvanie);
p++; }
cout<<"kol-vo sravnenij : "<<count<<endl;
cout<<"kol-vo perestanovok : "<<p<<endl;
}//KV_VIBORKA
void menu ()
{system("cls");
cout<<"1. vvod vrychnyu."<<endl<<endl;
cout<<"2. vvod iz fajla."<<endl<<endl;
cout<<"3. vixod."<<endl;
int c;
cin>>temp;
c = atoi(temp);
switch(c)
{case 1:
{ system("cls");
cout<<"bil vibran rychnoj vvod."<<endl<<endl;
cout<<"vvesti dannie: "<<endl;
vvod();
vuvod_tabl();
int y;
cout<<"\nDlya linejnogo poiska 1."<<endl;
cout<<"dlya dvoichnogo 2."<<endl;
cout<<"dlya sortirovki kvadratichnoj viborki 3."<<endl;
cout<<"dlya vixoda v glavnoe menu 6."<<endl;
cin>>temp;
y = atoi(temp);
switch(y)
{
case 1:
{system("cls");
cout<<"bil vibran linejnij poisk."<<endl;
line_search();
system("pause");
menu();
break;
}//case 1
case 3:
{system("cls");
KV_VIBORKA();
vuvod_tabl();
menu();
break;
}case 6:
{system("cls");
menu();
break;}
default:
{system("cls");
cout<<"nepravilnij vvod."<<endl;
system("pause");
menu();
break;
}//default
}// switch(y)
break; }//case 1
case 2:
{system("cls");
cout<<"vvod iz fajla."<<endl;
open_file();
cout<<"\nDlya linejnogo poiska nazhmite 1."<<endl;
cout<<"Dlya dvoichnogo poiska nazhmite 2."<<endl;
cout<<"Dlya vivoda tablici 3."<<endl;
cout<<"dlya sortirovki kvadratichnoj viborki 4."<<endl;
cout<<"dlya vixoda v glavnoe menu 7."<<endl;
int y;
cin>>temp;
y = atoi(temp);
switch(y)
{case 1:
{system("cls");
cout<<"bil vibran linejnij poisk."<<endl;
line_search();
system("pause");
menu();
break;}//case 1
case 2:
{system("cls");
cout<<"bil vibran dvoichnij poisk."<<endl;
cout<<"neobxodimo otsortirovat."<<endl;
vuvod_tabl();
bin_search();
system("pause");
menu();
break;
}//case 2
case 3:
{system("cls");
vuvod_tabl();
menu();
break;}
case 4:
{system("cls");
KV_VIBORKA();
vuvod_tabl();
menu();
break;}
case 7:
{ system("cls");
menu();
break;}
default:
{system("cls");
cout<<"nepravilnij vvod."<<endl;
system("pause");
menu();
break;
}//default}//switch (y)
break;}//case2
case 3:
{break;}
default:
{system("cls");
cout<<"nepravilnij vvod."<<endl;
system("pause");
menu();
break;
}
}//switch(c)
}void main (void){
menu();}