Binary Insertion Sort

// O(nlogn) – O(n2)
void BinInsSort(int m[],int n)
{
int i,left,right,tmp,mid;
for(i=1;i<n;++i)
{
left = 0;
right = i;
tmp = m[i];
while(left<right)
{
mid = (left+right)/2;
if(m[mid]<tmp) left=mid+1;
else right = mid;
}
for(int j=i;j>left;–j)
swap(m[j],m[j-1]);
}

}

Shaker Sort

O(n2)

void ShakerSort(int m[],int n)
{
int left,right,idx,i;
left = 0;
right = n-1;
idx = n-1;
do
{
for(i=right;i>0;i–)
if(comparer(m[i-1],m[i]))
{
swap(m[i],m[i-1]);
idx = i;
}
left = idx;
for(i=left;i<right;i++)
if(comparer(m[i],m[i+1]))
{
swap(m[i],m[i+1]);
idx = i;
}
right = idx;
}
while(left<right);
}

Bubble Sort

O(n) – O(n2)

void BubbleSort(int arr[],int n)
{
int i,idx,right;
right = n-1;
while(right>0)
{
idx = 0;
for(i=0;i<right;i++)
{
if(comparer(arr[i],arr[i+1]))
{
swap(arr[i],arr[i+1]);
idx = i;
}
}
right = idx;
}
}

Shell Sort

complexity: unknown

void ShellSort(int arr[],int n)
{
int h[]={5,3,1};
int h_len = 3;
for(int i=0;i<h_len;i++)
{
Insertion(arr,n,h[i]);
}
}

void Insertion(int arr[],int n,int len)
{
int idx,tmp;
for(int i=len;i<n;i+=len)
{
idx = i;
tmp = arr[i];
while(idx>0 && comparer(arr[idx-len],tmp))
{
arr[idx] = arr[idx-len];
idx-=len;
}
arr[idx]=tmp;
}
}

Quick Sort (recursion)

O(n Log (n) ) – O(n2)

void QSort(int arr[],int left,int right)
{
int holdLeft,holdRight,midValue;
holdLeft = left;
holdRight = right;
midValue = arr[(left+right)/2];

do
{

while(comparer(midValue,arr[holdLeft])) holdLeft++;
while(comparer(arr[holdRight],midValue)) holdRight–;

if(holdLeft<=holdRight) swap(arr[holdLeft++],arr[holdRight--]);
}

while(holdLeft<holdRight);

if(left<holdRight) QSort(arr,left,holdRight);

if(holdLeft<right) QSort(arr,holdLeft,right);

}

Insertion Sort

O(n) – O(n2)
void InsertionSort(int arr[],int n)
{
int idx,tmp;
for(int i=1;i<n;i++)
{
idx = i;
tmp = arr[i];
while(idx>0 && comparer(arr[idx-1],tmp))
{
arr[idx] = arr[idx-1];
idx–;
}
arr[idx]=tmp;
}
}

Selection Sort

THe complexity of best case is the same with worst case’s ones : O(n2)

void SelectionSort(int arr[],int n)
{
int idx;
for(int i=0;i<n-1;i++)
{
idx=i;
for(int j=i+1;j<n;j++)
if(comparer(arr[idx],arr[j]))
idx = j;
if(idx>i)
swap(arr[idx],arr[i]);
}
}

Exchange Sort

O(n) – O(n2)

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