Записки программиста Программирование и не только

27Июл/100

Сортировка выбором (выделением)

В данной сортировке сначала ищется (выбирается) минимальный элемент в массиве и меняется местами с первым элементом. Первый элемент из дальнейшей сортировки выбывает.

void selection_sort(int *mArray, int _size)
{
	for(int i = 0; i < _size; i++)
	{
		int k = i;
		for(int j = k + 1; j < _size; j++)
		{
			if(mArray[k] > mArray[j]) k = j;
		}
		if(i != k) std::swap(mArray[i], mArray[k]);
	}
}
26Июл/100

Сортировка "Шейкер"

int shaker_sort(int *&mArray, int _size)
{
	int L = 0;
	int R = _size - 1;
	int k = _size - 1;
	do
	{
		for( int j = R; j >= L; j--)	//Ставим на место самый маленький элемент
		{
			if(mArray[j-1] > mArray[j])
			{
				std::swap(mArray[j], mArray[j-1]);
				k = j;
			}
		}
		L = k + 1;	//Сдвигаем левую границу
		for(int j = L; j <= R; j++)	//Ставим на место самый большой элемент
		{
			if(mArray[j-1] > mArray[j])
			{
				std::swap(mArray[j], mArray[j-1]);
				k = j;
			}
		}
		R = k - 1;	//Сдвигаем правую границу
	} while(L < R);
}
25Июл/100

Последовательный (линейный) поиск

Поиск последовательно проверяет все элементы, а так же достижение конца массива.

int line_seach(int *mArray, int _size, int find_el)
{
	int position = 0;
	for(;(mArray[position] != find_el) && (position < _size); position++);	//Поиск

	position++;	//Корректируем номер позиции

	return position <= _size ? position : 0;	//Если элемент найден, то возвращаем его позицию, если нет, то 0
}
Метки записи: , Нет комментариев
21Июл/100

Двоичный поиск (только для отсортированных массивов)

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

Боевой пример:

int dv_seach(int *mArray, int _size, int find_el)
{
	int left = 0, right = _size - 1, m;	//Устанавливаем границы
	while(left < right)
	{
		m = (left + right) / 2;	//Выбираем середину
		if (find_el > mArray[m]) left = m + 1;	//Если элемент в середине рассматриваемого
												//участка больше искомого, то сдвигаем границу влево
		else right = m;							//Если меньше - вправо
	}

	return find_el == mArray[left] ? left + 1 : 0;	//Если элемент найден, то возвращаем его позицию, если нет, то 0
}
Метки записи: , Нет комментариев
20Июл/100

Планы

Итак, в планах написать и оформить:

Алгоритмы поиска символа:
1. Последовательный (линейный) поиск (уже есть)
2. Поиск с барьером (уже есть)
3. Двоичный поиск (бинарный, деление пополам) - только для отсортированных массивов (уже есть)

Алгоритмы поиска слова:
1. Прямой поиск (уже есть)
2. КМП поиск (уже есть) дооформить
3. Алгоритм Бойера-Мура (уже есть (упрощенный(?)))

Алгоритмы сортировки:
1. Сортировка обменом (метод «пузырька) (C++ и Java) дооформить
2. Сортировка «Шейкер» (уже есть) дооформить
3. Сортировка вставками (включением) (уже есть) дооформить
4. Сортировка выбором (выделением) (уже есть)
5. Алгоритм Шелла (уже есть)
6. Алгоритм Хоара (быстрая сортировка) (C++, Pascal)
7. Пирамидальная сортировка (уже есть)
8. Гномья сортировка (Gnome Sort) (Java)

Динамические структуры данных:
1. Линейный односвязный список
2. Очередь
3. Стек
4. Дек
5. Кольцевой односвязный список
6. Линейный двусвязный список
7. Бинарное дерево
7.1. AVL дерево
7.2. Красно-черное дерево

Алгоритмы сжатия информации:
1. Алгоритм Шеннона и Фако
2. Алгоритм Хафмана
3. Алгоритм скошенного дерева

Метки записи: Нет комментариев
20Июл/102

Поиск с барьером

Алгоритм поиска заключается в установке "барьера" - искомого элемента - в конец массива.
Таким образом пропадает необходимость проверки на достижение конца массива.

Боевой пример:

int barrier_seach(int *mArray, int _size, int find_el)
{
	int position = 0;
	if (mArray[_size-1] != find_el)	//Проверим, нет ли искомого элемента на последней позиции
	{
		mArray[_size-1] = find_el;	//Установим &quot;барьер&quot;
		for(;mArray[position] != find_el; position++);	//Поиск
		position++;	//Корректируем номер позиции
	}
	else return _size;	//Если искомый элемент на последней позиции, то возвращаем размер

	return position < _size ? position : 0;	//Если элемент найден, то возвращаем его позицию, если нет, то 0
}
Метки записи: , 2 Комментарии