Сортировка массива

сортировка массива

Сортировка массива очень типичная задача на работу с массивами, наверное каждому (или почти каждому) прийдет сразу идея отсортировать массив простым перебором. Если это не так, то специально для вас мы добавили в пост видео, на котором Румынский ансамбль обыгрывает различные сортировки массива. Но в этой статье мы рассмотрим не только самый примитивный метод, доступный рядовому выпускнику ПТУ, но и довольно сложные алгоримы.


Сортировка пузырьком (Bubble sort)

Подробно пузырьку, больший элемент массива поднимается "вверх".

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

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

Реализация

void bubble(int* a, int n)
{
  for (int i=n-1; i>=0; i--)
  {
    for (int j=0; j<i; j++)
    {
      if (a[j] > a[j+1])
      {
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
      }
    }
  }
}
.cpp .pas .py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод пузырька оказывается крайне неэффективным на любом входном наборе данных. Единственный плюс алгоритма - простота его исполнения.


Сортировка вставками (Insertion sort)

Выбираем и вставляем элемент в нужную позицию.

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

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора.

Реализация

void insert_sort(int *a, int n)
{
    int i, j, value;
 
    for(i = 1; i < n; i++)
    {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--)
        {
            a[j + 1] = a[j];
        }
        a[j + 1] = value;
    }
}
.cpp .pas .py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод оказывается эффективным только на маленьких массивах (не более 10), на массивах больших размеров, в силу асимптотической сложности n^2, алгоритм оказывается крайне не эффективным.


Сортировка выбором (Selection sort)

Упорядочиваем постепенно массив, заполняя первую позицию неупорядоченной части минимальным элементом из неупорядоченной части.

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

Шаги алгоритма: находим номер минимального значения в текущем списке, производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции), теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы. Для реализации устойчивости алгоритма необходимо в пункте 2 минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов.

Реализация

void select_sort(int *a, int length){
    for (int i = 0; i < length - 1; i++) {
    /* устанавливаем начальное значение минимального индекса */
                    int min_i = i;
	    /* находим индекс минимального элемента */
    	    for (int j = i + 1; j < length; j++) {
		if (a[j] < a[min_i]) {
			min_i = j;
		}
	    }
                    /* меняем значения местами */
	    int temp = array[i];
	    array[i] = array[min_i];
	    array[min_i] = temp;
    }
}
.cpp .pas .py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод оказывается эффективным только на маленьких массивах (не более 10), на массивах больших размеров, в силу асимптотической сложности n^2, алгоритм оказывается крайне не эффективным.


Сортировка слиянием (Merge sort)

Упорядочиваем списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.

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

Для решения задачи сортировки эти три этапа выглядят так: 1) Сортируемый массив разбивается на две части примерно одинакового размера; 2) Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом; 3) Два упорядоченных массива половинного размера соединяются в один. 1.1. - 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным). 3.1. Соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива. Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда: 3.2. Слияние двух подмассивов в третий результирующий массив. На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.3. "Прицепление" остатка. Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.

Реализация

void merge(int *a, int low, int mid, int high)
{
	// Variables declaration. 
	int *b = new int[high+1-low];
	int h,i,j,k;
	h=low;
	i=0;
	j=mid+1;
	// Merges the two array's into b[] until the first one is finish
	while((h<=mid)&&(j<=high))
	{
		if(a[h]<=a[j])
		{
			b[i]=a[h];
			h++;
		}
		else
		{
			b[i]=a[j];
			j++;
		}
		i++;
	}
	// Completes the array filling in it the missing values
	if(h>mid)
	{
		for(k=j;k<=high;k++)
		{
			b[i]=a[k];
			i++;
		}
	}
	else
	{
		for(k=h;k<=mid;k++)
		{
			b[i]=a[k];
			i++;
		}
	}
	// Prints into the original array
	for(k=0;k<=high-low;k++) 
	{
		a[k+low]=b[k];
	}
	delete[] b;
}
void merge_sort(int *a, int low, int high)		
{// Recursive sort ...
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		merge_sort(a, low,mid);
		merge_sort(a, mid+1,high);
		merge(a, low,mid,high);
	}
}
.cpp .pas .py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод оказывается крайне эффективным, однако требуется выделение дополнительной памяти.


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

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.

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

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

  1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
  2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
    1. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
    2. Вычисляется индекс опорного элемента m.
    3. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
    4. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
    5. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
    6. Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.
  3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
  4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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

Реализация

void quicksort(int* a, int first, int last)
{
    int i = first, j = last, x = a[(first + last) / 2];
    do {
        while (a[i] < x) i++;
        while (a[j] > x) j--;
 
        if(i <= j) {
            if (i < j) swap(a[i], a[j]);
            i++;
            j--;
        }
    } while (i <= j);
    if (i < last)
        quicksort(a, i, last);
    if (first < j)
        quicksort(a, first,j);
}
.cpp .pas .py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод показывает высокую эффективноть, при этом он не требует расходов на дополнительную память. Однако, в худшем случае алгоритм оказывается крайне медленным (O(n2)).


Источники:
  • "The Art of Computer Programming, vol.3. Sorting and Searching," 2-ed Donald E. Knuth
  • "Introduction to Algorithms" Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
  • "An Introduction to the Analysis of Algorithms" Robert Sedgewick, Phillipe Flajolet.

↑ Расскажите друзьям о статье


Comments system Cackle

© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 25.07.16)

Рейтинг@Mail.ru