各種ソートアルゴリズムのまとめ
目次
ソートの挿入
1.ソートの直接挿入
2.shellソート
ソートの選択
1.直接選択
2.ヒープのソート
並べ替え
1.泡立ちソート
2.クイックソート
その他のソート
1.集計ソート
2.基数ソート
ソートの挿入
1.ソートの直接挿入
2.shellソート
ソートの選択
1.直接選択
2.ヒープのソート
並べ替え
1.泡立ちソート
2.クイックソート
その他のソート
1.集計ソート
2.基数ソート
ソートの挿入
1.ソートの直接挿入
2.shellソート
ソートの選択
1.直接選択
2.ヒープのソート
並べ替え
1.泡立ちソート
2.クイックソート
その他のソート
1.集計ソート
2.基数ソート
ソートの挿入
1.ソートの直接挿入
/* ：
*
* O(n^2) O(n) O(n^2) O(1)
*/
#include
#include
using namespace std;
template
void InsertSort(vector& v)
{
int i;
for (i=1; i 0 && v[pos] < v[pos-1]) {
T temp = v[pos];
v[pos] = v[pos-1];
v[pos-1] = temp;
pos--;
}
}
}
int main()
{
vectorv{1,-5,5,6,6,2,5,3,2,1};
InsertSort(v);
for (auto x : v)
cout << x << ' ';
cout << endl;
return 0;
}
2.shellソート
/*
*
*
* O(n^1.3) O(n^1.25) O(1.6*n^1.25) O(1)
*/
#include
#include
using namespace std;
template
void ShellSort(vector& v)
{
int i;
int pos;
T temp;
int gap = v.size()/2;
while(gap > 0) {
for (i=gap; i= gap && v[pos-gap] > temp) {
v[pos] = v[pos-gap];
pos -= gap;
}
v[pos] = temp;
}
gap /= 2;
}
}
int main()
{
vectorv{2,2,2,2,2,2,1,1,1,1,1,1};
ShellSort(v);
for (auto x : v)
cout << x << ' ';
cout << endl;
return 0;
} ソートの選択
1.直接選択
/*
*
*
* O(n^2) O(n^2) O(n^2) O(1)
*/
#include
#include
using namespace std;
template
void SelectSort(vector& v)
{
int len = v.size();
int i,j;
for (i=len-1; i>=0; i--) {
int max = 0;
for (j=0; j<=i; j++)
if (v[j] > v[max])
max = j;
T temp = v[i];
v[i] = v[max];
v[max] = temp;
}
}
int main()
{
vectorv{1,5,2,0,3,2,3,-1,-56,23,1,2,0,2,5,-10};
SelectSort(v);
for (auto x : v)
cout << x << ' ';
cout << endl;
return 0;
}
2.ヒープのソート
/*
*
*
* O(nlog2n) O(nlog2n) O(nlog2n) O(1)
*/
#include
#include
using namespace std;
template
void MaxHeap(vector& v,int index,int len)
{
int left = 2*index + 1;
int right = 2*index + 2;
int largest = index;
if (left < len && v[left] > v[largest])
largest = left;
if (right < len && v[right] > v[largest])
largest = right;
if (index != largest) {
T temp = v[index];
v[index] = v[largest];
v[largest] = temp;
MaxHeap(v,largest,len);
}
}
template
void CreateHeap(vector& v)
{
int i;
for (i=v.size()/2; i>=0; i--)
MaxHeap(v,i,v.size());
}
template
void HeapSort(vector& v)
{
CreateHeap(v);
int i;
for (i=v.size()-1; i>=0; i--) {
T temp = v[0];
v[0] = v[i];
v[i] = temp;
MaxHeap(v,0,i);
}
}
int main()
{
vector v{1,5,2,0,-5,2,3,5,12};
HeapSort(v);
for (auto x : v)
cout << x << ' ';
cout << endl;
return 0;
}
並べ替え
1.泡立ちソート
/*
*
*
* O(n^2) O(n) O(n^2) O(1)
*/
#include
#include
using namespace std;
template
void BubbleSort(vector& v)
{
int i,j;
for (i=v.size(); i>0; i--) {
bool flag = true; //
for(j=0; j v[j+1]) {
T temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
flag = false;
}
if (flag)
break;
}
}
int main()
{
vectorv{1,2,3,4,5,6,7};
BubbleSort(v);
for (auto x : v)
cout << x << ' ';
cout << endl;
return 0;
}
2.クイックソート
/*
*
*
* O(nlog2n) O(nlog2n) O(n^2) O(nlog2n)
*/
#include
#include
using namespace std;
template
int QSortPartition(vector& v,int left,int right)
{
T key = v[left];
while (left < right) {
while(left < right && v[right] >= key)
right--;
v[left] = v[right];
while(left < right && v[left] <= key)
left++;
v[right] = v[left];
}
v[left] = key;
return left;
}
template
void QSort(vector& v,int left,int right)
{
if (left < right) {
int pivot = QSortPartition(v,left,right);
QSort(v,left,pivot-1);
QSort(v,pivot+1,right);
}
}
int main()
{
vectorv{1,2,5,0,-5,1,63,12,0,-125};
QSort(v,0,v.size()-1);
for (auto x : v)
cout << x << ' ';
cout << endl;
return 0;
}
その他のソート
1.集計ソート
/*
*
*
* O(nlog2n) O(nlog2n) O(nlog2n) O(n)
*/
#include
#include
using namespace std;
template
void Merge(vector& v,int left,int mid,int right)
{
int i = left;
int j = mid+1;
T key;
vector temp;
while (i<=mid && j<=right) {
key = v[i] < v[j] ? v[i++] : v[j++];
temp.push_back(key);
}
while (i<=mid)
temp.push_back(v[i++]);
while (j<=right)
temp.push_back(v[j++]);
i = left;
for (auto x : temp)
v[i++] = x;
}
template
void MergeSort(vector& v,int left,int right)
{
if (left < right) {
int mid = (left + right) >> 1;
MergeSort(v,left,mid);
MergeSort(v,mid+1,right);
Merge(v,left,mid,right);
}
}
int main()
{
vectorv{1,4,2,0,-6,56,-100,45,234,1,1,1};
MergeSort(v,0,v.size()-1);
for (auto x : v)
cout << x << ' ';
cout << endl;
return 0;
}
2.基数ソート
/*
*
*
* O(d(r+n)) O(d(n+rd)) O(d(r+n)) O(rd+n)
*/
#include
#include
#include
using namespace std;
void RadixSort(vector& v)
{
int a[10]; // 。
vector b(v.size()); //
int max = v[0];
for (auto x : v)
if (x > max)
max = x;
int exp = 1;
int i;
while (max / exp > 0) {
memset(a,0,sizeof(a));
//
for (auto x : v)
a[x/exp%10]++;
for (i=1; i<10; i++)
a[i] += a[i-1];
//
for (i=v.size()-1; i>=0; i--)
b[--a[v[i]/exp%10]] = v[i];
//
v.clear();
v.assign(b.begin(),b.end());
exp *= 10;
}
}
int main()
{
vectorv{1,2,6,34,234,1,2,3,1234556,45,767,87};
RadixSort(v);
for (auto x : v)
cout << x << ' ';
cout << endl;
return 0;
}