Алгоритми за сортирања

 

Сортирањето претставува процес на преуредување на дадено множество објекти по некој однапред зададен критериум.

Кога пребаруваме некој телефонски број во именик или збор во речник се користи знаењето за тоа како се организирани податоците во именикот или речникот (алфабетски подредени т.е сортирани). Ако податоците не се подредени во некој логички редослед, пронаоѓањето на некој податок претставува вистинска тешкотија или одзема многу време.

Целта на сортирањето е да се олесни и забрза пребарувањето на објектите.

 Сортирањето е проблем за кој постојат голем број разновидни алгоритми наречени алгоритми за сортирање кои меѓусебно се разликуваат според  времето потребно за извршување како и потребните мемориски ресурси односно сложеност.

Формална дефиниција Нека земеме една произволна низа S={sk1, sк2, ..., skn} составена од n ≥ 0 елементи од некое универзално множество U. Целта на сортирањето е да се реорганизираат елементите од низата S создавајќи некоја нова низа S’ во која елементите ќе бидат подредени.

 Алготитми за сортирање  (организирани според главниот медот на кој се засновани)

· Сортирање со избор – (eng. Selection sort)

· Сортирање со метод на меурчиња – (eng. Bubble sort)

· Сортирање со мешање – (eng. Merge sort)

· Сортирање со вметнување –(eng. Insertion sort)

· Сортирање со замена – (eng. Exchange sort)

· Сортирање со распределба – (eng. Distribution sort)

 Ке обработиме неколку од нив.

 Алгоритми за сортирање со избор (eng Selection Sort)

Основна идеја: За реализација на овој алгоритам потребни се n-1 премини во низата. Во секој чекор на алгоритмот вршиме линеарно барање низ несортираниот дел од низата барајќи ја позицијата на најголемиот/најмалиот елемент. Тој елемент го поставуваме на крајната/првата позиција вршејќи замена со елементот кој се наоѓа на таа позиција, после секој чекор должината на низата над која се извршува алгоритмот ја намалуваме за еден

Пример Да се сортира низата  со помош на методата за сортирање со избор.

Алгоритмот може да се опише со следните чекори:

1. Со линеарно пребарување најди го минималниот / максималниот елемент во низата.
2. Замени ги првиот / последниот елемент од низата и минималниот /максималниот
3. Повтори ја постапката за преостанатите n-1 елементи, потоа за n-2 итн се додека не остане само еден т.е. најголемиот / најмалиот елемент.

Подредување во растечки редослед

