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

Для решения многих задач необходимо упорядочить данные по определенному признаку. Этот процесс называется сортировкой. Сортировка используется в массивах.

Элементы массива можно сортировать:

по возрастанию (каждый следующий элемент больше предыдущего а [1] < a [2] < a [3] и т.д.);
по неубыванию (каждый следующий элемент не меньше предыдущего а [1] <= a [2] <= a [3] и т.д.);
по убыванию (каждый следующий элемент меньше предыдущего а [1] > a [2] > a [3] и т.д.);
по невозрастанию (каждый следующий элемент не больше предыдущего а [1] >= a [2] >= a [3] и т.д.).

Существующие методы сортировки обычно разбивают на три класса, в зависимости от лежащего в их основе приема:

сортировка выбором;
сортировка обменами;
сортировка включениями (вставками).

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

Сортировка простым выбором

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

void select (int x[ ], int n)

{ int i, j, k;

int q, tmp;

for (i=0; i<n-1; i++)

{ q=0; k=I; tmp=x[i]

for (j=i+s; j<n; j++)

{ if (x[j]<tmp) { k=j;

tmp=x[j]

q=1;

} }

if (q´=0)

{ x[k]=x[i]; x[i]=tmp; }

}

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

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

Первый вариант данной сортировки

void buble (int x[ ], int n)

{ int i, j, tmp;

for (i=1; i<n; i++)

for (j=n-1; j>=i; j--)

if (x[j-1]>x[j]) {tmp=x[j-1];

x[j-1]=x[j]

x[j]=tmp;

}

Второй вариант сортировки

void buble1 (int x[ ], int n)

{ int i, j, tmp, q;

m: q=0;

for (i=0; i<n-1; i++)

if (x[i]>x[i+1])

{ tmp=x[i];

x[i]=x[i+1];

x[i+1]=tmp;

q=1;

}

if (q´= 0) goto m;

}

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

Идея этого метода базируется на последовательном пополнении ранее упорядоченных элементов. На первом шаге сортируется первые два элемента. Далее берется третий элемент и для него подбирается такое место в отсортированной части массива, что упорядоченность не нарушается. К трем упорядоченным добавляется четвертый. И так продолжается до тех пор, пока к n-1 ранее упорядоченным элементам не присоединяется последний.

void insert (int x[ ], int n)

{ int i, j, tmp;

for (i=1; i<n; i++)

{ tmp=x[i]

for (j=i-1; j>=0 && tmp<x[j]; j--)

x[j+1]=x[j];

x[j+1]=tmp;

} }

Существуют и другие разновидности сортировок:

–сортировка методом Шелла;

–сортировка методом Хоара;

–сортировка слияниями.

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

Алгоритмы поиска, как и алгоритмы сортировки, являются основными алгоритмами обработки данных прикладных задач.

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

–линейный (последовательный) поиск;
–бинарный поиск;
–интерполяционный поиск.

Последовательный поиск

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

Классический алгоритм поиска элемента q в массиве а[n]:

1 шаг: установить начальный индекс равный 1 (j=1)

2 шаг: проверить условие q=a[j], если оно выполняется, то сообщить, что искомое значение находится в массиве на j-о м месте и прервать работу. В противном случае продолжить работу;

3 шаг: увеличить индекс на 1;

4 шаг: проверить условие j<n+1, если выполняется, то вернуться к шагу 2, в противном случае выдать сообщение, что данное значение q в массиве не содержится

int ssearch (int q, int a[ ], int n)

{ int j;

for (j=0; j<n; j++)

if (q= =a[j]) return j;

return -1;

}

Бинарный поиск (двоичный)

Метод половинного деления. Применяется только для предварительно упорядоченных массивов.

Даны целое число х и массив а[n], отсортированный в порядке неубывания. Идея бинарного метода состоит в том, чтобы проверить, является ли х средним элементом массива. Если да, то ответ получен, если нет, то возможны два случая:

а) х < среднего значения, тогда из рассмотрения исключаются все элементы массива, расположенных в нем правее среднего;

б) х > среднего значения, тогда из рассмотрения исключается левая половина массива.

