#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef struct STUDENT
{
char name[50];
int StudentID;
float GPA;
}Student;
void Nhap(Student dssv[], int i)
{
fflush(stdin);
cout << "Nhap ten sinh vien: ";
gets_s(dssv[i].name);
fflush(stdin);
cout << "Ma so sinh vien: ";
cin >>dssv[i].StudentID;
fflush(stdin);
cout << "Diem trung binh: ";
cin >> dssv[i].GPA;
}
void Xuat(Student dssv[], int i)
{
cout << "Ten Sinh Vien:";
puts(dssv[i].name);
cout << "Ma so sinh vien:" << dssv[i].StudentID << endl;
cout << "Diem trung binh: " << dssv[i].GPA << endl;
}
int Linearsearch(Student dssv[], int n, char *x)
{
int i = 0;
while ((i < n) && (dssv[i].name != x))
i++;
if (i == n)
return 0;
else
return 1;
}
int Binarysearch(Student dssv[], int n, int m)
{
int left,right, mid;
left = 0;
right = n - 1;
do
{
mid = (left + right) / 2;
if (dssv[mid].StudentID == m)
return 1;
else
if (dssv[mid].StudentID < m)
left = mid + 1;
else
right = mid - 1;
} while (left <= right);
return 0;
}
void hoanvi(Student &a, Student &b)
{
Student temp = a;
a = b;
b = temp;
}
void ShakeSort(Student dssv[], int n)
{
int j;
int left=0, right=n-1, k=0;
while (left < right)
{
for (j = right; j > left ; j--)
{
if (dssv[j].GPA > dssv[j - 1].GPA)
{
hoanvi(dssv[j], dssv[j - 1]);
k = j;
}

}
left = k;

for (j = left; j < right; j++)
{
if (dssv[j].GPA < dssv[j + 1].GPA)
{
hoanvi(dssv[j], dssv[j + 1]);
k = j;
}

}
right = k;
}

}
int main()
{
Student dssv[100];
int n,i,m;
char x[50];

cout << " So sinh vien can nhap vao:";
cin >> n;
for (i = 0; i < n; i++)
{
cout << "Sinh vien thu " << i+1 << endl;
Nhap(dssv, i);
cout << endl;
}

fflush(stdin);
cout << "Ten sinh vien can tim: ";
gets_s(x);
if (Linearsearch(dssv, n, x) == 0)
cout << "Khong Tim Thay" << endl;
else
Xuat(dssv, i);

fflush(stdin);
cout << "Nhap MSSV can tim:";
cin >> m;
if (Binarysearch(dssv, n, m) == 1)
Xuat(dssv, i);
else
cout << "Khong Tim Thay" << endl;

ShakeSort(dssv, n);
for (i = 0; i < n; i++)
{
Xuat(dssv, i);
cout << endl;
}
system("pause");
return 0;
}