Шейкерная или челночная сортировка

При использовании пузырьковой сортировки «легкие» и «тяжелые» элементы неодинаково быстро продвигаются к своим местам. Так, если самый легкий элемент стоит на 250-м месте в массиве из 500 элементов, то он переместится на свое законное первое место уже в ходе первого просмотра. Для того, чтобы самый тяжелый элемент сместился на свое законное последнее место с 250-го места того же массива, понадобится целых 250 просмотров! Чтобы сделать продвижения легких и тяжелых элементов одинаковыми по скорости и тем самым сократить количество необходимых просмотров, можно чередовать направления просмотров: сначала справа налево, затем слева направо. Результаты работы шейкерной сортировки представлены последовательным представлением содержимого массивов в таблицах 8.6–8.9.

Таблица 8.6 – Результат первого просмотра массива методом шейкерной сортировки

				55

Таблица 8.7 – Результат второго просмотра массива методом шейкерной сортировки

Таблица 8.8 – Результат третьего просмотра массива методом шейкерной сортировки

Таблица 8.9 – Результат четвертого просмотра массива методом шейкерной сортировки

Код шейкерной сортировки:

int left=0,right=n-1;

while(left<right){

int flag=1;

for(int i=left;i<right;++i)//просмотр слева направо

if(a[i]>a[i+1]){

int tmp=a[i]; a[i]=a[i+1]; a[i+1]=tmp;//обмен

flag=0;

}

if(flag)

break;

--right; flag=1;

for(int i=right;i>left;--i)//посмотр справа налево

if(a[i]<a[i-1]){

int tmp=a[i];a[i]=a[i-1];a[i-1]=tmp;//обмен

flag=0;

}

if(flag)

break;

++left;

}

Сортировка устойчивая. В отдельных случаях может сработать существенно быстрее пузырьковой, но и код длиннее и запутаннее.

8.5. Поиск в отсортированном массиве

При поиске элемента key в массиве a длины n с использованием алгоритма последовательного сравнения элементов массива со значением key в среднем будет выполнено n/2 сравнений. В отсортированном массиве используется дихотомический (бинарный) поиск. При дихотомическом поиске требуется не более m сравнений, если n-m -ая степень 2, если n не является степенью 2, то n<k=2^m.

Массив делится пополам MID:=(L+R)/2 и определяется в какой части массива находится нужный элемент key. Т. к. массив упорядочен, то если a[MID]<X, то искомый элемент находится в правой части массива, иначе – находится в левой части. Выбранную часть массива снова надо разделить пополам и т. д., до тех пор, пока границы отрезка L и R не станут равны.

Пусть имеем массив, представленный в таблице 8.10.

Таблица 8.10 – Исходные данные

Найдем в нем индекс элемента со значением 29. Если элемента нет, выведем -1.

Сначала левая граница L=0, правая R=17.

Итерация 1. Находим MID=(0+17)/2=8. a[8]=17<29, заменяем L=MID+1=9.

Итерация 2. Находим MID=(9+17)/2=13. a[13]=25<29, заменяем L=MID+1=14.

Итерация 3. Находим MID=(14+17)/2=15. a[15]=31>29, заменяем R=MID=15.

Итерация 4. Находим MID=(14+15)/2=14. a[14]=29, R=MID=14=L, нашли.

Код бинарного поиска индекса элемента массива а, значение которого равно key. Массив a состоит из n целых чисел,

int key;

printf(“Enter elem to be found:”);

scanf(“%d”, &key);

int l=0, r=n-1, middle;

do

{

middle=(l+r)/2;//средний элемент

if(a[middle]<b)l=middle+1;//перенести левую границу

else r=middle;//перенести правую границу

}while(l!=r);

if(a[l]==b) return l;

else return -1;

8.6. Слияние отсортированных массивов

Пусть имеются два отсортированных по неубыванию массива. Нам требуется слить их в один, который будет также отсортирован по неубыванию. Можно тогда «склеить» массивы в один и отсортировать полученный массив. Это, однако, не лучшая идея. Учтите, что массивы могут быть достаточно большими, а сортировка больших массивов, да к тому же содержащих сложные и объемные элементы, может оказаться неоправданно затратной.

С другой стороны, можно же просто сравнивать очередные элементы рассматриваемых массивов и помещать в результирующий массив тот из них, который меньше. Эти действия повторять, пока элементы в обоих массивах не исчерпаются.

Пример:

Массив a: 4 7 9 12 23 24 39

Массив b: 10 11 13 17 22 29 44 67

4<10 -> c[0]=4, 7<10 -> c[1]=7, 9<10 -> c[2]=9, 12>10 ->c[3]=10, 12>11 -> c[4]=11,

12<13 ->c[5]=12, 23>13 ->c[6]=13, 23>17 ->c[7]=17, 23>22 ->c[8]=22, 23<29 ->c[9]=23,

