Алгоритмы сортировки на C++

С++

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

Алгоритм пузырьковой сортировки


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

void BubbleSort(int *massiv, int size)
{
  int temp;
  for (int i = 1; i < size; i++) 
  {
    for (int j = 0; j < size-1; j++) 
    {
      if (massiv[j] > massiv[j+1]) 
	  {
		temp = massiv[j];      
		massiv[j] = massiv[j+1];
		massiv[j+1] = temp;
	  }      
    } 
  }
}
void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
BubbleSort(massiv, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Алгоритмы сортировки на C++ Пузырьковая сортировка

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


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

void SelectionSort(int *massiv, int size)
{
int temp;
int i,j;
for (i = 0; i < size - 1; i++)
{
temp=massiv[i];
for (j = i-1; j>=0 && massiv[j]>temp; j--)
{
massiv[j+1] = massiv[j];
}
massiv[j+1] = temp;
}
}
void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
SelectionSort(massiv, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

C++ Алгоритм вставками

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


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

void DirectSelectionSort(int *massiv, int size)
{
int min, temp;
for (int i = 0; i < size - 1; i++)
{
min = i;
for (int j = i + 1; j < size; j++)
{
if (massiv[j] < massiv[min])
min = j;
}
temp = massiv[i];
massiv[i] = massiv[min];
massiv[min] = temp;
}
}
void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
DirectSelectionSort(massiv, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Результат работы программы

Отсортированный массив

Алгоритм сортировки прямым включением


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

void DirectInclusionSort(int *massiv, int size)
{
for (int i = 0; i < size; i++)
{
int temp=massiv[i];
int index=i;
while ((index>0) && (massiv[index-1]>temp))
{
massiv[index]=massiv[index-1];
index--;
}
massiv[index]=temp;
}
}
void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
DirectInclusionSort(massiv, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Результат работы программы

C++ Алгоритм сортировки прямым включением

Алгоритм сортировки слиянием


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

void Merge(int *massiv, int first, int last)
{
int middle, start, end, j;
int *mas=new int[last+1];
middle=(first+last)/2;
start=first;
end=middle+1;
for(j=first; j<=last; j++)
if ((start<=middle) && ((end>last) || (massiv[start]<massiv[end])))
{
mas[j]=massiv[start];
start++;
}
else
{
mas[j]=massiv[end];
end++;
}
for (j=first; j<=last; j++)
massiv[j]=mas[j];
delete[]mas;
}

void MergeSort(int *massiv, int first, int last)
{
if (first<last)
{
MergeSort(massiv, first, (first+last)/2);
MergeSort(massiv, (first+last)/2+1, last);
Merge(massiv, first, last);
}
}

void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
MergeSort(massiv, 0, size-1);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Результат работы программы

C++Алгоритм сортировки слиянием

Алгоритм шейкерной сортировки (перемешиванием) 


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

void Swap(int *massiv, int size)
{
int temp;
temp=massiv[size];
massiv[size]=massiv[size-1];
massiv[size-1]=temp;
}

void ShakerSort(int *massiv, int Start, int size)
{
int Left, Right, i;
Left=Start;
Right=size-1;
while (Left<=Right)
{
for (i=Right; i>=Left; i--)
if (massiv[i-1]>massiv[i]) Swap(massiv, i);
Left++;
for (i=Left; i<=Right; i++)
if (massiv[i-1]>massiv[i]) Swap(massiv, i);
Right--;
}
}

void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
ShakerSort(massiv, 1, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Результат работы программы

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

Алгоритм гномьей сортировки


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

void GnomeSort(int *massiv, int size)
{
int i=1, j=2;
while (i<size)
{
if (massiv[i-1]<massiv[i]) {
i=j;
j++;
}
else
{
int temp=massiv[i];
massiv[i]=massiv[i-1];
massiv[i-1]=temp;
i--;
if (i==0) {
i=j;
j++;
}
}
}
}

void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
GnomeSort(massiv, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Результат работы программы

C++ гномья сортировка

Алгоритм пирамидальной сортировки


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

void siftDown(int *massiv, int root, int bottom)
{
int maxIndex;
int done = 0;
while ((root * 2 <= bottom) && (!done))
{
if (root * 2 == bottom)
maxIndex = root * 2;
else if (massiv[root * 2] > massiv[root * 2 + 1])
maxIndex = root * 2;
else
maxIndex = root * 2 + 1;
if (massiv[root] < massiv[maxIndex])
{
int temp = massiv[root];
massiv[root] = massiv[maxIndex];
massiv[maxIndex] = temp;
root = maxIndex;
}
else
done = 1;
}
}

void PyramidSort(int *massiv, int size)
{
for (int i = (size / 2) - 1; i >= 0; i--)
siftDown(massiv, i, size - 1);
for (int i = size - 1; i >= 1; i--)
{
int temp = massiv[0];
massiv[0] = massiv[i];
massiv[i] = temp;
siftDown(massiv, 0, i - 1);
}
}

void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
PyramidSort(massiv, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Результат работы программы

C++ Пирамидальная сортировка

Алгоритм сортировки Шелла


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

int increment(int *massiv, int size)
{
int p1, p2, p3, s;
p1 = p2 = p3 = 1;
s = -1;
do
{
if (++s % 2)
{
massiv[s] = 8*p1 - 6*p2 + 1;
}
else
{
massiv[s] = 9*p1 - 9*p3 + 1;
p2 *= 2;
p3 *= 2;
}
p1 *= 2;
}
while(3*massiv[s] < size);
return s > 0 ? --s : 0;
}

void ShellSort(int *massiv, int size)
{
int inc, i, j, seq[40];
int s;
s = increment(seq, size);
while (s >= 0)
{
inc = seq[s--];
for (i = inc; i < size; ++i)
{
int temp = massiv[i];
for (j = i; (j >= inc) && (temp < massiv[j-inc]); j -= inc)
{
massiv[j] = massiv[j - inc];
}
massiv[j] = temp;
}
}
}

void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
ShellSort(massiv, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Результат работы программы

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

Алгоритм быстрой сортировки с рекурсией

#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

void QuickSortR(int *massiv, int size) {
int i = 0, j = size-1;
int temp, p;
p = massiv[size>>1];
do {
while (massiv[i] < p) i++;
while (massiv[j] > p) j--;
if (i <= j) {
temp = massiv[i];
massiv[i] = massiv[j];
massiv[j] = temp;
i++;
j--;
}
} while (i<=j);
if (j > 0) QuickSortR(massiv, j);
if (size > i) QuickSortR(massiv+i, size-i);
}

void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
QuickSortR(massiv, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Результат работы программы

С++ Алгоритм быстрой сортировки рекурсия

Алгоритм быстрой сортировки (сортировка Хоара)

#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

#define MAXSTACK 2048

void QuickSort(int *massiv, int size) {
int i, j;
int lb, ub;
int lbstack[MAXSTACK], ubstack[MAXSTACK];
int stackpos = 1;
int ppos;
int pivot;
int temp;
lbstack[1] = 0;
ubstack[1] = size-1;
do {
lb = lbstack[ stackpos ];
ub = ubstack[ stackpos ];
stackpos--;
do {
ppos = ( lb + ub ) >> 1;
i = lb;
j = ub;
pivot = massiv[ppos];
do {
while ( massiv[i] < pivot ) i++;
while ( pivot < massiv[j] ) j--;
if ( i <= j ) {
temp = massiv[i];
massiv[i] = massiv[j];
massiv[j] = temp;
i++; j--;
}
} while ( i <= j );
if ( i < ppos ) {
if ( i < ub ) {
stackpos++;
lbstack[ stackpos ] = i;
ubstack[ stackpos ] = ub;
}
ub = j;
} else {
if ( j > lb ) {
stackpos++;
lbstack[ stackpos ] = lb;
ubstack[ stackpos ] = j;
}
lb = i;
}
} while ( lb < ub );
} while ( stackpos != 0 );
}

void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
QuickSort(massiv, size);
cout<<"Отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}

Результат работы программы

С++ Алгоритм быстрой сортировки

Стандартная функция сортировки sort в C++


#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <algorithm>
using namespace std;

void main()
{
setlocale(LC_ALL,"Rus");
int size, i;
int *massiv;
srand(time(NULL));
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
for (i=0; i<size; i++)
{
massiv[i]=rand()%100;
cout<<massiv[i]<<" ";
}
cout<<endl;
sort(massiv, massiv+100);
cout<<"отсортированный массив"<<endl;
for (i=0; i<size; i++)
{
cout<<massiv[i]<<" ";
}
delete[] massiv;
cout<<endl;
system("pause");
}
<pre>

Результат работы программы со стандартной функцией sort

sort стандартная функция C++

9248

Leave a Reply

Ваш адрес email не будет опубликован.