Сортировка вставками

Задача.В программе задан массив из 10 элементов. Необходимо отсортировать его по возрастанию и вывести отсортированный массив на экран. Для сортировки использовать алгоритм сортировки массива вставками (см. рис. 4.2.).

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

int main(){

const int arraySize = 10;

int a[arraySize] = {2,6,4,8,10,12,89,68,45,37};

int b[arraySize];

cout << "In natural order" << endl;

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

cout << a[i] << "\t";

cout << endl;

//Insert sorting************************

for (i = 0; i< arraySize; i++){

int j = i;

while ((j>0) && (b[j-1]>a[i]))

{

b[j]=b[j-1];

j=j-1;

}

b[j] = a[i];

}

//*******************************************

cout << "In right order" << endl;

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

cout << b[i] << "\t";

cout << endl;

}

Рис. 4.2. Программа, иллюстрирующая работу сортировки вставками

4.3. Поиск в массивах Линейный поиск

int main()

{

const int arraySize = 10;

int a[arraySize] = {13,6,4,8,10,12,89,68,45,37};

int searchKey, element;

cout << "Enter search key: ";

cin >> searchKey;

element = -1;

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

if(a[i]==searchKey)

element = i;

if (element != -1)

cout << "Number is " << element << endl;

else

cout << "No such element" << endl;

}

Рис. 4.3. Линейный поиск в массиве

Линейный поиск [1] сравнивает каждый элемент массива с ключом поиска. Поскольку массив может быть неупорядочен, вполне вероятно, что отыскиваемое значение окажется первым же элементом массива. Но в среднем программа должна сравнить с ключом поиска половину элементов массива (рис. 4.3.).

Метод линейного поиска хорошо работает для небольших или для неотсортированных массивов. Однако для больших массивов линейный поиск неэффективен. Если массив отсортирован, можно использовать высокоэффективный метод двоичного поиска.

Двоичный поиск

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

4.4. Многомерные массивы

Массивы в С++ могут иметь много индексов. Обычным представлением многомерных массивов являются таблицы значений, содержащие информацию в строках и столбцах. Чтобы определить отдельный табличный элемент, нужно указать два индекса: первый (по соглашению) показывает номер строки, а второй (по соглашению) - номер столбца. Таблицы или массивы, которые требуют двух индексов для указания отдельного элемента, называются двумерными.

Каждый элемент в двумерном массиве arrопределяется именем элемента в формеarr[i][j];arr– это имя массива, аiиj– индексы, которые однозначно определяют каждый элемент вarr. Имена элементов первой строки имеют первый индекс0, имена элементов четвертого столбца имеют второй индекс3.

Многомерные массивы могут получать начальные значения в своих объявления точно так же, как массивы с единственным индексом. Значения группируются в строки, заключенные в фигурные скобки:

int b [2][3] = {{1,2,3,}, {4,5,6}};

Если начальных значений в данной строке не хватает для их присвоения всем элементам строки, то остающимся элементам строки присваиваются нулевые значения

int b [2][3] = {{1,}, {4,5,6}};

int Array [2][3] = {{1,2,3,4,5};

Объявление массива Arrayсодержит пять начальных значений. Начальные значения присваиваются первой строке, затем второй строке. Любые элементы, которые не имеют явно заданных начальных значений, автоматически получают нулевые значения.