24<29 ->c[10]=24, 39>29 ->c[11]=29, 39<44 -> c[12]=39,

Массив a исчерпан, остаток массива b «доливаем» в с: c[13]=44, c[14]=67

Код слияния отсортированных массивов a и b в c (массив a содержит na элементов, массив b содержит nb элементов, считаем, что память под массивы выделена корректно, код оформлен функцией).

void slijanie(int c[], int &nc,int a[],int na, int b[], int nb)/*nc – количество элементов в результирующем массиве, выходной параметр, передается по ссылке */

{

int ia=0,ib=0,ic=0;

while(ia<na && ib<nb)

if(a[ia]<b[ib])

c[ic++]=a[ia++];

else c[ic++]=b[ib++];

for(; ia<na;)

c[ic++]=a[ia++];

for(;ib<nb;)

c[ic++]=b[ib++];

nc=ic;

}

Аналогично можно сливать и массивы, отсортированные в разных направлениях. Можно при слиянии исключать одинаковые элементы.

Упражнения:

1) Даны два массива – массив а из na целых чисел, расположенных по возрастанию, и массив b из nb целых чисел, расположенных по невозрастанию (убыванию, но допускаются равные элементы). Сформировать из них новый массив c, элементы которого будут расположены по неубыванию.

2) Напишите функцию, которая сливает два отсортированных по возрастанию массива в один, элементы которого расположены по убыванию (Равные элементы включаются в единственном экземпляре. Хорошо продумайте, какие параметры будет иметь ваша функция).

Динамическая память

Все переменные, объявленные в программе, размещаются в одной непрерывной области памяти, которую называют сегментом данных. Такие переменные не меняют своего размера в ходе выполнения программы и называются статическими.

Размера сегмента данных может оказаться недостаточно для размещения больших массивов информации. Кроме того, часто нам ничего неизвестно о размерах массивов, с которыми будет работать наша программа: в одной ситуации они могут содержать десятки тысяч элементов, в другой – лишь несколько десятков, в третьей, возможно, вообще не понадобятся. И, конечно, жаль выделять по максимуму в сегменте данных память для их хранения.

Выходом из этой ситуации является использование динамической памяти или т.н. кучи. Динамическая память – это память, выделяемая программе в процессе ее работы, когда уже точно известны все потребности. Специальная программа операционной системы (менеджер кучи) обрабатывает запросы, которые выдает ваша программа в ходе выполнения, выделяя из кучи память нужного размера по и освобождая ее по окончанию работы с ней.

Для работы с динамической памятью используют указатели. С их помощью осуществляется доступ к участкам динамической памяти, которые называются динамическими переменными. Динамические переменные создаются с помощью специальных функций и операций. Они существуют либо до конца работы программ, либо до тех пор, пока не будут уничтожены с помощью специальных функций или операций.

Для создания динамических переменных используют операцию new, определенную в С++:

указатель = new имя_типа:

или

указатель = new имя_типа(инициализатор);// инициализатор – выражение.

Операция new позволяет выделить и сделать доступным участок динамической памяти, который соответствует заданному типу данных. Если задан инициализатор, то в этот участок будет занесено значение, указанное в инициализаторе.

int*x=new int(5);

Для удаления динамических переменных используется операция delete, определенная в С++:

delete указатель;

где указатель содержит адрес участка памяти, ранее выделенный с помощью операции new.

delete x;

В языке Си определены библиотечные функции для работы с динамической памятью, их прототипы находятся в файле <stdlib.h>:

1) void*malloc(unsigned s) – возвращает указатель на начало области динамической памяти длиной s байт, при неудачном завершении возвращает NULL;

2) void*calloc(unsigned n, unsigned m) – возвращает указатель на начало области динамической памяти для размещения n элементов длиной m байт каждый, при неудачном завершении возвращает NULL;

3) void*realloc(void *p,unsigned s) –изменяет размер блока ранее выделенной динамической памяти до размера s байт, р – адрес начала изменяемого блока, при неудачном завершении возвращает NULL;

4) void *free(void *p) – освобождает ранее выделенный участок динамической памяти, р – адрес начала участка.

Пример:

int *u=(int*)malloc(sizeof(int)); // в функцию передается количество требуемой памяти в байтах, т. к. функция возвращает значение типа void*, то его необходимо преобразовать к типу указателя (int*).

free(u); //освобождение выделенной памяти

Указатели и массивы

10.1. Одномерные массивы и указатели

При определении массива ему выделяется память. После этого имя массива воспринимается как константный указатель того типа, к которому относятся элементы массива. Исключением является использование операции sizeof (имя_массива) и операции &имя_массива.

Примеры:

int a[100];

int k=sizeof(a);// результатом будет 4*100=400 (байтов).

int n=sizeof(a)/sizeof(a[0]);// количество элементов массива

Результатом операции & является адрес нулевого элемента массива. В С/С++ принято:

