2015-09-06
241
Алгоритм сортировки выбором состоит из трех шагов:
1. Находится номер минимального значения в текущем списке.
2. Производится обмен этого значения со значением первой, не отсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции).
3. Сортируется «хвост» списка, исключив из рассмотрения уже отсортированные элементы.
Для реализации устойчивости алгоритма необходимо на шаге 2 минимальный элемент непосредственно вставлять в первую, не отсортированную позицию, не меняя порядок остальных элементов.
Листинг 5.3. Задан список студентов с указанием фамилии и номера группы (рис. 5.3). Упорядочить этот список по возрастанию номера группы, а внутри группы построить его в алфавитном порядке.
//L5_3.cpp
#include <string.h>
#include <iostream>
using namespace std;
int main()
{
setlocale(LC_CTYPE,"russian");
int n, i, j, *grup, jmax, gm;
char **name, fam[30], *fm;
fstream ff("input.txt");
ff>>n;
name=new char*[n ]; // Выделение памяти для указателей, связанных
//с фамилией студентов.
grup=new int[n]; // Выделение памяти под номера групп
|
|
|
for(i=0;i<n;i++)
{
ff>>fam>>grup[i];
name[i]=strdup(fam); // Заполняется фамилия i-го студента
}
ff.close();
for(i=0;i<n-1;i++)
{
fm=name[i];
gm=grup[i];
jmax=i;
for(j=i+1;j<n;j++)
if(grup[j]<gm ||(grup[j]==gm && strcmp(name[j],fm)<0))
{
fm=name[j];
gm=grup[j];
jmax=j;
}
name[jmax]=name[i];
name[i]=fm;
grup[jmax]=grup[i];
grup[i]=gm;
}
cout<<"Полученный список\n";
for(i=0;i<n;i++)
{
cout.width(6); // Выделение поля для вывода группы
cout<<grup[i]<<" ";
cout<<name[i]<<'\n';
}
ff.open("input.txt", ios::app);
ff<<"\nПолученный список\n";
for(i=0;i<n;i++)
{
ff.width(6);
ff<<grup[i]<<" ";
ff<<name[i]<<'\n';
}
ff.close();
cin.get();
return 0;
}
Содержимое файла “input.txt”
Рис. 5.3. Информация, находящаяся в файле «input.txt»
Результат работы программы листинга 5.3 приведен на рис. 5.4:
Рис. 5.4. Результат работы программы листинга 5.3