Средний элемент в том и другом случае в дальнейшем не рассматривается. На каждом шаге отсекается та часть массива, где заведомо не может быть обнаружен элемент х.

int binar (int q, int a[ ], int n)

{ int l, r, m;

l=0; r=n-1;

for (; l<=r;)

{ m=(l+r)/2;

if (q<a[m]) r=m-1;

else if (q>a[m]) l=m+1;

else return m;

}

return -1;

}

Интерполяционный поиск

Если k находится между k_e и k_r, то номер очередного элемента для сравнения определяется формулой:

m=l+(r-l)*(k-k_e)/(k_r-k_e)

Пример: Два упорядоченных массива объединить в один, тоже упорядоченный.

#include<iostream.h>

#define n 5

void main()

{ int a[n], b[n], c[2*n], I, j, k;

for (i=0;i<n; i++)

cin>>a[i];

for(j=0; j<n; j++)

cin>>b[j];

i=0; j=0; k=0;

do { if (a[i]<b[j]) c[k++]=a[i++];

else if (a[i]>b[j]) c[k++]=b[j++];

else { c[k++]=a[i++];

c[k++]=b[j++]

}

while ((i<n) && (i<j));

while (i<n) c[k++]=a[i++];

while(i<n) c[k++]=b[j++];

for(i=0; i<2*n; i++)

cout<<c[i]<<’\t’;

cout<<’\n’;

}

Пример задачи с сортировкой (Решение задачи можно посмотреть, скачав файл "Задача-12"):

Дан одномерный массив. Найти количество различных чисел в этом массиве. Использовать функцию сортировки.

#include<iostream.h>
#include<math.h>
#include<conio.h>
#define n 10
void sort(int mas[n])
{int i,j,c;
for (j=0;j<n;j++)
{for (i=n-1;i>=1;i--)
if (mas[i]>mas[i-1]) {c=mas[i-1];
mas[i-1]=mas[i];
mas[i]=c;
}
}
}
main()
{int i, kol=0, m[n];
clrscr();
cout<<"Vvedite elementy massiva"<<'\n';
for (i=0; i<n; i++)
cin>>m[i];
cout<<"Ishodniy massiv:"<<'\n';
for(i=0;i<n;i++)
cout<<m[i]<<" ";
cout<<'\n';

sort (m);
cout<<"Otsortirovanniy massiv:"<<'\n';
for (i=0; i<n; i++)
cout<<m[i]<<" ";
cout<<'\n';
for (i=0; i<n; i++)
if (m[i]!=m[i+1]) kol++;
cout<<"Kolichestvo razlicnih chisel= "<<kol;
return 0;
}

Пример задачи с интерполяционным поиском(Решение задачи можно посмотреть, скачав файл "Задача-13"):

Два упорядоченных массива объединить в один, тоже упорядоченный.

#include<iostream.h>
#include<conio.h>
#define n 5

interpolationSearch(int a[], int key, int n1)
{ int left = 0;
int right = n1 - 1;
int mid;
while ((a[left] < key) && (key < a[right]))
{
mid = left + (key - a[left]) * (right - left) / (a[right] - a[left]);
if (a[mid] < key) left = mid + 1;
   else if (a[mid] > key) right = mid - 1;
       else return mid;
}
if (a[left] == key) return left;
   else if (a[right] == key) return right;
       else return -1;
}
void main()
{ int a[n], b, i, j, k;
clrscr();
cout<<"vvedite otsortirovanniy po vozrastaniyu massiv iz "<<n<<" elementov"<<endl;
for (i=0;i<n; i++)
cin>>a[i];
cout<<"vvedite chislo dlya poiska: " ;
cin>>k;
j=interpolationSearch(a,k,n);
if (j==-1) cout<<"chislo "<<k<<" v massive otsutstvuet"<<endl;
   else cout<<"chislo "<<k<<" nahoditcya v position "<<j<<endl;
}

Среда, 08.05.2024, 10:34
Приветствую Вас Гость

Язык программирования С++