Smartzworld.com Smartworld.

asia
return 0;

Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in
the graph.

Applications of Depth First Search

Depth-first search (DFS) is an algorithm (or technique) for traversing a graph.
Following are the problems that use DFS as a bulding block.
1) For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair
shortest path tree.
2) Detecting cycle in a graph
A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check
for back edges. (See this for details)
3) Path Finding
We can specialize the DFS algorithm to find a path between two given vertices u and z.
i) Call DFS(G, u) with u as the start vertex.
ii) Use a stack S to keep track of the path between the start vertex and the current vertex.
iii) As soon as destination vertex z is encountered, return the path as the
contents of the stack
See this for details.
4) Topological Sorting
See this for details.
5) To test if a graph is bipartite
We can augment either BFS or DFS when we first discover a new vertex, color it opposited its parents, and
for each other edge, check it doesn’t link two vertices of the same color. The first vertex in any connected
component can be red or black! See this for details.
6) Finding Strongly Connected Components of a graph A directed graph is called strongly connected if
there is a path from each vertex in the graph to every other vertex. (See this for DFS based algo for finding
Strongly Connected Components)

7) Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a
maze by only including nodes on the current path in the visited set.)

UNIT – IV

SORTING TECHNIQUES
Sorting in general refers to various methods of arranging or ordering things based on criterias
(numerical, chronological, alphabetical, hierarchical etc.). There are many approaches to sorting data
and each has its own merits and demerits.

Bubble Sort:
Bubble Sort is probably one of the oldest, easiest, straight-forward, inefficient sorting algorithms. Bubble
sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted,
comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass
through the list is repeated until no swaps are needed, which indicates that the list is sorted. The
algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only
uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple,
most of the other sorting algorithms are more efficient for large lists. Bubble sort is not a stable sort
which means that if two same elements are there in the list, they may not get their same order with

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

respect to each other.

Bubble Sort Algorithm:

Step 1: Repeat Steps 2 and 3 for i=1 to 10
Step 2: Set j=1
Step 3: Repeat while j<=n
(A) if a[i] < a[j]
Then interchange a[i] and a[j]
[End of if]
(B) Set j = j+1
[End of Inner Loop]
[End of Step 1 Outer Loop]
Step 4: Exit
Source Code:
#include<stdio.h>
#include<conio.h>
void main()
{
int i,n,temp,j,arr[25];
clrscr();
printf("Enter the number of elements in the Array: ");
scanf("%d",&n);
printf("\nEnter the elements:\n\n");
for(i=0 ; i<n ; i++)
{
printf(" Array[%d] = ",i);
scanf("%d",&arr[i]);
}
for(i=0 ; i<n ; i++)
{
for(j=0 ; j<n-i-1 ; j++)
{
if(arr[j]>arr[j+1]) //Swapping Condition is Checked
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
printf("Array Elements after sorting: ");
for(i=0 ; i<n ; i++)
{
printf("%5d",arr[i]);
}
}

output:
/*
Enter the number of elements in the Array: 10

Enter the elements:

Array[0] = 23
Array[1] = 65
Array[2] = 78
Array[3] = 22
Array[4] = 12
Array[5] = 09
Array[6] = 69
Array[7] = 34
Array[8] = 21
Array[9] = 56

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Array Elements after sorting: 9 12 21 22 23 34 56 65 69 78

*/
Step-by-step example:
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number
using bubble sort. In each step, elements written in bold are being compared. Three passes will be
required.
First Pass:

(51428) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

(15428) ( 1 4 5 2 8 ), Swap since 5 > 4

(14528) ( 1 4 2 5 8 ), Swap since 5 > 2

(14258)

( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:

(14258) (14258)

(14258) ( 1 2 4 5 8 ), Swap since 4 > 2

(12458) (12458)

(12458) (12458)
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm
needs one whole pass without any swap to know it is sorted.
Third Pass:

(12458) (12458)

(12458) (12458)

(12458) (12458)

(12458) (12458)

Time Complexity:
Worst Case Performance O(N2)
Best Case Performance O(N2)
Average Case Performance O(N2)
Selection Sort:
The algorithm divides the input list into two parts: the sub-list of items already sorted, which is built up
from left to right at the front (left) of the list, and the sub-list of items remaining to be sorted that
occupy the rest of the list. Initially, the sorted sub-list is empty and the unsorted sub-list is the entire
input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order)
element in the unsorted sub-list, exchanging it with the leftmost unsorted element (putting it in sorted
order), and moving the sub-list boundaries one element to the right.
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time
complexity, making it inefficient on large lists.
Selection Sort Algorithm and Pseudo Code:
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
/* a[0] to a[n-1] is the array to sort */
int i,j;
int iMin;
/* advance the position through the entire array */
/* (could do j < n-1 because single element is also min element) */
for (j = 0; j < n-1; j++) {
/* find the min element in the unsorted a[j .. n-1] */
/* assume the min is the first element */
iMin = j;
/* test against elements after j to find the smallest */
for ( i = j+1; i < n; i++) {
/* if this element is less, then it is the new minimum */
if (a[i] < a[iMin]) {
/* found new minimum; remember its index */
iMin = i;
}
}

/* iMin is the index of the minimum element. Swap it with the current
position */
if ( iMin != j ) {
swap(a[j], a[iMin]);
}
}
Source Code:
# include <stdio.h>
# include <conio.h>
void main()
{
int i,j,a[20],n,minindex,temp;
clrscr();
printf("\n Enter array size:");
scanf("%d",&n);
printf("\n Enter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n The elements after sorting are:");
for(i=0;i<n;i++)
{
minindex=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[minindex])
minindex=j;
}
temp=a[i];
a[i]=a[minindex];
a[minindex]=temp;
printf("%5d",a[i]);
}
getch();
}

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Output:
Enter array size:6
Enter the elements:96 94 81 56 76 45
The elements after sorting are: 45 56 76 81 94 96
Step-by-step example:
Here is an example of this sort algorithm sorting five elements:

