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

8Окт/120

Гномья сортировка (Gnome sort)

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
Дик Грун

Мой вариант реализации:

void gnom_sort(int[] mas) {
	int p = 2;
	int i = 1;
	for (; i < mas.length; ) {
		if (mas[i - 1] <= mas[i]) {
			p++;
			i = p;
		} else {
			int a = mas[i];
			mas[i] = mas[i - 1];
			mas[i - 1] = a;
			i--;
			if (i == 0) {
				p++;
				i = p;
			}
		}
	}
}
15Сен/126

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

Теории уже достаточно для того, чтобы начать делать всякое.
Попробуем реализовать простейшую сортировку.

Что такое сортировка пузырьком?
Это когда последовательно берется каждый элемент массива и "всплывается" на своё место пока не встретит более "легкий" элемент или конец массива.

Что для этого надо?
Для начала, нужно проходить по всему массиву:

for(int i = 0; i < arr.length; i++)

Ничего сложного, да?
Теперь надо каждый найденный элемент поднимать вверх.

for(int i = 1; i < arr.length; i++)	//внимание на начальный номер
					//связано это с тем, что сравниваем с "предыдущим" пузырьком
					//но индекса "-1" в массиве нет
{
	for(int j = i; j >= 1; j--)
	{
		//меняем элементы местами
		int a = arr[j];
		arr[j] = arr[j-1];
		arr[j-1] = a;
	}
}

Элементы "всплывают". Но чего-то не хватает... Точно, проверки - нужно ли вообще всплывать!

for(int i = 1; i < arr.length; i++)
{
	for(int j = i; (j >= 1) && (arr[j] < arr[j - 1]); j--)
	//ПОКА (arr[j] меньше arr[j-1]) И (в массиве еще есть элементы (j >= 0))
        {
                int a = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = a;
	}
}

Вот так вот.
Массив для проверки можно создать так:

int arr[] = {4, 7, 2, 9, 0, 1, 9, 12 ,56 ,78};

Но мы жешь программисты!
Так что воспользуемся готовой функцией random!

int arr[] = new inr[10];
for(int i = 0; i < arr.length; i++)
	arr[i] = Math.random();

В качестве домашнего задания попробуйте реализовать сортировку по убыванию.
Ну и на сложное - Гномью сортировку (gnome sort)

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);
}
31Май/100

Сортировка обменом (метод "пузырька")

void buble_sort(int mArray[], int mArr_size)
{
	for(int i = 1; i < mArr_size; i++)
		for (int k = i; (k >= 1) && (mArray[k] < mArray[k-1]); k--)
			std::swap(mArray[k],mArray[k-1]);
}
31Май/100

Сортировка вставками (включением)

void insertSort(int a[], int size)
    {
        int x, i, j;
        for (i = 1; i < size; i++)                   // цикл проходов, i - номер прохода
        {
            x = a[i];                               // сохраняем элемент, место которому необходимо найти
            for (j = i; j > 0 && a[j-1] > x; j--)    // поиск места элемента в готовой последовательности
                a[j] = a[j-1];                      // сдвигаем элемент направо, пока не дошли
            a[j] = x;                             // место найдено, вставить элемент
        }
    }
30Мар/100

Быстрая сортировка (Pascal)

В дополнении к ЭТОЙ теме.

procedure quickSort(l,h: integer);
var
	i,j,mid,tmp: integer;
begin
	i := l;
	j := h;
	mid := mArray[(l + h) div 2];
	repeat
		while mArray[i] < mid do inc(i);
		while mArray[j] > mid do dec(j);
		if (i < = j) then
		begin
			if (i < j) then
			begin
				tmp := mArray[i];
				mArray[i] := mArray[j];
				mArray[j] := tmp;
			end;
			inc(i);
			dec(j);
		end;
	until i > j;
	if l < j then quickSort(l, j);
	if i < h then quickSort(i, h);
end;
10Окт/090

Пирамидальная сортировка

Сортировка:
1. Быстрая сортировка (англ. quicksort)
2. Сортировка Шелла (англ. Shell sort)

Поиск:
1. Прямой поиск (он же Простой, он же Алгоритм грубой силы)
2. Алгоритм Бойера-Мура-Хорспула

И новенькое:
Пирамидальная сортировка

4Сен/090

Быстрая сортировка

Продолжаю публиковать алгоритмы. Уже есть Сортировка Шелла

А сегодня у нас: Быстрая сортировка (англ. quicksort)

28Авг/090

Сортировка Шелла

Начну собирать коллекцию алгоритмов.

Итак, прошу любить и жаловать: Сортировка Шелла (англ. Shell sort)