Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
31.
Библиотечная функция qsort()
#include<cstdlib>
void qsort(void *buf,size_t num,size_t size,int (*compare)(const void*,const void *));
Функция qsort() упорядочивает массив buf с помощью алгоритма быстрой сортировки. После выполнения функции массив оказывается упорядоченным. Количество элементов массива задается параметром num, а размер каждого элемента (в байтах) задается параметром size.
Для сравнения элементов массива используется функция compare. Объявление функции compare() должно выглядеть следующим образом:
int func_name(const void *arg1,const void *arg2);
Она должна возвращать значения, описанные в следующей таблице.
|
Сравнение |
Возвращаемое значение |
|
arg1 меньше arg2 |
Меньше нуля |
|
arg1 равно arg2 |
Нуль |
|
arg1 больше arg2 |
Больше нуля |
Аргументы, передаваемые функции compare, определены как void*, то есть внутри функции они должны приводиться к нужному типу.
Массив сортируется в порядке возрастания.
Рассмотрим пример 1 программы, в которой используется библиотечная функция qsort() для сортировки массивов различных типов данных и по различных критериям.
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
//Класс студент
class student{
char name[20]; // фамилия студента
int num; //номер зачетной книжки
public:
//конструктор без параметров
student(){}
//конструктор с параметрами
student(char *fam,int nm){
strcpy(name,fam);
num=nm;}
const char* getname()
{ return name;}
int getnum()
{ return num;}
//перегруженные функции извлечения
// и помещения в поток
friend ostream& operator<<(ostream &stream,student ob);
friend istream& operator>>(istream &stream,student &ob);
};
ostream& operator<<(ostream &stream,student ob)
{ stream<<ob.name<<"\t";
stream<<ob.num<<"\n";
return stream;}
istream& operator>>(istream &stream,student &ob)
{ stream>>ob.name;
stream>>ob.num;
return stream;}
//критерий сортировки: по убыванию (для типа int)
int comp1(const void* arg1,const void* arg2)
{ int *a1=(int*)arg1;
int *a2=(int*)arg2;
if(*a1>*a2) return -1;
if(*a1==*a2) return 0;
return 1;
}
//критерий сортировки: по возрастанию абсолютного значения
//(для типа double)
int comp2(const void* arg1,const void* arg2)
{ double *a1=(double*)arg1;
double *a2=(double*)arg2;
if(fabs(*a1)<fabs(*a2)) return -1;
if(fabs(*a1)==fabs(*a2)) return 0;
return 1;
}
//критерий сортировки: по возрастанию номеров зачеток
//(для типа student)
int comp3(const void* arg1,const void* arg2)
{ student *a1=(student*)arg1;
student *a2=(student*)arg2;
if((*a1).getnum()<(*a2).getnum()) return -1;
if((*a1).getnum()==(*a2).getnum()) return 0;
return 1;
}
//критерий сортировки: в алфавитном порядке
//по фамилиям (для типа student)
int comp4(const void* arg1,const void* arg2)
{ student *a1=(student*)arg1;
student *a2=(student*)arg2;
if(strcmp((*a1).getname(),(*a2).getname())<0) return -1;
if(strcmp((*a1).getname(),(*a2).getname())==0) return 0;
return 1;
}
int main()
{
int a[10]={2,3,4,1,10,9,8,7,-1,20};
double b[5]={-2.5,1.8,10.2,5.4,3.8};
student group[5];
//Сортируем по убыванию элементы массива a
qsort(a,10,sizeof(int),comp1);
cout<<"Array a after sort:\n";
for(int i=0;i<10;++i)
cout<<a[i]<<'\t';
cout<<endl;
//Сортируем по возрастанию абсолютного значения
// элементы массива b
qsort(b,5,sizeof(double),comp2);
cout<<"Array b after sort:\n";
for(int i=0;i<5;++i)
cout<<b[i]<<'\t';
cout<<endl;
//заполняем массив group с помощью ввода с клавиатуры
cout<<"Vvod information about 5 students:\n";
for(int i=0;i<5;++i)
cin>>group[i];
cout<<endl;
cout<<"Array group:\n";
for(int i=0;i<5;++i)
cout<<group[i];
cout<<endl;
//Cортируем по возрастанию номеров зачеток
//элементы массива group
qsort(group,5,sizeof(student),comp3);
cout<<"Array group after sort (num):\n";
for(int i=0;i<5;++i)
cout<<group[i];
cout<<endl;
//Сортируем элементы массива group
//по фамилиям в алфавитном порядке
qsort(group,5,sizeof(student),comp4);
cout<<"Array group after sort (name):\n";
for(int i=0;i<5;++i)
cout<<group[i];
cout<<endl;
return 0;}
Алгоритм sort из STL
Прототипы:
template<typename RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<typename RandomAccessIterator,typename Compare>
void sort(RandomAccessIterator first,RandomAccessIterator last,Compare comp);
Алгоритм sort сортирует элементы в диапазоне [first;last).
В первой версии алгоритма sort сортировка осуществляется в возрастающем порядке. Во второй версии алгоритма sort в качестве третьего параметра используется функциональный объект, задающий критерий сортировки. В качестве него может выступать функция, предопределенный функциональный объект или объект функционального класса.
Алгоритм sort реализован версией алгоритма быстрой сортировки. Он не является устойчивым.
Алгоритм sort сортирует последовательность длиной N при помощи O(NlogN) сравнений и присваиваний в среднем. Однако имеется небольшое количество входных последовательностей, которые требуют квадратичного времени работы алгоритма.
Рассмотрим пример 2 программы на использование обобщенного алгоритма sort из стандартной библиотеки шаблонов (STL).
#include<iostream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<cstdlib>
using namespace std;
//Класс студент
class student{
char name[20]; // фамилия студента
int num; //номер зачетной книжки
public:
//конструктор без параметров
student(){}
//конструктор с параметрами
student(char *fam,int nm){
strcpy(name,fam);
num=nm;}
const char* getname()
{ return name;}
int getnum()
{ return num;}
//перегруженные функции извлечения
// и помещения в поток
friend ostream& operator<<(ostream &stream,student ob);
friend istream& operator>>(istream &stream,student &ob);
//перегруженная операция <
friend bool operator<(const student& o1,const student& o2);
};
ostream& operator<<(ostream &stream,student ob)
{ stream<<ob.name<<"\t";
stream<<ob.num<<"\n";
return stream;}
istream& operator>>(istream &stream,student &ob)
{ stream>>ob.name;
stream>>ob.num;
return stream;}
bool operator<(const student&o1,const student&o2)
{ if(o1.num>o2.num) return true;
return false;}
//функциональный класс с перегруженной операцией ()
//для типа int и типа student
class comp
{
public:
bool operator()(int x,int y)
{return x%10<y%10;}
bool operator()(student a,student b)
{if(strcmp(a.getname(),b.getname())<0) return true;
return false;
}
};
int main()
{const int n=20;
int mas[n];
student group[5];
//сортируем массив типа int
//по возрастанию остатка от деления на 10
for(int i=0;i<n;++i)
mas[i]=i;
cout<<"Before sort():\n";
for(int i=0;i<n;++i)
cout<<mas[i]<<" ";
cout<<endl;
//используем вторую версию алгоритма sort
//в качестве критерия сортировки использован
// объект функционального класса
sort(mas,mas+n,comp());
cout<<"After sort():\n";
for(int i=0;i<n;++i)
cout<<mas[i]<<" ";
cout<<endl;
//сортируем по убыванию массив типа double
double mas1[n];
cout<<"Before sort():\n";
for(int i=0;i<n;i++)
{mas1[i]=1000*(double)rand()/RAND_MAX-500;
cout<<mas1[i]<<'\t';}
cout<<endl;
//используем вторую версию алгоритма sort
//в качестве критерия сортировки использован
//предопределенный функциональный объект
sort(mas1,mas1+n,greater<double>());
cout<<"After sort():\n";
for(int i=0;i<n;i++)
cout<<mas1[i]<<'\t';
cout<<endl;
//заполняем массив group с помощью ввода с клавиатуры
cout<<"Vvod information about 5 students:\n";
for(int i=0;i<5;++i)
cin>>group[i];
cout<<endl;
cout<<"Array group:\n";
for(int i=0;i<5;++i)
cout<<group[i];
cout<<endl;
//Cортируем по убыванию номеров зачеток
//элементы массива group
//используем первую версию алгоритма sort
//«срабатывает» перегруженный классе student оператор<
sort(group,group+5);
cout<<"Array group after sort (num):\n";
for(int i=0;i<5;++i)
cout<<group[i];
cout<<endl;
//Сортируем элементы массива group
//по фамилиям в алфавитном порядке
//используем вторую версию алгоритма sort
//в качестве критерия сортировки использован
//объект функционального класса
sort(group,group+5,comp());
cout<<"Array group after sort (name):\n";
for(int i=0;i<5;++i)
cout<<group[i];
cout<<endl;
return 0;}