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

убыванию, последней цифре, сумме делителей, …).
Задача: переставить элементы массива в порядке возрастания.
Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
сложные, но эффективные
«быстрая сортировка» (Quick Sort)
сортировка «кучей» (Heap Sort)
сортировка слиянием
пирамидальная сортировка

сложность O(N2)

сложность O(N·logN)

вверх.
Для массивов – самый маленький («легкий») элемент перемещается вверх («всплывает»).

начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-ый проход

2-ой проход

3-ий проход

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

…
A[0] и A[1]

A[j] и A[j+1]

for( j = N-2; j >= 0 ; j-- )
if ( A[j] > A[j+1] ) {
c = A[j];
A[j] = A[j+1];
A[j+1] = c;
}

0

; j-- )
if ( A[j] > A[j+1] ) {
c = A[j];
A[j] = A[j+1];
A[j+1] = c;
}

1

(i+1)-ый проход

for ( j = N-2; j >= i ; j-- )
...

i

i, j, c;
// заполнить массив
// вывести исходный массив
for (i = 0; i < N-1; i ++){
for (j = N-2; j >= i ; j --)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
}
}
// вывести полученный массив
}

элементы выше A[i] уже поставлены

i

меняем A[j] и A[j+1]

было обменов, массив уже отсортирован и остальные проходы не нужны.
Реализация: переменная-флаг, показывающая, был ли обмен; если она равна false, то выход.

do {
flag = false; // сбросить флаг
for (j = N-2; j >= 0; j --)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
flag = true; // поднять флаг
}
}
while ( flag ); // выход при flag = false

flag = false;

flag = true;

( flag );

boolean flag;

сбросить флаг
for ( j = N-2; j >= i ; j -- )
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
flag = true; // поднять флаг
}
i ++;
}
while ( flag ); // выход при flag = false

i = 0;

i

i ++;

с A[0])
из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[1]), и т.д.

) {
nMin = i ;
for ( j = i+1; j < N; j ++)
if( A[j] < A[nMin] ) nMin = j;
if( nMin != i ) {
c = A[i];
A[i] = A[nMin];
A[nMin] = c;
}
}

N-1

нужно N-1 проходов

поиск минимального от A[i] до A[N-1]

если нужно, переставляем

i+1

i

[0..100] и отсортировать его по последней цифре.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
30 11 41 32 13 14 25 76 97 58
Задача 2: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
13 14 25 30 76 97 58 41 32 11

условию (например, отрицательные), и скопировать их в другой массив.

Примитивное решение:

int N = 5;
int A[N], B[N];
// здесь заполнить массив A
for( i = 0; i < N; i ++ )
if( A[i] < 0 ) B[i] = A[i];

A

B

выбранные элементы не рядом, не в начале массива
непонятно, как с ними работать

ставится на место B[count].

int A[N], B[N], count = 0;
// здесь заполнить массив A
for( i = 0; i < N; i ++ )
if( A[i] < 0 ) {
B[count] = A[i];
count ++;
}
// вывод массива B
for( i = 0; i < count; i ++ )
System.out.printf(
"%d\n", B[i]);

A

B

count

все числа, у которых вторая с конца цифра (число десятков) – ноль.
Пример:
Исходный массив:
40 105 203 1 14
Результат:
105 203 1
Задача 2: Заполнить массив случайными числами и выделить в другой массив все числа, которые встречаются более одного раза.
Пример:
Исходный массив:
4 1 2 1 11 2 34
Результат:
1 2

установить, что его нет.
Решение: для произвольного массива: линейный поиск (перебор)
недостаток: низкая скорость
Как ускорить? – заранее подготовить массив для поиска
как именно подготовить?
как использовать «подготовленный» массив?

i ++)
if ( A[i] == X ) {
nX = i;
break; //выход из цикла
}

Улучшение: после того, как нашли X, выходим из цикла.

break;

nX = -1; // пока не нашли ...
for ( i = 0; i < N; i ++) // цикл по всем элементам
if ( A[i] == X ) // если нашли, то ...
nX = i; // ... запомнили номер
if (nX<0) System.out.printf("Не нашли...");
else System.out.printf("A[%d]=%d", nX, X);

nX – номер нужного элемента в массиве

элемент A[c] и сравнить с X.
Если X = A[c], нашли (выход).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.

N-1; // границы: ищем от A[0] до A[N-1]
while ( R >= L ){
c = (R + L) / 2;
if (X = = A[c]) {
nX = c;
break;
}
if (X < A[c]) R = c - 1;
if (X > A[c]) L = c + 1;
}
if (nX < 0) System.out.printf("Не нашли...");
else System.out.printf("A[%d]=%d", nX, X);

номер среднего элемента

если нашли …

выйти из цикла

сдвигаем границы

>