Shell Sort – Shellsort, also known as Shell sort or Shell's
method is an in-place comparison sort. It generalizes an exchanging sort, such
as insertion or bubble sort, by allowing
the comparison and exchange of elements that lie far apart. Its first version
was published by Donald Shell. The running time of Shellsort is heavily
dependent on the gap sequence it uses. For many practical variants, determining
their time complexity remains an open problem.
Complexity :
Worst case performance O(n^2)
Best case performance O(N)
Average case performance depends
on gap sequence
Algorithm.
function shellsort(int arr[],int
n)
int
last,tmp,limit,temp,k
int
mid=n/2
while
mid>0
do
last=0;
limit=n-mid;
while
last==0
do
tmp=0;
for
k=0 to limit-1 step 1
do
if
arr[k]>arr[k+mid]
then
temp=arr[k]
arr[k]=arr[k+mid]
arr[k+mid]=temp
tmp=k
endif
endfor
limit=tmp-mid
if
tmp==0 then
then
last=1
endif
enddo
mid=mid/2
enddo
end
Source Code
#include <stdio.h>
#include <conio.h>
//Shell Sort
void shellsort(int arr[],int n)
{
int
last,tmp,limit,temp,k;
int
mid=n/2;
while(mid>0)
{
last=0;
limit=n-mid;
while(last==0)
{
tmp=0;
for(k=0;k<limit;k++)
{
if(arr[k]>arr[k+mid])
{
temp=arr[k];
arr[k]=arr[k+mid];
arr[k+mid]=temp;
tmp=k;
}
}
limit=tmp-mid;
if(tmp==0)
{
last=1;
}
}
mid=mid/2;
}
}
//Main Funtion
void
main()
{
int
i;
int
Arr[20],n;
clrscr();
printf("\n\tEnter
Size of Array below 20 : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n\tEnter
Array Element at [%d] : ",i);
scanf("%d",&Arr[i]);
}
printf("\n\tOriginal
Array : ");
for(i=0;i<n;i++)
{
printf("%d
",Arr[i]);
}
shellsort(Arr,n);
printf("\n\tAfter
Sort : ");
for(i=0;i<n;i++)
{
printf("%d
",Arr[i]);
}
getch();
}
Bucket Sort – Bucket sort is a divide and
conquer sorting algorithm that generalizes Counting sort by partitioning an
array into a finite number of buckets. Each bucket is then sorted individually,
either using a different sorting algorithm, or by recursively applying the
bucket sorting algorithm. A variation of this method called the single buffered
count sort is faster than quicksort.[citation needed] Due to the fact that
bucket sort must use a limited number of buckets it is best suited to be used
on data sets of a limited scope. Bucket sort would be unsuitable for data such
as social security numbers - which have a lot of variation.
Bucket sort works as follows:
1. Set up an array of
initially empty "buckets."
2. Scatter: Go over
the original array, putting each object in its bucket.
3. Sort each
non-empty bucket.
4. Gather: Visit the
buckets in order and put all elements back into the original array.
Complexity :
•
Worst case performance O(n2)
•
Average case performance O(n
+ k)
•
Worst case space complexity O(n
* k)
Algorithm.
function BucktSort(int A[], int
n)
int
bucks[10][MAX]={{0}},f=0,i,j,m,k
i=1
while(f!=n)
do
f=0;
for
j=1 to n-1
do
bucks[(A[j]/i)%10][j]
= A[j]
if (A[j]/i)%10
== 0 then
then
f++
endif
endfor
if
f == n
then
print
“Sorted Values "
for
j=0 to n-1
do
print
A[j]
enddo
endif
m=0
for
j=0 to 9
do
fork=0
to n-1
{
if
bucks[j][k] > 0
then
A[m]
= bucks[j][k]
bucks[j][k]
= 0
m++
endif
endfor
endfor
i=i*10
enddo
end
Source Code
#include <stdio.h>
#include <conio.h>
#define MAX 20
void BucktSort(int A[], int n)
{
int
bucks[10][MAX]={{0}},f=0,i,j,m,k;
for(i=1;f!=n;i*=10)
{
f=0;
for(j=0;j<n;j++)
{
bucks[(A[j]/i)%10][j]
= A[j];
if
( (A[j]/i)%10 == 0 )
{
f++;
}
}
if
(f == n)
{
printf("\nSorted
Values ");
for(j=0
; j < n ; j++)
{
printf("%d
" , A[j]);
}
}
for(j=0,m=0;j<10;j++)
{
for(k=0;k<n;k++)
{
if(
bucks[j][k] > 0 )
{
A[m]
= bucks[j][k];
bucks[j][k]
= 0 ;
m++;
}
}
}
}
}
//Main
Function
void
main()
{
int
A[MAX] ;
int i, n ;
clrscr();
printf("\nEnter
Size of Array [Below 20] : ");
scanf("%d",&n);
for(i=0
; i < n ; i++)
{
scanf("%d",&A[i]);
}
printf("\nOrigianl
Values : ");
for(i=0
; i < n ; i++)
{
printf("%d
", A[i]);
}
BucktSort(A,n);
getch();
}
No comments:
Post a Comment