Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Сортировка слияниями






Метод слияний – один из первых в теории алгоритмов сортировки. Он предложен Дж. фон Нейманом в 1945 году.

Рассмотрим следующую задачу. Объединить («слить») упорядоченные фрагменты массива A A [ k ],... A [ m ] и A [ m +1],..., A [ q ] в один A [ k ],..., A [ q ], естественно, тоже упорядоченный (k £ m £ q). Основная идея решения состоит в сравнении очередных элементов каждого фрагмента, выяснении, какой из элементов меньше, переносе его во вспомогательный массив D (для простоты) и продвижении по тому фрагменту массива, из которого взят элемент. При этом следует не забыть записать в D оставшуюся часть того фрагмента, который не успел себя «исчерпать».

Пример. Пусть первый фрагмент состоит из 4-х элементов: 2 4 6 11, а второй – из 8-и: 1 3 5 7 14 17. Рис 1. Иллюстрация слияния упорядоченных фрагментов. иллюстрирует начало объединения упорядоченных фрагментов.

Рис 1. Иллюстрация слияния упорядоченных фрагментов.

Реализация слияния фрагментов:

#include < iostream>

#include < locale.h>

using namespace std;

 

void Sl(int m[], int k, int q) // или...int *a

{

// k – нижняя граница упорядоченного фрагмента

// q – верхняя граница фрагмента

int i, j, t, mid, d[20];

i=k;

mid=k+(q-k)/2;

j=mid+1;

t=1;

while (i< =mid & & j< =q)

{

if (m[i]< =m[j]) {d[t]=m[i]; i++; }

else { d[t]=m[j]; j++; }

t++;

}

// Один из фрагментов обработан полностью, осталось перенести в D остаток другого фрагмента

while (i< =mid)

{ d[t]=m[i]; i++; t++; }

while (j< =q)

{ d[t]=m[j]; j++; t++; }

for (i=1; i< =t-1; i++) m[k+i-1]=d[i];

}

// Рекурсивная реализация сортировки слиянием

void Sort_Sl(int *m, int i, int j)

{

int t;

if (i< j)

// Обрабатываемый фрагмент массива состоит более, чем из одного элемента

if (j-i==1) {

if (m[j]< m[i])

// Обрабатываемый фрагмент массива состоит из двух элементов*)

{ t=m[i]; m[i]=m[j]; m[j]=t; }; }

else {

// Разбиваем заданный фрагмент на два

Sort_Sl(m, i, i+(j-i)/2); // рекурсивные вызовы процедуры Sort_Sl

Sort_Sl(m, i+(j-i)/2+1, j);

Sl(m, i, j);

}

}

void input(int *m, int & n) // Имя массива является адресом его начала.

{ // Или void input(int m[], int & n)

cout< < " Введите количество элементов массива ";

cin> > n;

for (int i=0; i< n; i++)

{

cout< < " a[" < < i< < " ]=";

cin> > m[i]; // Конструкция a[i] эквивалентна *(a + i)

}

 

}

void print (int *m, int n)

{

for (int i=0; i< n; i++)

cout< < m[i]< < " ";

cout< < " \n";

 

}

void main()

{

setlocale(LC_ALL, " rus");

const int nmax=20;

int n, a[nmax];

input(a, n);

cout< < " Исходный массив: \n";

print(a, n);

Sort_Sl(a, 0, n-1);

cout< < " Отсортированный массив: \n";

print(a, n);

}

Первый вызов процедуры – Sort_Sl(a, 0, n-1);, где a – исходный массив из N элементов.

Данный алгоритм работает быстрее чем, например, пузырьковая, а недостаток метода – в требовании довольно большого объема дополнительной памяти.

9. Быстрая сортировка (сортировка Хоара, 1962) [1]

Рассмотрим элемент, находящийся посередине массива М (назовем его Х). Затем начнем осуществлять два встречных просмотра массива: двигаемся слева направо, пока не найдем элемент M [ i ]> X и справа налево, пока не найдем элемент M [ j ]< X. Когда указанные элементы будут найдены, поменяем их местами и продолжим процесс " встречных просмотров с обменами", пока два идущих навстречу друг другу просмотра не встретятся. В результате массив разделится на две части: левую, состоящую из элементов меньших или равных Х, и правую, в которую попадут элементы, большие или равные Х. После такого разделения массива М, чтобы завершить его сортировку, достаточно осуществить то же самое с обеими полученными частями, затем с частями этих частей и т.д., пока каждая часть не будет содержать ровно один элемент.

Реализация указанного метода приводит к следующему (рекурсивному!) решению задачи сортировки:

void Qsort(int a[], int L, int R) // или...int *a

{ int i=L, j=R, w, x;

x=a[(L+R)/2];

do { while (a[i]< x) i++;

while (a[j]> x) j--;

if(i< =j)

{w=a[i]; a[i]=a[j]; a[j]=w;

i++; j--; }

} while (i< j);

if (L< j) Qsort(a, L, j);

if (i< R) Qsort(a, i, R);

}

void main()

{

setlocale(LC_ALL, " rus");

const int nmax=20;

int n, a[nmax];

input(a, n);

cout< < " Исходный массив: \n";

print(a, n);

Qsort(a, 0, n-1);

cout< < " Отсортированный массив: \n";

print(a, n);

}

Основная программа должна содержать вызов процедуры в виде:


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.009 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал