Пространства имен (поименованные области)
Мета роботи
Получити навички у створенні «пространства имен»
6.2 Вказівки щодо організації самостійної роботи студентів
Поименованные области служат для логического группирования объявлений и ограничения доступа к ним. Чем больше программа, тем более актуально использование поименованных областей. Простейшим примером применения является отделение кода, написанного одним человеком, от кода, написанного другим. При использовании единственной глобальной области видимости формировать программу из отдельных частей очень сложно из-за возможного совпадения и конфликта имен. Использование поименованных областей препятствует доступу к ненужным средствам.
Объявление поименованной области (ее также называют пространством имен) имеет формат:
namespace [ имя_области ]{ /* Обьявления */ }
Поименованная область может объявляться неоднократно, причем последующие объявления рассматриваются как расширения предыдущих. Таким образом, поименованная область может объявляться и изменяться за рамками одного файла.
Если имя области не задано, компилятор определяет его самостоятельно с помощью уникального идентификатора, различного для каждого модуля. Объявление объекта в неименованной области равнозначно его описанию как глобального с модификатором static. Помещать объявления в такую область полезно для того, чтобы сохранить локальность кода. Нельзя получить доступ из одного файла к элементу неименованной области другого файла.
Пример.
namespace demo{
int i = 1; int k = 0;
void fund (int);
void func2(int) { /* ... */ }
}
namespace demo{ // Расширение
// int i = 2; Неверно - двойное определение
void funcl(double); // Перегрузка
void func2(int); // Верно (повторное объявление)
}
В объявлении поименованной области могут присутствовать как объявления, так и определения. Логично помещать в нее только объявления, а определять их позднее с помощью имени области и оператора доступа к области видимости ::, например:
void demo::fund(int) { /* ... */ }
Это применяется для разделения интерфейса и реализации. Таким способом нельзя объявить новый элемент пространства имен.
Объекты, объявленные внутри области, являются видимыми с момента объявления. К ним можно явно обращаться с помощью имени области и оператора доступа к области видимости ::, например:
demo::i = 100; demo::func2(10);
Если имя часто используется вне своего пространства, можно объявить его доступным с помощью оператора using:
using demo::i: После этого можно использовать имя без явного указания области.
Если требуется сделать доступными все имена из какой-либо области, используется оператор using namespace:
using namespace demo:
Операторы usingи using namespaceможно использовать и внутри объявления поименованной области, чтобы сделать в ней доступными объявления из другой области:
namespace Department_of_Applied_Mathematics{ using demo::i; // ... }
Имена, объявленные в поименованной области явно или с помощью оператора using,имеют приоритет по отношению к именам, объявленным с помощью оператора usi ng namespace(это имеет значение при включении нескольких поименованных областей, содержащих совпадающие имена).
Короткие имена пространств имен могут войти в конфликт друг с другом, а длинные непрактичны при написании реального кода, поэтому допускается вводить синонимы имен:
namespace DAM = Department_of_Applied_Mathematics;
Пространства имен стандартной библиотеки.Объекты стандартной библиотеки определены в пространстве имен std.Например, объявления стандартных средств ввода/вывода С в заголовочном файле <stdio.h>помещены в пространство имен следующим образом:
// stdio.h namespace std{
int feof(FILE *f);
}
using namespace std;
Это обеспечивает совместимость сверху вниз. Для тех, кто не желает присутствия неявно доступных имен, определен новый заголовочный файл <cstdio>:
// cstdio
namespace std{
int feof(FILE *f);
}
Если в программу включен файл <cstdio>, нужно указывать имя пространства имен явным образом:
std::feof(f);
Механизм пространств имен вместе с директивой finclude обеспечивают необходимую при написании больших программ гибкость путем сочетания логического группирования связанных величин и ограничения доступа.
Как правило, в любом функционально законченном фрагменте программы можно выделить интерфейсную часть (например, заголовки функций, описания типов), необходимую для использования этого фрагмента, и часть реализации, то есть вспомогательные переменные, функции и другие средства, доступ к которым извне не требуется. Пространства имен позволяют скрыть детали реализации и, следовательно, упростить структуру программы и уменьшить количество потенциальных ошибок. Продуманное разбиение программы на модули, четкая спецификация интерфейсов и ограничение доступа позволяют организовать эффективную работу над проектом группы программистов.
// Пример передачи в функцию массива структур.
#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;
struct Tadres
{
char strace[80];
int numDom;
int numKv;
};
struct TStudent
{
char fio[80];
Tadres adres;
int pos;//номер в списке
};
void SetAdres(Tadres& adres)
{
cout<<"Vvedite name ulici"<<endl;
cin.getline(adres.strace,80);
cout<<"Vvedite nomer doma"<<endl;
char str[1000];
cin.getline(str,1000);
adres.numDom=atoi(str);
cout<<"Vvedite nomer kvartiri"<<endl;
cin.getline(str,1000);
adres.numKv=atoi(str);
};
void SetGrup(TStudent *Grup,int n)
{
for (int i(0);i<n;i++)
{
cout<<"Vvedite FIO "<<i<<" student:"<<endl;
cin.getline(Grup[i].fio,80);
SetAdres(Grup[i].adres);
Grup[i].pos=i;
}
};
void OutputStudent(TStudent *Grup,int n,int kol)
{
if(n>=kol)
{
cout<<"Student not found"<<endl;
return;
}
cout<<"FIO: "<<Grup[n].fio<<endl;
cout<<"Adres: "<<Grup[n].adres.strace<<" "<<Grup[n].adres.numDom<<" "<<Grup[n].adres.numKv<<endl;
};
int main()
{
int kolS;//количество студентов
char ch;
int num;
char str[1000];
cout<<"Vvedite kolichestvo studenta"<<endl;
cin.getline(str,1000);
kolS=atoi(str);
if (kolS<=0)return 1;
TStudent *BIKS = new TStudent [kolS];
SetGrup(BIKS,kolS);
do //печатать информацию о студенте по номеру
{
cout<<"Vvedite num studenta"<<endl;
char str[1000];
cin.getline(str,1000);
num=atoi(str);
OutputStudent(BIKS,num,kolS); //поиск студента
cout<<"Zakonchit' Y/N"<<endl;
ch=getch();
}while((ch!='y')&&(ch!='Y')&&(ch!='н')&&(ch!='Н'));
getch();
delete [] BIKS;
return 0;
}
Порядок виконання роботи
6.4 Контрольні запитання та завдання
Завдання
6.6 Варіанти завдань
Общие требования.
1. Необходимо каждый пункт задания оформить в виде функции. Все необходимые данные для функций должны передаваться им в качестве параметров. Использование глобальных переменных в функциях не допускается.
2. Все структуры и функции должны бить сгруппированы в поименованную область и сохранены в отдельном файле (*.h).
Вариант 1
Описать структуру с именем STUDENT, содержащую следующие поля: - фамилия и инициалы;
- номер группы;
- успеваемость (массив из пяти элементов). Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из десяти структур типа STUDENT; записи должны быть упорядочены по возрастанию номера группы;
- вывод на дисплей фамилий и номеров групп для всех студентов, включенных в массив, если средний балл студента больше 4.0;
- если таких студентов нет, вывести соответствующее сообщение.
Вариант 2
Описать структуру с именем STUDENT, содержащую следующие поля; - фамилия и инициалы;
- номер группы;
- успеваемость (массив из пяти элементов). Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из десяти структур типа STUDENT; записи должны быть упорядочены по возрастанию среднего балла;
- вывод на дисплей фамилий и номеров групп для всех студентов, имеющих оценки 4 и 5;
- если таких студентов нет, вывести соответствующее сообщение.
Вариант 3
Описать структуру с именем STUDENT, содержащую следующие поля:
- фамилия и инициалы; - номер группы;
- успеваемость (массив из пяти элементов). Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из десяти структур типа STUDENT; записи должны быть упорядочены по алфавиту;
- вывод на дисплей фамилий и номеров групп для всех студентов, имеющих хотя бы одну оценку 2;
- если таких студентов нет, вывести соответствующее сообщение.
Вариант 4
Описать структуру с именем AEROFLOT, содержащую следующие поля:
- название пункта назначения рейса;
- номер рейса;
- тип самолета.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из семи элементов типа AEROFLOT; записи должны быть упорядочены по возрастанию номера рейса;
- вывод на экран номеров рейсов и типов самолетов, вылетающих в пункт назначения, название которого совпало с названием, введенным с клавиатуры;
- если таких рейсов нет, выдать на дисплей соответствующее сообщение
Вариант 5
Описать структуру с именем AEROFLOT, содержащую следующие поля:
- название пункта назначения рейса;- номер рейса;
- тип самолета.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из семи элементов типа AEROFLOT; записи должны быть размещены в алфавитном порядке по названиям пунктов назначения;
- вывод на экран пунктов назначения и номеров рейсов, обслуживаемых самолетом, тип которого введен с клавиатуры;
- если таких рейсов нет, выдать на дисплей соответствующее сообщение.
Вариант 6
Описать структуру с именем WORKER, содержащую следующие поля:
- фамилия и инициалы работника;
- название занимаемой должности;
- год поступления на работу.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из десяти структур типа WORKER; записи должны быть размещены по алфавиту;
-вывод на дисплей фамилий работников, чей стаж работы в организации превышает значение, введенное с клавиатуры;
- если таких работников нет, вывести на дисплей соответствующее сообщение.
Вариант 7
Описать структуру с именем TRAIN, содержащую следующие поля:
- название пункта назначения;
- номер поезда;
- время отправления.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа TRAIN; записи должны быть размещены в алфавитном порядке по названиям пунктов назначения;
- вывод на экран информации о поездах, отправляющихся после введенного с клавиатуры времени;
- если таких поездов нет, выдать на дисплей соответствующее сообщение.
Вариант 8
Описать структуру с именем TRAIN, содержащую следующие поля:
- название пункта назначения;
- номер поезда;- время отправления.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из шести элементов типа TRAIN; записи должны быть упорядочены по времени отправления поезда;
- вывод на экран информации о поездах, направляющихся в пункт, название которого введено с клавиатуры;
- если таких поездов нет, выдать на дисплей соответствующее сообщение.
Вариант 9
Описать структуру с именем TRAIN, содержащую следующие поля:
- название пункта назначения;
- номер поезда;
- время отправления.
Написать программу, выполняющую следующие действия:
-ввод с клавиатуры данных в массив, состоящий из восьми элементов типа TRAIN; записи должны быть упорядочены по номерам поездов;
- вывод на экран информации о поезде, номер которого введен с клавиатуры;
- если таких поездов нет, выдать на дисплей соответствующее сообщение.
Вариант 10
Описать структуру с именем MARSH, содержащую следующие поля:
- название начального пункта маршрута;
- название конечного пункта маршрута;
- номер маршрута.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа MARSH; записи должны быть упорядочены по номерам маршрутов;
- вывод на экран информации о маршруте, номер которого введен с клавиатуры;
- если таких маршрутов нет, выдать на дисплей соответствующее сообщение.
Вариант 11
Описать структуру с именем MARSH, содержащую следующие поля:
- название начального пункта маршрута;
- название конечного пункта маршрута;
- номер маршрута.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа MARSH; записи должны быть упорядочены по номерам маршрутов;- вывод на экран информации о маршрутах, которые начинаются или оканчиваются в пункте, название которого введено с клавиатуры;
- если таких маршрутов нет, выдать на дисплей соответствующее сообщение.
Вариант 12
Описать структуру с именем NOTE, содержащую следующие поля:
- фамилия, имя;
- номер телефона;
- дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа NOTE; записи должны быть упорядочены по датам рождения;
- вывод на экран информации о человеке, номер телефона которого введен с клавиатуры;
- если такого нет, выдать на дисплей соответствующее сообщение.
Вариант 13
Описать структуру с именем NOTE, содержащую следующие поля:
- фамилия, имя;
- номер телефона;
- дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа NOTE; записи должны быть размещены по алфавиту;
- вывод на экран информации о людях, чьи дни рождения приходятся на месяц, значение которого введено с клавиатуры;
- если таких нет, выдать на дисплей соответствующее сообщение.
Вариант 14
Описать структуру с именем NOTE, содержащую следующие поля:
- фамилия, имя; - номер телефона;
- дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа NOTE; записи должны быть упорядочены по трем первым цифрам номера телефона;
- вывод на экран информации о человеке, чья фамилия введена с клавиатуры;
- если такого нет, выдать на дисплей соответствующее сообщение.
Вариант 15
Описать структуру с именем ZNAK, содержащую следующие поля:
- фамилия, имя;
- знак Зодиака;
- дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа ZNAK; записи должны быть упорядочены по датам рождения;
- вывод на экран информации о человеке, чья фамилия введена с клавиатуры;
- если такого нет, выдать на дисплей соответствующее сообщение.
Вариант 16
Описать структуру с именем ZNAK, содержащую следующие поля:
- фамилия, имя;
- знак Зодиака;
- дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа ZNAK; записи должны быть упорядочены по датам рождения;
- вывод на экран информации о людях, родившихся под знаком, название которого введено с клавиатуры!
- если таких нет, выдать на дисплей соответствующее сообщение.
Вариант 17
Описать структуру с именем ZNAK, содержащую следующие поля: - фамилия, имя;
- знак Зодиака;
- дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа ZNAK; записи должны быть упорядочены по знакам Зодиака;
- вывод на экран информации о людях, родившихся в месяц, значение которого введено с клавиатуры;
- если таких нет, выдать на дисплей соответствующее сообщение.
Вариант 18
Описать структуру с именем PRICE, содержащую следующие поля:
- название товара;- название магазина, в котором продается товар;
- стоимость товара в руб.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа PRICE; записи должны быть размещены в алфавитном порядке по названиям товаров;
- вывод на экран информации о товаре, название которого введено с клавиатуры;
- если таких товаров нет, выдать на дисплей соответствующее сообщение
Вариант 19
Описать структуру с именем PRICE, содержащую следующие поля:
- название товара;
- название магазина, в котором продается товар;
- стоимость товара в руб.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа PRICE; записи должны быть размещены в алфавитном порядке по названиям магазинов;
- вывод на экран информации о товарах, продающихся в магазине, название которого введено с клавиатуры;
- если такого магазина нет, выдать на дисплей соответствующее сообщение.
Вариант 20
Описать структуру с именем ORDER, содержащую следующие поля:
- расчетный счет плательщика; - расчетный счет получателя;
- перечисляемая сумма в руб.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа ORDER; записи должны быть размещены в алфавитном порядке по расчетным счетам плательщиков;
- вывод на экран информации о сумме, снятой с расчетного счета плательщика, введенного с клавиатуры;
- если такого расчетного счета нет, выдать на дисплей соответствующее сообщение.
Вариант 21
Описать структуру с именем STUDENT, содержащую следующие поля; - фамилия и инициалы;
- номер группы;
- успеваемость (массив из пяти элементов). Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из десяти структур типа STUDENT; записи должны быть упорядочены по возрастанию среднего балла;
- вывод на дисплей фамилий и номеров групп для всех студентов, у которых успеваемость выше среднего;
Вариант 22
Описать структуру с именем STUDENT, содержащую следующие поля; - фамилия и инициалы;
- номер группы;
- успеваемость (массив из пяти элементов). Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из десяти структур типа STUDENT; записи должны быть упорядочены по возрастанию среднего балла;
- вывод на дисплей фамилий и номеров групп для всех студентов, у которых успеваемость выше 2.0 бала и ниже 4.5.
Вариант 23
Описать структуру с именем PRICE, содержащую следующие поля:
- название товара;
- название магазина, в котором продается товар;
- стоимость товара в руб.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа PRICE;
- вывод на экран перечень магазинов, в которых есть в наличии товаре, название которого введено с клавиатуры;
- если таких товаров нет, выдать на дисплей соответствующее сообщение
Вариант 24
Описать структуру с именем PRICE, содержащую следующие поля:
- название товара;
- название магазина, в котором продается товар;
- стоимость товара в руб.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа PRICE;
- вывод на список товаров, в которые есть в наличии в указанном магазине;
- если такого магазина нет, выдать на дисплей соответствующее сообщение
Вариант 25
Описать структуру с именем COMP, содержащую следующие поля:
- название компьютера;
- рейтинговая частота процессора;
- количество ОЗУ.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа COMP;
- вывод на экран список компьютеров у которых мощность процессора выше среднего;
Вариант 25
Описать структуру с именем COMP, содержащую следующие поля:
- название компьютера;
- рейтинговая частота процессора;
- количество ОЗУ.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа COMP;
- вывод на экран список компьютеров у которых количество памяти больше 64Мб и меньше 1024Мб.
Вариант 26
Описать структуру с именем COMP, содержащую следующие поля:
- название компьютера;
- рейтинговая частота процессора;
- количество ОЗУ.
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа COMP;
- вывод на экран список компьютеров у которых количество памяти больше 128Мб и частота процессора больше 1000Гц.
Контрольний приклад
Описать структуру с именем STUDENT, содержащую следующие поля:
- фамилия и инициалы;
- средний бал успеваемости;
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры;
- вывод полного списка на экран;
- поиск студента с наихудшей успеваемостью.
Пример решения:
Текст файла main.cpp
#include"student.h"
using namespace grup;
int main()
{
int n;
cout<<"Vvedite kolichestvo studentov=";
char kolTMP[10]; //
cin.getline(kolTMP,10); //Делаем защиту от
n=atoi(kolTMP); //ошибочного ввода
if(!n) return 1;
Stud *PMM=new Stud[n];
input(PMM,n);
output(PMM,n);
Stud *StudMin=serchMin(PMM,n);
cout<<"Student s minim balom:"<<endl;
cout<<StudMin->FIO<<'\t'<<StudMin->bal<<endl;
cin.get();
delete []PMM;
return 0;
}
Текст файла student.h
#include<iostream>
using namespace std;
namespace grup
{
struct Stud
{
char FIO[80];
float bal;
};
void input(Stud *IB,int n);
//Функция для ввода с клавиатуры
void output(Stud *IB,int n);
//Функция для вывода на экран
Stud *serchMin(Stud *IB,int n);
//Функция для нахождения студента с минимальным бaлом
}// конец namespace grup
void grup::input(Stud *IB,int n)
//Функция для ввода с клавиатуры
{
for(int i=0;i<n;i++)
{
cout<<"Vvedite imja Studenta "<<endl;
cin.getline(IB[i].FIO,80);
char strTMP[10];
cout<<"Vvedite bal Studenta "<<endl;
cin.getline(strTMP,80);
IB[i].bal=atoi(strTMP);
}
};
void grup::output(Stud *IB,int n)
//Функция для вывода на экран
{
for(int i=0;i<n;i++)
{
cout<<IB[i].FIO<<'\t'<<IB[i].bal<<endl;
}
};
grup::Stud *grup::serchMin(Stud *IB,int n)
//Функция для нахождения студента с минимальным бaлом
{
Stud *Min;
Min=&IB[0];
for(int i=1;i<n;i++)
if(Min->bal>IB[i].bal)
Min=&IB[i];
return Min;
};
7 Пошук і сортування
Мета роботи
Отримати практичні навички програмування на С++задач, де використовується пошук і сортування інформації.
7.2 Методичні вказівки до організації самостійної роботи студентів
Одна з дій, що найбільш часто зустрічається в програмуванні — пошук. Існує кілька основних способів пошуку і для них створено багато різних алгоритмів. При виконанні роботи варто виходити з допущення, що група даних, у якій необхідно відшукати заданий елемент, фіксована.
Сортування — це задача розташування довільних об'єктів у порядку (не-) зменшення чи (не-)зростання деякої ознаки. Існує велика кількість методів сортування, що відрізняються друг від друга як тимчасовою складністю, так і універсальністю.
7.2.1 Лінійний пошук
Якщо немає ніякої додаткової інформації про розшукувані дані, то очевидний підхід — простий послідовний перегляд масиву зі збільшенням крок за кроком тієї його частини, де бажаного елемента не виявлено.Умови закінчення пошуку: елемент знайдено чи весь масив переглянуто і збігу не виявлено.
7.2.2 Пошук розподілом навпіл (двійковий пошук)
Пошук може бути більш ефективним, якщо дані будуть упорядковані. Основна ідея – вибрати випадково деякий елемент аm і порівняти його з аргументом пошуку х. Якщо він дорівнює х, то пошук закінчується, якщо він менше х, то всі елементи з індексами, меншими чи рівними m, можна виключити з подальшого пошуку; якщо ж він більше х, то виключаються індекси, більші чи рівні m.
Сортування вставками
Нехай потрібно упорядкувати масив 
за зростанням пропонується використовувати наступний підхід: для 
, кожен елемент 
будемо вставляти в потрібне місце серед упорядкованих раніше елементів 
, розсовуючи їх за рахунок видалення . Цей метод у явному виді рідко використовується на практиці, однак покладена в його основу ідея добре працює, коли потрібно вставити новий елемент у вже упорядкований масив.
Метод пухирця
Ідея методу полягає в упорядкуванні всіх пар сусідніх елементів. Масив проглядається зліва направо і, якщо xi > xi+1 (i=1…n-1), то вони міняються місцями. При цьому i-й елемент (крім першого й останнього) бере участь у двох порівняннях, а це значить, що максимальний елемент масиву буде переміщатися («спливати») до правого кінця масиву і до кінця проходу виявиться останнім. За наступний прохід «спливе» другий по величині елемент і т.д., поки всі елементи не займуть свої місця. Очевидно, для цього буде потрібно не більш n-1 проходів.
Сортування перерахуванням
Для кожного елемента масиву X(n) вважаємо, скільки елементів менше його, тобто фактично знаходимо його положення в упорядкованому масиві. Для збереження цієї інформації можна використовувати масив лічильників C(n). Тоді значення Сi+1 визначає положення елемента xi у результуючому відсортованому масиві R(n).
Швидке сортування
Цей алгоритм одержав широке поширення в багатьох прикладних програмах. Однак ефективність його використання істотно залежить від числа елементів сортуемого масиву, а також характеру розподілу цих даних. Отже:
— вибирається який–небудь елемент (x) (звичайно знаходиться в середині послідовності). Будемо переглядати масив ліворуч доти, поки не знайдемо елемент аi>x, потім будемо переглядати масив праворуч, поки не зустрінеться аj<x. Тепер поміняємо місцями ці два елементи і продовжимо наш процес перегляду й обміну, поки обидва перегляди не зустрінуться десь у середині масиву (значення i та j рівні). У результаті виявиться, що масив розбито на дві половини із ключами, меншими або рівними x, і більшими або рівними x, а сам елемент x буде знаходитися в необхідному місці; 
— ітераційно повторюємо процес 1 для кожної з отриманих половин (у перший раз одержимо чотири піддіапазону вихідної послідовності) доти, поки значення індексів для кожного вкладеного діапазону чи будуть рівні, чи змінять відношення. У результаті ми одержимо упорядковану послідовність.
Сортування злиттям
Це алгоритм об'єднання двох відсортованих масивів в один. Розглянемо два відсортованих по неубуванню масиву X(n) і Y(m). Нехай необхідно об'єднати їх в один масив Z(n+m), також упорядкований. Вирішимо цю задачу в такий спосіб: з кожної пари мінімальних елементів масивів X і Y (починаючи з x1 і y1) вибираємо найменший і записуємо його в Z, а в масиві, з якого був узятий цей елемент, збільшуємо на одиницю індекс наступного, ще не розглянутого елемента. Так продовжуємо, поки один з масивів не вичерпається. Якщо першим вичерпався масив X, то залишок Y цілком переписуємо в Z, якщо першим вичерпався Y, то в Z переписуємо залишок X .
Приклад 7Реалізація методу “швидкого” сортування
#include<iostream.h>
#include<stdio.h>
#define b=16
int n=6;
int a[6];
int i,j,l,r=6;
void swap(int*,int*);
Void quicksort(int,int);
void part(int,int,int&,int&);
Int main()
{ for(int k=1;k<=n; k++)
{cout << "input а["<<k<<"] of massive \n";
cin >> a[k]; }
quicksort(1,n);// вызов функции быстрой сортировки
for(k=1; k<=n; k++)
{printf("a[ %d ]= %d \n",k,a[k]);}
cin>>k;
Return 0;
}
void swap(int* p,int* q)
{ int prom;
prom=*p;
*p=*q;
*q=prom; }
void quicksort(int l,int r) //функция быстрой сортировки
{ int i,j; i=l; j=r;
{ part(l,r, i, j);
if(i<r) quicksort(i,r); //переход к сортировке слева
if(j>l) quicksort(l,j); } // переход к сортировке справа
}
void part(int l,int r,int &i,int &j)
{ int x ; i=l; j=r; x=(l+r)/2;
do { while (a[i]<a[x]) i++; //просмотр: найдёмa[j]> a[x]
while(a[j]>a[x]) j--; //просмотр: найдём a[j]< a[x], меняем местами
if(i<=j)
{ swap(&a[i],&a[j]); //обмен этих элементов
i++;j--; }
} while(i<j); }
7.3 Контрольні запитання
1. Як змінити алгоритм пошуку найбільшого з уведених чисел, щоб він знаходив найменше число ?
2. Запропонуйте алгоритм не двоїчного, а троїчного пошуку.
3. Що потрібно змінити в алгоритмі обмінного сортування, щоб першими займали свої місця не великі числа, а маленькі ?
4. Поліпшите алгоритм обмінного сортування так, щоб робота припинялася, якщо проходження масиву не викликало жодного обміну.
5. Розробіть алгоритм злиття масивів a і b з упорядкованими ділянками довжини d.
6. Розробіть алгоритм злиття двох масивів з упорядкованими ділянками довільної довжини. Як визначити кінець упорядкованої ділянки?
7. Чи зміниться складність алгоритму злиття, якщо зливати не по два, а по три масива?
Варіанти індивідуальних завдань
Реалізуйте на практиці 2 алгоритми пошуку та 2 алгоритми сортування. Результати порівняйте.
Перелік посилань
1. Керниган Б., Ритчи Д. Язык программирования Си: Пер. с англ. — М.: Финансы и статистика, 1992. — 272 с.
2. Страуструп Б. Язык программирования С++. Часть 1. — Киев: "ДиаСофт", 1993. — 264 с.
3. Страуструп Б. Язык программирования С++. Часть 2. — Киев: "ДиаСофт", 1993. — 296 с.
4. Подбельский В.В. Язык Си+: Учеб. пособие. — М.: БИНОМ, 1995. — 400 с.
5. Глушаков С.В. и др. Язык программирования С++. —Харьков: Фолио, 2002. — 500 с.
6. Х.М.Дейтел, П.Дж. Дейтел Как программировать на С++.- М.:ЗАО «Издательство БИНОМ», 2000 г. — 1024 с.
7. Ван Тассел Д. Стиль, разработка, отладка и испытание программ.-M.:Мир,1985.
8. Проценко В.С. Техніка програмування мовою С. —Навч. Посібник. –К.:Либідь, 1993. — 224с.
9. Жешке Р. Толковый словарь стандарта языка Си: — С.-Петербург: Питер, 1994. — 221с.
10. Язык Си. Книга ответов: Пер. с англ. — М.: Финансы и статистика, 1994. — 160 с.