Сортировка « Записки программиста

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;
			}
		}
	}
}

Метки записи: Example, Java, Алгоритмы, Сортировка Нет комментариев

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)

Метки записи: Example, Java, Сортировка 6 Комментарии

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]);
	}
}

Метки записи: C++, Сортировка Нет комментариев

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);
}

Метки записи: C++, Сортировка Нет комментариев

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]);
}

Метки записи: C++, Сортировка Нет комментариев

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;                             // место найдено, вставить элемент
        }
    }

Метки записи: C++, Сортировка Нет комментариев

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;

Метки записи: Pascal, Сортировка Нет комментариев

10Окт/092