3.3. Сортировка с помощью разделения
При улучшении пузырьковой сортировки, являющейся самой неэффективной из всех трех алгоритмов простой сортировки, был получен один из самых лучших метод сортировки для массивов. Этот метод называется быстрой сортировкой (Quicksort). В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных на ключах в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Но из этого примера можно извлечь и нечто действительно поучительное.
Воспользуемся таким алгоритмом: выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент ai>x, затем будем просматривать массив справа, пока не встретим aj<x. Теперь поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена, пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую - с ключами больше (или равными) x.
Теперь напомним, что наша цель - не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям затем к частям частей, и так до тех пор, пока каждая из частей не будет состоять из одного-единственного элемента. Эти действия описываются следующей программой, в которой процедура Sort рекурсивно обращается сама к себе.
const int n=8;
int a[n], b[n]={44,55,12,42,94,18,6,67};
/* Сортировка с помощью разделения*/
void sort(int L, int R)
{
int i,j,w,x;
i = L; j = R;
x = a[(L+R)/2];
do {
while(a[i]<x) i++;
while(x<a[j]) j--;
if(i<=j) {
w=a[i]; a[i]=a[j]; a[j]=w;
i++; j--;
}
while(i<=j);
if(L<j) sort(L, j);
if(i<R) sort(i, R)
}
void QuickSort(int n, int a[]);
{
sort(1, n)
}
/* Головная программа */
void main()
{
a = b;
printf("Массив a до сортировки ");
writev(n, n, a, " a");
printf("\n");
QuickSort(n, a);
writeln("Массив a после сортировки ");
writev(n, n, a, " a");
}
4. Пример разработки программы сортировки массива в Borland C++ Builder
4.1. Постановка задачи
Пусть задан
массив чисел
размерности n.
Требуется составить программу для формирования массива B из массива A с упорядочением элементов по возрастанию.
4.2. Описание алгоритма
Задание размерности n массивов A,B;
Ввод исходного массива A;
Формирование массива B из элементов массива A.
Упорядочение элементов массива B по возрастанию
Вывод массива С в виде таблицы.
4.3. Реализация алгоритма в Delphi
Согласно условиям задачи требуется задать размерность матриц n, исходный одномерный числовой массив A. Для размещения размерности n определим в программе переменную n. Для хранения исходного массива A, а также для размещения массива результата B определим в программе тип данных массив и переменные a, b этого типа. Для отображения в интерфейсном окне программы (окне формы) данных (размерности, исходных матриц и матрицы результата) следует использовать стандартные визуальные объекты: элемент редактирования Edit1 – для размерности; таблицы StringGreed1 - StringGreed2 – для массивов A, B соответственно. Для обеспечения возможности ввода данных в поля таблицы StringGreed1 в инспекторе объектов следует установить значение true для свойства Edition вкладки Options. В поле FixedCols инспектора объектов для StringGreed1 и StringGreed2 ввести значение 0
Для отображения в окне формы пояснений к выбранным визуальным компонентам следует использовать метки Label. Для построения и отображения графика в виде столбиковой диаграммы используется объект Chart. В объект Chart с помощью кнопки Add… закладки Chart встроенного редактора свойств необходимо вставить два объекта Series1 и Series2 типа Bar. Встроенный редактор Chart вызывается с помощью пункта Edit Chart… локального меню этого объекта (для вызова нажать правую клавишу мыши на объекте Chart)
Для управления работой программы выберем в качестве управляющих элементов кнопки Button1 - Button4, с которыми свяжем соответствующие шаги алгоритма. В результате окно формы с выбранными объектами может быть представлено как показано на рис. 5.1.
Рис. 4.1. Окно формы с выбранными объектами для сортировки одномерного массива
С событием Click каждой кнопки свяжем определенное действие, которое должна выполнить программа в ответ на нажатие конкретной кнопки при выполнении программы: Button1 – запрос и ввод размерности массивов и таблиц; Button2 – запрос и ввод исходного массива A (перед этим значения элементов исходного массива должны быть введены в таблицу StringGreed1; Button3 – сортировка массива методом простого выбора и вывод упорядоченного массива в таблицу StringGreed2 для отображения в окне формы; Button4 – построения графика (столбиковой диаграммы) по значениям элементов массива A до и после сортировки. Для того чтобы программа в ответ на конкретное событие выполняла именно то действие, которое требуется, в окне кода вносим соответствующий программный код для обработчика каждого события Click. В результате получаем следующий исходный код программы для сортировки одномерного массива.
Файл Sort.h:
#ifndef SortH
#define SortH
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include <Chart.hpp>
#include <ExtCtrls.hpp>
#include <Grids.hpp>
#include <TeEngine.hpp>
#include <TeeProcs.hpp>
#include <Series.hpp>
const int M = 15;
class TForm1 : public TForm
{
__published: // IDE-managed Components
TEdit *Edit1;
TButton *Button1;
TButton *Button2;
TButton *Button3;
TButton *Button4;
TLabel *Label1;
TStringGrid *StringGrid1;
TStringGrid *StringGrid2;
TChart *Chart1;
TBarSeries *Series1;
TBarSeries *Series2;
void __fastcall Button1Click(TObject *Sender);
void __fastcall Button2Click(TObject *Sender);
void __fastcall Button3Click(TObject *Sender);
void __fastcall Button4Click(TObject *Sender);
private: // User declarations
public: // User declarations
__fastcall TForm1(TComponent* Owner);
};
extern PACKAGE TForm1 *Form1;
void SortSelection(int n, int a[]);
#endif
Файл Sort.cpp:
#include <vcl.h>
#pragma hdrstop
#include "Sort.h"
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int a[M], b[M];
int n;
void SortSelection(int n, int a[])
{ /* Сортировка одномерного массива a размерности n методом простого выбора */
int i,j,k,x;
for(i=0; i<n; i++) {
k=i; x=a[i];
for(j=i+1; j<n; j++)
if(a[j]<x) { k=j; x=a[j]; }
a[k]=a[i]; a[i]=x;
}
}
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
void __fastcall TForm1::Button1Click(TObject *Sender)
{
n = StrToInt(Edit1->Text);
StringGrid1->ColCount = n;
StringGrid2->ColCount = n;
for(int i=0; i<n; i++) {
StringGrid1->Cells[i][0]=IntToStr(i+1);
StringGrid2->Cells[i][0]=IntToStr(i+1);
}
}
void __fastcall TForm1::Button2Click(TObject *Sender)
{
for(int i=0; i<n; i++) a[i]=StrToInt(StringGrid1->Cells[i][1]);
}
void __fastcall TForm1::Button3Click(TObject *Sender)
{
int i,j,k,x;
for(i=0; i<n; i++) b[i]=a[i];
SortSelection(n, b);
for(i=0; i<n; i++) StringGrid2->Cells[i][1]=IntToStr(b[i]);
}
void __fastcall TForm1::Button4Click(TObject *Sender)
{
Series1->Clear(); Series2->Clear();
/* Рисуем график */
for(int i=0; i<n; i++) {
Series1->AddXY(i, a[i], "", clRed);
Series2->AddXY(i, b[i], "", clGreen);
}
}
На рис.4.2. представлено окно программы с исходным и упорядоченным массивом.
Рис. 4.2. Окно программы с исходным и упорядоченным массивом, которые отображены в виде таблиц и столбиковых диаграмм на графике