#include<iostream>
using namespace std;
int main()
{
int n, a[50], i, j, pom, min, chk, index;
cout<<"Vnesi broj na elementi n= : ";
cin>>n;
cout<<"Vnesi "<<n<<" elementi: ";
for(i=0; i<n; i++)
cin>>a[i];
for(i=0; i<(n-1); i++)
{
chk=0;
min = a[i];
for(j=i+1; j<n; j++)
{
if(min>a[j])
{
min = a[j];
chk++;
index = j;
}
}
cout<<"Step "<<i+1<<": ";
for(j=0; j<n; j++)
cout<<a[j]<<" ";
cout<<endl;

if(chk!=0)
{ pom = a[i];
a[i] = min;
a[index] = pom;
}
}
cout<<"\nPodredena niza :\n";
for(i=0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}

Output
Vnesi broj na elementi n= : 5
Vnesi 5 elementi: -9  23  -123  0  45
Step 1: -9  23  -123  0  45
Step 2: -123  23  -9  0  45
Step 3: -123  -9  23  0  45
Step 4: -123  -9  0   23 45
Pоdredena niza :
-123 -9 0 23 45

Со функција 

#include<bits/stdc++.h>
using namespace std;

void print(int arr[], int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}

void selectionSort(int arr[], int n)
{

int i,j,min_in;
for(i=0;i<n;i++)
{
min_in = i;
for(j=i+1;j<n;j++)
if (arr[j] < arr[min_in])
min_in = j;
swap(arr[i],arr[min_in]);
}
}

int main( )
{
int arr[] = {5,4,10,1,6,2};
int i,j,n,temp;
n = sizeof(arr)/sizeof(int);
cout<<"Unsorted Array :";
print(arr,n);
selectionSort(arr,n);
cout<<"Sorted Array :";
print(arr,n);
return(0);
}

 Сортирање со метода на меурче (eng Bubble Sort)

Основна идеја За да се сортира низата a₁, ..., a_n со оваа метода потребно е да се направат n-1 премини во низата. Во секој премин се споредуваат парови соседни елементи, ако елементите кои се споредуваат не се во бараниот редослед , тие си ги заменуваат местата. После првиот премин најголемиот елемент од низата ќе дојде на првата позиција од низата (избива на површината како меурче во чаша вода ). После k премини над низата последните k елементи од низата се на “точната” позиција и не треба повеќе да се разгледуваат.

Овој алгоритам има квадратна сложеност O(n2 ) бидејќи и во најдобар случај кога низата е сортирана потребни се истиот број на споредби за да со сигурност се потврди дека низата е сортирана.

Да се сортира низата  -2,45,0,11,-9 со помош на методата на меурче:

Прва итерација  (Compare and Swap)

1. Почнувајќи од првиот индекс, споредете ги првиот и вториот елемент.

2. Ако првиот елемент е поголем од вториот елемент, тие се заменуваат.

3. Сега, споредете ги вториот и третиот елемент. Заменете ги ако не се во редослед.

4. Горенаведениот процес продолжува до последниот елемент

Преостаната итерација 
1. Истиот процес продолжува и за останатите повторувања.

2. По секое повторување, на крајот се става најголемиот елемент меѓу несортираните елементи.

Во секое повторување, споредбата се одвива до последниот несортиран елемент.

Низата се подредува кога сите несортирани елементи се поставени на нивните правилни позиции.

#include <iostream>
using namespace std;
int main()
{
int n,pom,i,j;
int a[100];
cout<<"Vnesi go n = ";
cin>>n;
cout<<"Vnesi gi elementite na nizata ";
for(i=0; i<n; i++)
cin>>a[i];
for(i=n-1; i>0; i--)
{
for(j=0; j<i; j++)
{
 if(a[j]>a[j+1])
{ pom=a[j];
   a[j]=a[j+1];
   a[j+1]=pom;
  }
 }
}

cout<<"Podredenata niza e"<<endl;
for(i=0; i<n; i++)
cout<<a[i]<<" ";
return 0;
}

Со функција
#include <bits/stdc++.h>
using namespace std;
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{ int i, j;
   for (i = 0; i < n - 1; i++)
   for (j = 0; j < n - i - 1; j++)
   if (arr[j] > arr[j + 1])
   swap(arr[j], arr[j + 1]);
}

// Function to print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

int main()
{ int arr[] = { 5, 8, 4, 2, 1};
int N = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, N);
cout << "Sorted array: \n";
printArray(arr, N);
return 0;
}

Алгоритми за сортирање со мешање (eng Merge Sort)

Основна идеја И овој алгоритам е од типот раздели па владеј, најпрво низата која треба да се сортира се разделува на половина т.е. на две поднизи и потоа секоја подниза се сортира независно, на крај двете сортирани поднизи се мешаат со што се добива оригиналното решение. Пример Со помош на метод на претопување да се сортира низата 3,1,4,1,5,9,2,6,5,4.

Во секој чекор низата се разделува на половина и рекурзивно се повикува процедурата за сортирање за левата и десната подниза,и потоа процедурата за мешање.

Алгоритмот може да се опише со следните чекори:

1.Раздели ја низата на две поднизи со должина n/2 ,n/2

2.Рекурзивно сортирај ја секоја од двете поднизи.
3.Измешај ги сортираните поднизи за да се добие крајниот резултат.

#include <iostream>

using namespace std;

/* Merge two subarrays L and M into arr */
void merge(int arr[], int p, int q, int r)
{ /* Create L ← A[p..q] and M ← A[q+1..r] */
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];

/* Maintain current index of sub-arrays and main array */
int i, j, k;
i = 0;  j = 0;  k = p;

/* Until we reach either end of either L or M, pick larger among
elements L and M and place them in the correct position at A[p..r] */
while (i < n1 && j < n2) {
if (L[i] <= M[j])
{ arr[k] = L[i];
i++; }
else
{ arr[k] = M[j];
j++; }
k++;
}

/* When we run out of elements in either L or M,
pick up the remaining elements and put in A[p..r] */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}

/* Divide the array into two subarrays, sort them and //merge them */
void mergeSort(int arr[], int l, int r) {
if (l < r) {

/* m is the point where the array is divided into two subarrays */
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

// Merge the sorted subarrays
merge(arr, l, m, r);
}
}

// Print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
cout << "Sorted array: \n";
printArray(arr, size);
return 0;
}