имя_массива=&имя_массива=&имя_массива[0]

Т.к. имя массива является указателем-константой, значением которой служит адрес первого элемента массива, то к нему применимы все правила адресной арифметики, связанной с указателями. Запись имя_массива[индекс] это выражение с двумя операндами: имя массива и индекс. Имя_массива – это указатель константа, а индекс определяет смещение от начала массива. Используя указатели, обращение по индексу можно записать следующим образом: *(имя_массива+индекс).

Пример:

for(int i=0;i<n;i++) // печать массива

cout<<*(a+i)<<" "; // к имени адресу массива добавляется константа i и полученное значение разыменовывается.

Так как имя массива является константным указателем, то его невозможно изменить, следовательно, запись *(а ++) будет ошибочной, а *(а +1) – нет.

Указатели можно использовать и при определении массивов:

int a[100]={1,2,3,4,5,6,7,8,9,10};

int * na=a; /* поставили указатель на уже определенный массив, теперь na можно «двигать» по массиву, ничего не мешает нам использовать na++*/

int *b=new int[100]; /* выделили в динамической памяти место под массив из 100 элементов, работать далее с b можно традицонно, употребляя и b[i], и *(b+i) */

10.2. Многомерные массивы и указатели

Многомерный массив это массив, элементами которого служат массивы. Например, массив с описанием int a[4][5] – это массив из 4 указателей типа int*, которые содержат адреса одномерных массивов из 5 целых элементов (см. рис.).

int **a

	Элементы типа *int

Инициализация многомерных массивов выполняется аналогично одномерным массивам. Примеры:

int a[3][4] = {11,22,33,44}, {55,66,77,88}, {99,110,120,130}}; /* проинициализированы все элементы массива*/

int b[3][4] = {{1},{2},{3}};// проинициализированы первые элементы каждой строки

int c[3][2]={1,2,3,4,5,6};// проинициализированы все элементы массива

Доступ к элементам многомерных массивов возможен и с помощью индексированных переменных и с помощью указателей:

a[1][1] – доступ с помощью индексированных переменных,

*(*(a+1)+1) – доступ к этому же элементу с помощью указателей (см. рис.).

10.3. Динамические массивы

Операция new при использовании с массивами имеет следующий формат:

new тип_элементов_массива[количество элементов в массиве].

Такая операция выделяет для размещения массива участок динамической памяти соответствующего размера, но не позволяет инициализировать элементы массива. Операция new возвращает указатель на выделенный в куче участок памяти, этот указатель будет адресом первого элемента массива. К моменту выделения динамической памяти размеры массива должны быть полностью определены.

Примеры:

1. int *a=new int[100];*/ выделение динамической памяти размером 100*sizeof(int) байтов*/

double *b=new double[10];/* выделение динамической памяти размером 10*sizeof(double) байтов */

2. long(*la)[4];// la- указатель на массив из 4 элементов типа long

lа=new[2][4];// выделение динамической памяти размером 2*4*sizeof(long) байтов

3. int**matr=(int**)new int[5][10]; /* еще один способ выделения памяти под двумерный массив*/

4. int **matr;

matr =new int*[n]; // выделяем память под массив указателей int*, их n элементов

for (int i=0;i<4;i++)matr[i]=new int[m];/* выделяем память под строки массива, в каждой строке будет m элементов

Указатель на динамический массив затем используется при освобождении памяти с помощью операции delete.

Примеры:

delete[] a; /* освобождает память, выделенную под массив, если а – адрес его начала

for (i=0; i<n; i++) delete [] matr[i]; // удаляем строки

delete [] matr; // удаляем массив указателей

Пример.

Удалить из матрицы строку с номером K

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

int main()

{

int n,m;//размерность матрицы

int i,j;

printf(“\nEnter n");

scanf(“%d”,&n);//ввод количества строк

printf(“\nEnter m");

scanf(“%d”,&m);//ввод количества столбцов

//выделение памяти

int **matr=new int* [n];// память под указатели на строки

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

matr[i]=new int [m]; // память под элементы каждой строки матрицы

//заполнение матрицы

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

for(j=0;j<m;j++)

matr[i][j]=rand()%100;//заполнение матрицы

//печать сформированной матрицы

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

{

for(j=0;j<m;j++)

printf(“%5d”,matr[i][j]);

printf("\n");

}

//удаление строки с номером к

int k;

printf("\nEnter k");

scanf(“%d”,&k);

int *tmp=matr[k];//запомним указатель на k- ю строку

for(i=k+1; i<n; i++)

matr[i-1]=matr[i]; /* удалим указатель на k-ю строку из массива указателей matr*/

delete []tmp; // освободим память, которую занимала k- я строка

--n; // уменьшим на 1 количество строк

//печать новой матрицы

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

{

for(j=0;j<m;j++)

printf(“%5d”, matr[i][j);

printf("\n");

}

return 0;

}