Пузырьковая сортировка

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

Быстродействие программы можно повысить, тщательно оптимизировав внутренний цикл, таким же образом можно оптимизировать метод сортировки вставками.На рисунке 5 представлена работа сортировки массива.

Рисунок5

 

Код реализации пузырьковой сортировки:

/* * Ввести целочисленный массив из N целых чисел. * Отсортировать этот массив по возрастанию методом пузырька */

#include<iostream>

usingnamespace std;

intmain ()

{ int *arr; // указатель для выделения памяти под массив

int size; // размер массива// Ввод количества элементов массива

cout<<"n = ";

cin>>size;

if (size<= 0) { // Размер масива должен быть положитлеьным

cerr<<"Invalidsize"<<endl;

return 1; }

arr = newint [size]; // выделение памяти под массив// заполнение массива

for (int i = 0; i< size; i++)

{ cout<<"arr["<<i<<"] = ";

cin>>arr[i];

} int temp; // временная переменная для обмена элементов местами// Сортировка массива пузырьком

for (int i = 0; i< size - 1; i++)

{ for

(int j = 0; j < size - i - 1; j++)

{ if (arr[j] >arr[j + 1]) { // меняем элементы местами

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp; } } } // Вывод отсортированного массива на экран

for (int i = 0; i< size; i++)

{ cout<<arr[i] <<" "; }

cout<<endl;

delete [] arr; // освобождениепамяти;

return 0; }

Результат сортировки:

Сортировка пузырьком – простейший алгоритм сортировки, применяемый чисто для учебных целей. Практического применения этому алгоритму нет, так как он не эффективен, особенно если необходимо отсортировать массив большого размера. К плюсам сортировки пузырьком относится простота реализации алгоритма.

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

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

Идея сортировки методом Шелла состоит в том, чтобы сортировать элементы, отстоящие друг от друга на некотором расстоянии step. Затем сортировка повторяется при меньших значениях step, и в конце процесс сортировки Шелла завершается при step = 1 (а именно обычной сортировкой вставками).

Код реализации:

#include "stdafx.h"
#include<iostream>
using namespace std;
int i, j, n, d, count;
void Shell(int A[], int n) //сортировка Шелла
{
d=n;
d=d/2;
while (d>0)
{
for (i=0; i<n-d; i++)
{
j=i;
while (j>=0 && A[j]>A[j+d])
{
count=A[j];
A[j]=A[j+d];
A[j+d]=count;
j--;
}
}
d=d/2;
}
for (i=0; i<n; i++) cout<<A[i]<<" "; //вывод массива
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
cout<<"Размер массива > "; cin>>n;
int *A= new int[n]; //объявление динамического массива
for (i=0; i<n; i++) //ввод массива
{ cout<<i+1<<" элемент > "; cin>>A[i]; }
cout<<"\nРезультирующий массив: ";
Shell(A, n);
delete [] A; //освобождение памяти
system("pause>>void");
}

Анализ этого алгоритма – сложная математическая задача, у которой до сих пор нет полного решения. В настоящий момент неизвестно, какая последовательность расстояний даёт наилучший результат, но известно, что расстояния не должны быть кратными друг другу. Это необходимо, чтобы очередной проход не объединял две последовательности, до того никак не пересекавшиеся. На самом деле желательно, чтобы последовательности пересекались как можно чаще.

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

Quicksort (быстрая сортировка) – суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получим отсортированный массив. Сложность алгоритма зависит от входных данных.

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

Рисунок6

Реализация кода:

 

#include <stdio.h>
#include <stdlib.h>
// Функция быстрой сортировки
void quickSort(int *numbers, int left, int right)
{
int pivot; // разрешающий элемент
int l_hold = left; //левая граница
int r_hold = right; // правая граница
pivot = numbers[left];
while (left < right) // пока границы не сомкнутся
{
while ((numbers[right] >= pivot) && (left < right))
right--; // сдвигаем правую границу пока элемент [right] больше [pivot]
if (left!= right) // если границы не сомкнулись
{
numbers[left] = numbers[right]; // перемещаем элемент [right] на место разрешающего
left++; // сдвигаем левую границу вправо
}
while ((numbers[left] <= pivot) && (left < right))
left++; // сдвигаем левую границу пока элемент [left] меньше [pivot]
if (left!= right) // если границы не сомкнулись
{
numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
right--; // сдвигаем правую границу вправо
}
}
numbers[left] = pivot; // ставим разрешающий элемент на место
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива
quickSort(numbers, left, pivot - 1);
if (right > pivot)
quickSort(numbers, pivot + 1, right);
}
int main()
{
int a[10];
// Заполнение массива случайными числами
for (int i = 0; i<10; i++)
a[i] = rand() % 20 - 10;
// Вывод элементов массива до сортировки
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
printf("\n");
quickSort(a, 0, 9); // вызов функции сортировки
// Вывод элементов массива после сортировки
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
printf("\n");
getchar();
return 0;
}

Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента — один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел.