2 заметки с тегом

алгоритмы

Алгоритм поиска Ли

Алгоритм поиска пути в планарном графе. Зачастую используется в схемотехнике и в играх (стратегиях) для поиска кратчайшего пути.

Алгоритм состоит из 3 шагов:

  1. Инициализация
  2. Распространение волны
  3. Восстановление пути

Также есть 2 способа поиска пути: ортогональный и ортогонально-диагональный. Ниже на скриншотах можно увидеть работу этих двух способов.

Ортогональный поиск.
Ортогонально-диагональный поиск.

Псевдокод

Взято из Википедии.

Инициализация

Пометить стартовую ячейку 
d := 0

Распространение волны

ЦИКЛ
  ДЛЯ каждой ячейки loc, помеченной числом d
    пометить все соседние свободные непомеченные ячейки числом d + 1
  КЦ
  d := d + 1
ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны)

Восстановление пути

ЕСЛИ финишная ячейка помечена
ТО
  перейти в финишную ячейку
  ЦИКЛ
    выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
    перейти в выбранную ячейку и добавить её к пути
  ПОКА текущая ячейка — не стартовая
  ВОЗВРАТ путь найден
ИНАЧЕ
  ВОЗВРАТ путь не найден

Пример кода, который реализует алгоритм и выводит на экран путь (C#).

Алгоритмы сортировки

Классификация

  1. По степени роста сложности
  2. По использованию дополнительной памяти
  3. Рекурсивный или нет
  4. По устойчивости
  5. По методу сортировки: вставка, слияние, обмен

Распространенные алгоритмы

  • Сортировка пузырьком
  • Сортировка вставками
  • Сортировка выбором
  • Сортировка слиянием
  • Быстрая сортировка

Ссылка на сайт с гифками, которые демонстрируют работу алгоритмов: https://www.toptal.com/developers/sorting-algorithms

Сортировка пузырьком

Самая стандартная и простая сортировка. Выполняет проходы по массиву и перемещает наибольший элемент в конец массива.

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n) O(n^2) O(n^2)
Рост памяти O(1) O(1) O(1)
public void Sort(int[] inputArray)
{
	for (int i = 0; i < inputArray.Length; i++) {
		for (int j = 1; j < inputArray.Length; j++) {
			if (inputArray[j-1] > inputArray[j]) {
				Swap(inputArray, j-1, j);
			}
		}
	}
}

public void Swap(int[] inputArray, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = inputArray[indexLeft];
	inputArray[indexLeft] = inputArray[indexRight];
	inputArray[indexRight] = temp;
}

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

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n) O(n^2) O(n^2)
Рост памяти O(1) O(1) O(1)
public static void Sort(int[] inputArray)
{
	int currentElementIndex= 1;
	while (currentElementIndex < inputArray.Length)
	{
		if (inputArray[currentElementIndex] < inputArray[currentElementIndex - 1]) {
			var newIndex = FindIndex(inputArray, inputArray[currentElementIndex]);
			Insert(inputArray, newIndex, currentElementIndex);
		}
		currentElementIndex++;
	}
}

public static int FindIndex(int[] inputArray, int element)
{
	for (int i = 0; i < inputArray.Length; i++)
	{
		if (inputArray[i] > element) {
			return i;
		}
	}
	return 0;
}

public static void Insert(int[] inputArray, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = inputArray[indexLeft];
	inputArray[indexLeft] = inputArray[indexRight];
	for (int current = indexRight; current > indexLeft; current--) {
		inputArray[current] = inputArray[current-1];
	}
	inputArray[indexLeft + 1] = temp;
}

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

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n) O(n^2) O(n^2)
Рост памяти O(1) O(1) O(1)
public static void Sort(int[] input) {
	for (int i = 0; i < input.Length; i++) {
		var smallestElementIndex = FindIndexOfSmallestElement(input, i);
		Swap(input, smallestElementIndex, i);
	}
}

public static int FindIndexOfSmallestElement(int[] input, int startFrom = 0) {
	var smallestElementValue = input[startFrom];
	var smallestElementIndex = startFrom;
	for (int i = startFrom + 1; i < input.Length; i++)
	{
		if (smallestElementValue > input[i]) {
			smallestElementValue = input[i];
			smallestElementIndex = i;
		}
	}
	return smallestElementIndex;
}

public static void Swap(int[] input, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = input[indexLeft];
	input[indexLeft] = input[indexRight];
	input[indexRight] = temp;
}

Сортировка слиянием
Разбивает массив на подмассивы примерно одинакового размера, рекурсивно разбивает до тех пор, пока размер массива будет равен 1. После этого происходит сортировка частей и их соединение в один.

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n log n) O(n log n) O(n log n)
Рост памяти O(n) O(n) O(n)
public static void Sort(int[] input) {
	if (input.Length <= 1) {
		return;
	}
	
	// Поделили массивы
	var leftSize = input.Length / 2;
	var rightSize = input.Length - leftSize;
	var left = new int[leftSize];
	var right = new int[rightSize];
	
	// Скопировали данные из основного массива
	Array.Copy(input, 0, left, 0, leftSize);
	Array.Copy(input, leftSize, right, 0, rightSize);
	
	Sort(left);
	Sort(right);
	
	Merge(input, left, right);
}

public static void Merge(int[] input, int[] left, int[] right) {
	var leftIndex = 0;
	var rightIndex = 0;
	var leftAndRightSize = left.Length + right.Length;
	
	for (int i = 0; i < leftAndRightSize; i++) {
		if (leftIndex >= left.Length) {
			input[i] = right[rightIndex];
			rightIndex++;
		}
		else if (rightIndex >= right.Length) {
			input[i] = left[leftIndex];
			leftIndex++;
		}
		else if (left[leftIndex] < right[rightIndex]) {
			input[i] = left[leftIndex];
			leftIndex++;
		}
		else {
			input[i] = right[rightIndex];
			rightIndex++;
		}
	}
}

Быстрая сортировка
Один из самых быстрых алгоритмов, о чем говорит название.

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

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n log n) O(n log n) O(n^2)
Рост памяти O(1) O(1) O(1)
public static void Sort(int[] input, int leftIndex, int rightIndex) {
	var i = leftIndex;
	var j = rightIndex;
	var pivot = input[(leftIndex + rightIndex) >> 1];
	
	while (i <= j) {
		while (input[i] < pivot) {
			i++;
		}
		while (input[j] > pivot) {
			j--;
		}
		
		if (i <= j) {
			Swap(input, i, j);
			j--;
			i++;
		}
		
		if (leftIndex < j) {
			Sort(input, leftIndex, j);
		}
		
		if (rightIndex > i) {
			Sort(input, i, rightIndex);
		}
	}
}

public static void Swap(int[] input, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = input[indexLeft];
	input[indexLeft] = input[indexRight];
	input[indexRight] = temp;
}
 Нет комментариев    75   2 мес   алгоритмы   программирование