Алгоритмы работы с линейными массивами.

Линейный поиск в массивах, или как его ещё называют, поиск в ЛОБ эффективен в массивах, с небольшим количеством элементов, причём элементы в таких массивах никак не отсортированы и не упорядочены. Алгоритм линейного поиска в массивах последовательно проверяет все элементы массива и сравнивает их с ключевым значением. Таким образом, в среднем необходимо проверить половину значений в массиве, чтобы найти искомое значение. Чтобы убедиться, в отсутствии искомого значения необходимо проверить все элементы массива. Разработаем программу, которая ищет минимальное значение в массиве. Поиск в программе реализован согласно алгоритму линейного поиска в массиве.

25. Сортировка массивов (пузырьком, слиянием, подсчетом, быстрая сортировка Хоара)

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubblesort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: {\displaystyle O}O(n^2)

voidbubbleSort(int* arrayPtr, intlength_array) // сортировка пузырьком

{

inttemp = 0; // временная переменная для хранения элемента массива

boolexit= false; // болевая переменная для выхода из цикла, если массив отсортирован

while(!exit) // пока массив не отсортирован

{

exit= true;

for(intint_counter = 0; int_counter < (length_array - 1); int_counter++) // внутреннийцикл

//сортировка пузырьком по возрастанию - знак >

//сортировка пузырьком по убыванию - знак <

if(arrayPtr[int_counter] > arrayPtr[int_counter + 1]) // сравниваемдвасоседнихэлемента

{

// выполняем перестановку элементов массива

temp = arrayPtr[int_counter];

arrayPtr[int_counter] = arrayPtr[int_counter + 1];

arrayPtr[int_counter + 1] = temp;

exit= false; // на очередной итерации была произведена перестановка элементов

}

}

{\displaystyle (n^{2})} Алгоритмы работы с линейными массивами. - student2.ru .Сортировка слиянием (англ. mergesort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

privatevoidSortUnsorted(int[] a, intlo, inthi) {

if (hi <= lo)

return;

int mid = lo + (hi - lo) / 2;

SortUnsorted(a, lo, mid);

SortUnsorted(a, mid + 1, hi);

int[] buf = Arrays.copyOf(a, a.length);

for (int k = lo; k <= hi; k++)

buf[k] = a[k];

int i = lo, j = mid + 1;

for (int k = lo; k <= hi; k++) {

if (i > mid) {

a[k] = buf[j];

j++;

} else if (j > hi) {

a[k] = buf[i];

i++;

} else if (buf[j] < buf[i]) {

a[k] = buf[j];

j++;

} else {

a[k] = buf[i];

i++;

}

}

}

Здесь:

a – массив;
lo – позиция первого элемента в массиве (для первой итерации = 0);
hi – позиция последнего элемента в массиве (для первой итерации = a.length — 1).

Сортировка подсчётом(Черпачная) (англ. Countingsort) — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.

В этом варианте помимо входного массива A потребуется два вспомогательных массива — C[0..k - 1] для счётчика и B[0..n - 1] для отсортированного массива. Сначала следует заполнить массив C нулями, и для каждого A[i] увеличить C[A[i]] на 1. Далее подсчитывается количество элементов меньших или равных {\displaystyle k-1}k-1. Для этого каждый C[j], начиная с C[1], увеличивают на C[j - 1]. Таким образом в последней ячейке будет находиться количество элементов от {\displaystyle 0}0 до {\displaystyle k-1}k-1 существующих во входном массиве. На последнем шаге алгоритма читается входной массив с конца, значение C[A[i]] уменьшается на 1 и в каждый B[C[A[i]]] записывается A[i]. Алгоритмустойчив.

StableCountingSort

for i = 0 to k - 1

C[i] = 0;

for i = 0 to n - 1

C[A[i]] = C[A[i]] + 1;

for j = 1 to k - 1

C[j] = C[j] + C[j - 1];

for i = n - 1 to 0

C[A[i]] = C[A[i]] - 1;

B[C[A[i]]] = A[i];

C++

voidcounting_sort(int* vec, unsignedint len, int min, int max)

2 {

3 assert(min <= max);

4 assert(vec !=NULL);

6 int* cnt =newint[max-min+1];

8 for (int i = min; i <= max; ++i) {

9 cnt[i - min] =0;

10 }

12 for (int i =0; i < len; ++i) {

13 ++cnt[vec[i] - min];

14 }

16 for (int i = min; i <= max; ++i) {

17 for(int j = cnt[i - min]; j--;) {

18 *vec++= i;

19 }

20 }

21 delete [] cnt;

22 }

Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем {\displaystyle O(n\log n)}O(nlogn) обменов при упорядочении {\displaystyle n}n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

int n, a[n]; //n - количество элементов

voidqs(int* s_arr, int first, int last)

{

int i = first, j = last, x = s_arr[(first + last) /2];

do {

while (s_arr[i] < x) i++;

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

if(i <= j) {

if (s_arr[j] > s_arr[i]) swap(&s_arr[i], &s_arr[j]);

i++;

j--;

}

} while (i <= j);

if (i < last)

qs(s_arr, i, last);

if (first < i)

qs(s_arr, first, i);

}

Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.

qs(a, 0, n-1);

Наши рекомендации