64 25 12 22 11

11 25 12 22 64

11 12 25 22 64

11 12 22 25 64

11 12 22 25 64

Time Complexity:
Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops
depend on the data in the array. Selecting the lowest element requires scanning all n elements (this
takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element
requires scanning the remaining n − 1 elements and so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2
∈ O(n2) comparisons. Each of these scans requires one swap for n − 1 elements (the final element is
already in place).
Worst Case Performance O(N2)
Best Case Performance O(N2)
Average Case Performance O(N2)
Insertion Sort:
An algorithm consider the elements one at a time, inserting each in its suitable place among those
already considered (keeping them sorted). Insertion sort is an example of an incremental algorithm. It
builds the sorted sequence one number at a time. This is a suitable sorting technique in playing card
games. Insertion sort provides several advantages:

 Simple implementation
 Efficient for (quite) small data sets
 Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is
O(n + d), where d is the number of inversions
 More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such
as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
 Stable; i.e., does not change the relative order of elements with equal keys
 In-place; i.e., only requires a constant amount O(1) of additional memory space
 Online; i.e., can sort a list as it receives it
Source Code:
#include<stdio.h>
#include<conio.h>
void insertion_sort(int a[],int n)
{
int temp,pos,i;
for(i=0;i<n;i++)
{
temp=a[i];
pos=i;
while(pos>0&&a[pos-1]>temp)
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

{
a[pos]=a[pos-1];
--pos;
}
a[pos]=temp;
}
printf("\nElements after sorting....\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
}
void main()
{
int i,n,a[20];
clrscr();
printf("\nEnter the n:");
scanf("%d",&n);
printf("\nEnter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nElements before sorting:\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
insertion_sort(a,n);
getch();
}
Output:
Enter the n:5
Enter the elements: 1 3 6 25 0
Elements before sorting: 1 3 6 25 0
Elements after sorting: 0 1 3 6 25
Step-by-step example:

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Suppose, you want to sort elements in ascending as in above figure. Then,

1. Step 1: The second element of an array is compared with the elements that appear before it
(only first element in this case). If the second element is smaller than first element, second
element is inserted in the position of first element. After first step, first two elements of an array
will be sorted.
2. Step 2: The third element of an array is compared with the elements that appears before it (first
and second element). If third element is smaller than first element, it is inserted in the position
of first element. If third element is larger than first element but, smaller than second element, it
is inserted in the position of second element. If third element is larger than both the elements, it
is kept in the position as it is. After second step, first three elements of an array will be sorted.
3. Step 3: Similary, the fourth element of an array is compared with the elements that appear
before it (first, second and third element) and the same procedure is applied and that element is
inserted in the proper position. After third step, first four elements of an array will be sorted.

If there are n elements to be sorted. Then, this procedure is repeated n-1 times to get sorted list of
array.
Time Complexity:
Worst Case Performance O(N2)
Best Case Performance(nearly) O(N)
Average Case Performance O(N2)
Quick Sort:
Quick sort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average,
makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this
behavior is rare. Quick sort is often faster in practice than other O(n log n) algorithms. It works by first of
all by partitioning the array around a pivot value and then dealing with the 2 smaller partitions
separately. Partitioning is the most complex part of quick sort. The simplest thing is to use the first value
in the array, a[l] (or a[0] as l = 0 to begin with) as the pivot. After the partitioning, all values to the left of
the pivot are <= pivot and all values to the right are > pivot. The same procedure for the two remaining
sub lists is repeated and so on recursively until we have the entire list sorted.
Advantages:
 One of the fastest algorithms on average.
 Does not need additional memory (the sorting takes place in the array - this is called in-place
processing).
Disadvantages: The worst-case complexity is O(N2)
Quick Sort Procedure:
Quick sort is a divide and conquer algorithm. Quick sort first divides a large list into two smaller sub-lists:
the low elements and the high elements. Quick sort can then recursively sort the sub-lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while
all elements with values greater than the pivot come after it (equal values can go either way).
After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-list of elements with smaller values and separately
the sub-list of elements with greater values.
The base case of the recursion is lists of size zero or one, which never need to be sorted.
Source Code:
#include<stdio.h>
#include<conio.h>
void quick_sort(int,int);
int partition(int,int);
void interchange(int,int);
int a[25];
void main()
{
int i,n;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

clrscr();
printf("Enter no of elements:");
scanf("%d",&n);
printf("Enter elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quick_sort(0,n);
printf("Elements after sorting:");
for(i=0;i<n;i++)
printf("%3d",a[i]);
getch();
}
int partition(int low,int high)
{
int pivot=a[low];
int up=low,down=high;
do
{
do
{
up=up+1;
}while(a[up]<pivot);
do
{
down=down-1;
}while(a[down]>pivot);
if(up<down)
interchange(up,down);
}while(up<down);
a[low]=a[down];
a[down]=pivot;
return down;
}
void quick_sort(int low,int high)
{
int pivotpos;
if(low<high)
{
pivotpos=partition(low,high);
quick_sort(low,pivotpos-1);
quick_sort(pivotpos+1,high);

}
}

void interchange(int i,int j)

{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;

}
Output:
Enter no of elements:5
Enter elements:1 65 0 32 66
Elements after sorting: 0 1 32 65 66
Step-by-step example:

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

1 2 3 4 5 6 7 8 9 10 11 12 13 Remarks
38 08 16 06 79 57 24 56 02 58 04 70 45
Pivot 08 16 06 Up 57 24 56 02 58 Dn 70 45 Swap up and
down
Pivot 08 16 06 04 57 24 56 02 58 79 70 45
Pivot 08 16 06 04 Up 24 56 Dn 58 79 70 45 Swap up and
down
Pivot 08 16 06 04 02 24 56 57 58 79 70 45
Pivot 08 16 06 04 02 Dn Up 57 58 79 70 45 Swap pivot
and down
24 08 16 06 04 02 38 56 57 58 79 70 45
Pivot 08 16 06 04 Dn Up 56 57 58 79 70 45 Swap pivot
and down
(02 08 16 06 04 24) 38 (56 57 58 79 70 45)
Pivot 08 16 06 04 Up
dn
Pivot Up 06 Dn Swap up and
down
Pivot 04 06 16
Pivot 04 Dn Up Swap pivot
and down
06 04 08
Pivot Dn Up Swap pivot
and down
04 06
(02 04 06 08 16 24 38) (56 57 58 79 70 45)
Pivot Up 58 79 70 Dn Swap up and
down
Pivot 45 58 79 70 57
Pivot Dn Up 79 70 57 Swap pivot
and down
(45) 56 (58 79 70 57)
Pivot Up 70 Dn Swap up and
down
Pivot 57 70 79
Pivot Dn Up 79 Swap down
and pivot
(57) 58 (70 79)
Pivot Up Swap pivot
Dn and down
02 04 06 08 16 24 38 45 56 57 58 70 79 The array is
sorted
Time Complexity:

Worst Case Performance O(N2)

Best Case Performance(nearly) O(N log2 N)

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Average Case Performance O(N log2 N)

Merge Sort:
Merge sort is based on Divide and conquer method. It takes the list to be sorted and divide it in half to
create two unsorted lists. The two unsorted lists are then sorted and merged to get a sorted list. The
two unsorted lists are sorted by continually calling the merge-sort algorithm; we eventually get a list of
size 1 which is already sorted. The two lists of size 1 are then merged.
Merge Sort Procedure:
This is a divide and conquer algorithm.
This works as follows :
1. Divide the input which we have to sort into two parts in the middle. Call it the left part and right part.
Example: Say the input is -10 32 45 -78 91 1 0 -16 then the left part will be -10 32 45 -78 and the right
part will be 91 1 0 6.
2. Sort each of them separately. Note that here sort does not mean to sort it using some other method.
We use the same function recursively.
3. Then merge the two sorted parts.
Input the total number of elements that are there in an array (number_of_elements). Input the array
(array[number_of_elements]). Then call the function MergeSort() to sort the input array. MergeSort()
function sorts the array in the range [left,right] i.e. from index left to index right inclusive. Merge()
function merges the two sorted parts. Sorted parts will be from [left, mid] and [mid+1, right]. After
merging output the sorted array.
MergeSort() function:
It takes the array, left-most and right-most index of the array to be sorted as arguments. Middle index
(mid) of the array is calculated as (left + right)/2. Check if (left<right) cause we have to sort only when
left<right because when left=right it is anyhow sorted. Sort the left part by calling MergeSort() function
again over the left part MergeSort(array,left,mid) and the right part by recursive call of MergeSort
function as MergeSort(array,mid + 1, right). Lastly merge the two arrays using the Merge function.
Merge() function:
It takes the array, left-most , middle and right-most index of the array to be merged as arguments.
Finally copy back the sorted array to the original array.

Source Code:
#include<stdio.h>
#include<conio.h>
void merge(int a[],int start,int mid,int end)
{
int b[20],k=0,i,j;
i=start;
j=mid+1;
while((i<mid+1)&&(j<end+1))
{
if(a[i]<a[j])
{
b[k]=a[i];
i++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
while(i<mid+1)
{
b[k]=a[i];
k++;
i++;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

}
while(j<end+1)
{
b[k]=a[j];
j++;
k++;
}
for(i=0;i<k;i++)
{
a[start]=b[i];
start++;
}
}
void merge_sort(int a[20],int start,int end)
{
int mid;
if(start<end)
{
mid=(start+end)/2;
merge_sort(a,start,mid);
merge_sort(a,mid+1,end);
merge(a,start,mid,end);
}
}
void main()
{
int i,n,a[20],start=0,end;
clrscr();
printf("\nEnter the n:");
scanf("%d",&n);
printf("\nEnter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nElements before sort:\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
end=n-1;
merge_sort(a,start,end);
printf("\nElements after sort:\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
getch();
}

Output:
Enter the n:5
Enter the elements:102 321 365 320 111
Elements before sort:
102 321 365 320 111
Elements after sort:
102 111 320 321 365
Step-by-step example:

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Time Complexity:
Worst Case Performance O(N log2 N)
Best Case Performance(nearly) O(N log2 N)
Average Case Performance O(N log2 N)
Heap Sort:
The heap sort algorithm can be divided into two parts. In the first step, a heap is built out of the data. In
the second step, a sorted array is created by repeatedly removing the largest element from the heap,
and inserting it into the array. The heap is reconstructed after each removal. Once all objects have been
removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by
choosing a min-heap or max-heap in step one. Heap sort can be performed in place. The array can be
split into two parts, the sorted array and the heap.
The (Binary) heap data structure is an array object that can be viewed as a nearly complete binary tree.

Heap Sort Algorithm:

Step 1. Build Heap – O(n)-Build binary tree taking N items as input, ensuring the heap structure property
is held, in other words, build a complete binary tree. Heapify the binary tree making sure the binary tree
satisfies the Heap Order property.
Step 2. Perform n deleteMax operations – O(log(n))- Delete the maximum element in the heap – which

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

is the root node, and place this element at the end of the sorted array.
Source Code:
# include <stdio.h>
# include <conio.h>
void main()
{
int b[10],n,i,j,c,p,temp;
clrscr();
printf("\n Enter array size:");
scanf("%d",&n);
printf("\n Enter elements:");
for(i=0;i<n;i++)
scanf("%d",&b[i]);
for(i=1;i<n;i++)
{
c=i;
do
{
p=(c-1)/2;
if(b[p]<b[c])
{
temp=b[p];
b[p]=b[c];
b[c]=temp;
}
else
break;
c=p;
}while(c!=0);
}
for(j=n-1;j>=0;j--)
{
temp=b[0];
b[0]=b[j];
b[j]=temp;
p=0;
do
{
c=2*p+1;
if((b[c]<b[c+1])&&c<j-1)
c++;
if(b[p]<b[c]&&c<j)
{
temp=b[p];
b[p]=b[c];
b[c]=temp;
}
else
break;
p=c;
}while(c<j);
}
printf("\n Elements after sorting are:");
for(i=0;i<n;i++)
printf("%5d",b[i]);
getch();

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Output:
Enter array size:5
Enter elements:1 63 25 32 14
Elements after sorting are: 1 14 25 32 63
Step-by-step example:
Given an array of 6 elements: 15, 19, 10, 7, 17, 16, sort it in ascending order using heap sort.
Steps:
1. Consider the values of the elements as priorities and build the heap tree.
2. Start deleteMin operations, storing each deleted element at the end of the heap array.
After performing step 2, the order of the elements will be opposite to the order in the heap tree.
Hence, if we want the elements to be sorted in ascending order, we need to build the heap tree
in descending order - the greatest element will have the highest priority.
Note that we use only one array , treating its parts differently:
a. when building the heap tree, part of the array will be considered as the heap,
and the rest part - the original array.
b. when sorting, part of the array will be the heap, and the rest part - the sorted array.
This will be indicated by colors: white for the original array, blue for the heap and red for the sorted
array
Here is the array: 15, 19, 10, 7, 17, 6
A. Building the heap tree
The array represented as a tree, complete but not ordered:

Start with the rightmost node at height 1 - the node at position 3 = Size/2.
It has one greater child and has to be percolated down:

After processing array[3] the situation is:

Next comes array[2]. Its children are smaller, so no percolation is needed.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

The last node to be processed is array[1]. Its left child is the greater of the children.
The item at array[1] has to be percolated down to the left, swapped with array[2].

As a result the situation is:

The children of array[2] are greater, and item 15 has to be moved down further, swapped with array[5].

Now the tree is ordered, and the binary heap is built.

B. Sorting - performing deleteMax operations:

1. Delete the top element 19.

1.1. Store 19 in a temporary place. A hole is created at the top

1.2. Swap 19 with the last element of the heap.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

As 10 will be adjusted in the heap, its cell will no longer be a part of the heap.
Instead it becomes a cell from the sorted array

1.3. Percolate down the hole

1.4. Percolate once more (10 is less that 15, so it cannot be inserted in the previous hole)

Now 10 can be inserted in the hole

2. DeleteMax the top element 17

2.1. Store 17 in a temporary place. A hole is created at the top

2.2. Swap 17 with the last element of the heap.

As 10 will be adjusted in the heap, its cell will no longer be a part of the heap.
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Instead it becomes a cell from the sorted array

2.3. The element 10 is less than the children of the hole, and we percolate the hole down:

2.4. Insert 10 in the hole

3. DeleteMax 16
3.1. Store 16 in a temporary place. A hole is created at the top

3.2. Swap 16 with the last element of the heap.

As 7 will be adjusted in the heap, its cell will no longer be a part of the heap.
Instead it becomes a cell from the sorted array

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

3.3. Percolate the hole down (7 cannot be inserted there - it is less than the children of the hole)

3.4. Insert 7 in the hole

4. DeleteMax the top element 15

4.1. Store 15 in a temporary location. A hole is created.

4.2. Swap 15 with the last element of the heap.

As 10 will be adjusted in the heap, its cell will no longer be a part of the heap.
Instead it becomes a position from the sorted array

4.3. Store 10 in the hole (10 is greater than the children of the hole)

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

5. DeleteMax the top element 10.

5.1. Remove 10 from the heap and store it into a temporary location.

5.2. Swap 10 with the last element of the heap.

As 7 will be adjusted in the heap, its cell will no longer be a part of the heap. Instead it becomes a cell
from the sorted array

5.3. Store 7 in the hole (as the only remaining element in the heap

7 is the last element from the heap, so now the array is sorted

Time Complexity:
Worst Case Performance O(N log2 N)
Best Case Performance(nearly) O(N log2 N)
Average Case Performance O(N log2 N)
Radix/Bucket Sort:
Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of
buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by
recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in
the most to least significant digit flavor.
Bucket sort works as follows:
1. Set up an array of initially empty "buckets".
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

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.
Radix/Bucket Procedure:
1. Reading the list of elements. Calling the Radix sort function.
2. Checking the biggest number (big) in the list and number of digits in the biggest number (nd).
3. Inserting the numbers in to the buckets based on the one’s digits and collecting the numbers
and again inserting in to buckets based on the ten’s digits and soon…
4. Inserting and collecting is continued ‘nd’ times. The elements get sorted.
5. Displaying the elements in the list after sorting.
Source code:
#include<conio.h>
#include<stdio.h>
void radix_sort(int a[20],int n)
{
int bucket[10][10],ctr[10]={0};
int big,nd,i,j,k,l,div=1,b_no;
big=a[0];
i=1;
while(i<n)
{
if(a[i]>big)
big=a[i];
i++;
} /*checking the biggest number*/
nd=0;
while(big>0)
{
nd=nd+1;
big=big/10;
} /*checking number of digits in the biggest number*/
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
b_no=((a[j]/div)%10);
bucket[b_no][ctr[b_no]]=a[j];
ctr[b_no]=ctr[b_no]+1;
} /*Inserting the numbers in to the buckets*/
div=div*10;
j=0;
for(k=0;k<10;k++)
{
for(l=0;l<ctr[k];l++)
{
a[j]=bucket[k][l];
j++;
}
ctr[k]=0;
} /*collecting the elements from the buckets*/
}
}
void main()
{
int i,n,a[20];
printf("\nEnter n:");
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

scanf("%d",&n);
printf("\nEnter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nElements before sorting:\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
radix_sort(a,n);
printf("\nElements after sorting:\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
getch();
}
Output:
Enter n:5
Enter the elements:013 323 526 314 33
Elements before sorting:
13 323 526 314 33
Elements after sorting:
13 33 314 323 526
Step-by-step example:
Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66
Sorting by least significant digit (1s place) gives:
170, 90, 802, 2, 24, 45, 75, 66
Sorting by next digit (10s place) gives:
802, 2, 24, 45, 66, 170, 75, 90
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
It is important to realize that each of the above steps requires just a single pass over the data,
since each item can be placed in its correct bucket without having to be compared with other
items.
Some LSD radix sort implementations allocate space for buckets by first counting the number of
keys that belong in each bucket before moving keys into those buckets. The number of times
that each digit occurs is stored in an array. Consider the previous list of keys viewed in a
different way:

170, 045, 075,090, 002, 024, 802, 066

The first counting pass starts on the least significant digit of each key, producing an array of
bucket sizes:
2 (bucket size for digits of 0: 170, 090)
2 (bucket size for digits of 2: 002, 802)
1 (bucket size for digits of 4: 024)
2 (bucket size for digits of 5: 045, 075)
1 (bucket size for digits of 6: 066)

A second counting pass on the next more significant digit of each key will produce an array of
bucket sizes:
2 (bucket size for digits of 0: 002, 802)
1 (bucket size for digits of 2: 024)
1 (bucket size for digits of 4: 045)
1 (bucket size for digits of 6: 066)
2 (bucket size for digits of 7: 170, 075)
1 (bucket size for digits of 9: 090)

A third and final counting pass on the most significant digit of each key will produce an array of
bucket sizes:

jntuworldupdates.org Specworld.in