Heap Sort
Heap sort is works
by determining the largest (or smallest) element of the list, placing that at
the end (or beginning) of the list, then continuing with the rest of the list,
but accomplishes this task efficiently by using a data structure called a heap,
a special type of binary tree. Once the data list has been made into a heap,
the root node is guaranteed to be the largest(or smallest) element. When it is
removed and placed at the end of the list, the heap is rearranged so the
largest element remaining moves to the root. Using the heap, finding the next
largest element takes O(log n) time, instead of O(n) for a linear scan as in
simple selection sort. This allows Heap sort to run in O(n log n) time.
Complexity
·
It
is a well-known, traditional sorting algorithm you will be expected to know
·
Heap
sort is always O(n log n)
Quick sort is usually O(n log n) but in the worst case slows to O(n2)
Quick sort is usually O(n log n) but in the worst case slows to O(n2)
Quick
sort is generally faster, but Heap sort is better in time-critical applications
·
We
do the while loop n times (actually, n-1 times), because we remove one of the n
nodes each time
·
Removing
and replacing the root takes O(1) time
·
Therefore,
the total time is n times however long it takes the reheap method
·
To
reheap the root node, we have to follow one path from the root to a leaf node
(and we might stop before we reach a leaf)
·
The
binary tree is perfectly balanced
·
Therefore,
this path is O(log n) long
§
And
we only do O(1) operations at each node
§
Therefore,
reheaping takes O(log n) times
·
Since
we reheap inside a while loop that we do n times, the total time for the while
loop is n*O(log n), or O(n log n)
·
We
have seen that heapifying takes O(n log n) time
·
The
while loop takes O(n log n) time
·
The
total time is therefore O(n log n) + O(n log n)
This is the same as
O(n log n) time
Worst case
performance O(n log n)
Best case
performance Ω(n),O(n log n)
Average case
performance O(n log n)
Algorithm
HeapSort(int ar[], int n)
1. int i,j;
2. int lf, rt, mid, val, num;
3. val = (n-1)/2;
4. for j=val to 0 step -1
5. do
6. for i= val to 0 step
-1
7. do
8. lf =
(2*i)+1;
9. then
10. rt = (2*i)+2;
11. endif
12. if lf <= n and rt <= n
13. then
14. if ar[rt] >= ar[lf]
15. then
16. mid = rt;
17. else
18. mid = lf;
19. endif
20. else if(rt > n)
21. mid
= lf;
22. else
23. mid
= rt;
24. endif
25. if(ar[i] <
ar[mid])
26. then
27. num = ar[i];
28. ar[i]
= ar[mid];
29. ar[mid] = num;
30. endif
31. endfor
32. num = ar[0];
33. ar[0] = ar[n];
34. ar[n] = num;
35. endfor
Pseudo Code
HeapSort
BUILD_HEAP
heap-size (A) ←length [A]
for i ←
length[A]/2 down to 1 do
Heapify
(A, i)
HEAPSORT
BUILD_HEAP (A)
for i ← length (A) down to 2 do
exchange A[1] « A[i]
heap-size [A] ← heap-size [A] - 1
Heapify (A, 1)
Heapify
l ← left [i]
r← right [i]
if l ≤ heap-size [A] and A[l] >
A[i]
then largest ← l
else largest ← i
if r ≤ heap-size [A] and A[i] >
A[largest]
then largest ← r
if largest ≠ i
then exchange A[i] ↔A[largest]
Heapify (A, largest)
Source Code
#include <stdio.h>
#include <conio.h>
//Heapsort
void
HeapSort(int ar[], int n)
{
int
i,j;
int
lf, rt, mid, val, num;
val
= (n-1)/2;
for(j=val;j>=0;j--)
{
for(i=val;i>=0;i--)
{
lf
= (2*i)+1;
rt
= (2*i)+2;
if
((lf <= n) && (rt <= n))
{
if(ar[rt]
>= ar[lf])
{
mid
= rt;
}
else
{
mid
= lf;
}
}
else
{
if(rt
> n)
{
mid
= lf;
}
else
{
mid
= rt;
}
}
if
(ar[i] < ar[mid])
{
num
= ar[i];
ar[i]
= ar[mid];
ar[mid]
= num;
}
}
}
num
= ar[0];
ar[0]
= ar[n];
ar[n]
= num;
}
//Main Function
void
main(void)
{
int
i,n;
int
a[20];
clrscr();
printf("\n\tEnter
the Size (below 20) : ");
scanf("%d",&n);
for(
i=0 ;i<n;i++)
{
printf("\n\tEnter
Element at [%d] : ",i+1);
scanf("%d",&a[i]);
}
printf("\n\tOriginal :
");
for(i=0
;i<n;i++)
{
printf("%d
",a[i]);
}
for(i=n;
i>1; i--)
{
HeapSort(a,i-1);
}
printf("\n\tAfter
Sort : ");
for(i=0
;i<n;i++)
{
printf("%d ",a[i]);
}
getch();
}
Radix Sort
Radix sort is an
algorithm that sorts a list of fixed-size numbers of length k in O(n • k) time
by treating them as bit strings. We first sort the list by the least
significant bit while preserving their relative order using a stable sort. Then
we sort them by the next bit, and so on from right to left, and the list will
end up sorted. Most often, the counting sort algorithm is used to accomplish
the bitwise sorting, since the number of values a bit can have is minimal -
only '1' or '0'.
Complexity
·
Running
time for this example is:
·
T(n)
= Ө (d(n+k))
·
k
= number of buckets = 10(0 to 9).
·
n
= number of elements to be sorted = 15
·
d
= digits or maximum length of element = 2
·
Thus
in our example, the algorithm will take
·
T(n)
= Ө (d(n+k))
o = Ө (2(15+10))
o = Ө (50)
execution time.
·
Computational
complexity: classification is based on worst, average and best behavior of
sorting a list of size (n).
Algorithm
void radixsort(int a[],int n)
1. int rear[10],front[10],first,p,q,exp,k,i,y,j;
2. struct
3. {
4. int data;
5. int next;
6. }Temp[N];
7. for i=0 to n step 1
8. do
9. Temp[i].data=a[i];
10. Temp[i].next=i+1;
11. endfor
12. Temp[n-1].data=a[n-1];
13. Temp[n-1].next=-1;
14. first=0;
15. for k=1 to 2 step 1
16. do
17. for i=0 to 9 step 1
18. do
19. front[i]=-1;
20. rear[i]=-1;
21. endfor
22. while first!=-1
23. do
24. p=first;
25. first=Temp[first].next;
26. y=Temp[p].data;
27. exp=pow(10,k-1);
28. j=(y/exp)%10;
29. q=rear[j];
30. if q=-1)
31. then
32. front[j]=p;
33. else
34. Temp[q].next=p;
35. endif
36. rear[j]=p;
37. enddo
38. for j=0 to 10 and front[j]=-1
39. endfor
40. first=front[j];
41. while j<=9
42. do
43. for i=i+1 to 10 and front[i]=-1
44. endfor
45. if i<=9
46. then
47. p=i;
48. Temp[rear[j]].next=front[i]
49. endif
50. j=i;
51. enddo
52. Temp[rear[p]].next=-1;
53. endfor
54. for i=0 to n-1 step 1
55. do
56. a[i]=Temp[first].data;
57. first=Temp[first].next;
58. endfor
Pseudo Code
radixsort(int a[],int n)
iniatilize i,j,t,k;
i←1
define array b[n][100], bc[n];
while TRUE
do
for j←0 to n-1
do
bc[j]←0;
end for j
for j←0 to n-1
do
t←a[j]/i;
while t>9
do
t←t/10;
end while
b[t][bc[t]]←a[j];
bc[t]++;
end for j
if bc[0]==n
break;
t←0;
for j←0 to n-1
do
for k←0 to bc[j]
do
a[t]←b[j][k];
t++;
end for k
end for j
i¬i*10;
end while
Source Code
#define N 100
#include <stdio.h>
#include <conio.h>
#include <math.h>
//Radix
Sort
void
radixsort(int a[],int n)
{
int
rear[10],front[10],first,p,q,exp,k,i,y,j;
struct
{
int
data;
int
next;
}Temp[N];
for(i=0;i<n-1;i++)
{
Temp[i].data=a[i];
Temp[i].next=i+1;
}
Temp[n-1].data=a[n-1];
Temp[n-1].next=-1;
first=0;
for(k=1;k<=2;k++)
{
for(i=0;i<10;i++)
{
front[i]=-1;
rear[i]=-1;
}
while(first!=-1)
{
p=first;
first=Temp[first].next;
y=Temp[p].data;
exp=pow(10,k-1);
j=(y/exp)%10;
q=rear[j];
if(q==-1)
{
front[j]=p;
}
else
{
Temp[q].next=p;
}
rear[j]=p;
}
for(j=0;j<10&&front[j]==-1;j++);
first=front[j];
while(j<=9)
{
for(i=j+1;i<10&&front[i]==-1;i++)
;
if(i<=9)
{
p=i;
Temp[rear[j]].next=front[i]
;
}
j=i;
}
Temp[rear[p]].next=-1;
}
for(i=0;i<n;i++)
{
a[i]=Temp[first].data;
first=Temp[first].next;
}
}
//Main
Function
void
main()
{
int
n,a[20],i;
clrscr();
printf("\n\tEnter
the Size [below 100] : ");
scanf("%d",&n);
printf("\n\tEnter
Data, Positive Integer Only");
for(i=0;i<n;i++)
{
printf("\n\tEnter
Element at [%d] : ",i+1);
scanf("%d",&a[i]);
}
clrscr();
printf("\n\tOriginal
Data : ");
for(i=0;i<n;i++)
{
printf("
%d ",a[i]);
}
radixsort(a,n);
printf("\n\tAfter
Sort : ");
for(i=0;i<n;i++)
{
printf("
%d ",a[i]);
}
getch();
}
No comments:
Post a Comment