Experiment 7 -B
Aim: Write a program in C to implement selection sorting.
Objective: To make the students familiar with the concept of sorting given elements and also
introduce different types of sorting.
Algorithm:Selection_sort(A, N)
Let A be a linear array with N elements.
Step 1: Repeat steps 2 to 4 for k = 1 to N-1
Step 2: set MIN := A[k]
Position := k
Step 3: [Make a pass and obtain the element with smallest value]
Repeat for i = k+1 to N
If MIN > A[i] then
MIN := A[i] and Position := i
Step 4: [Exchange elements]
If Position<> k then
Temp := A[k]
A[k] := A[Position]
A[Position] := Temp
Step 5: Exit.
Expected Outcome: The user should input the list of elements to be sorted as input. The
sorted list of elements will be displayed as output.
Sample:
Enter the number of elements in array: 6
Enter the elements of array:
8 5 7 3 9 2
The sorted array is:
2 8
3 9
5
7
Code:
#include <stdio.h>
int main()
{
int a[100], n, i, j, position, swap;
printf("Enter number of elementsn");
scanf("%d", &n);
printf("Enter %d Numbersn", n);
for (i = 0; i< n; i++)
scanf("%d", &a[i]);
for(i = 0; i< n - 1; i++)
{
position=i;
for(j = i + 1; j < n; j++)
{
if(a[position] > a[j])
position=j;
}
if(position != i)
{
swap=a[i];
a[i]=a[position];
a[position=swap;
}
}
printf("Sorted Array:n");
for(i = 0; i< n; i++)
printf("%dn", a[i]);
return 0;
}
Experiment 7 C
Aim: Write a program in C to implement insertion sorting.
Objective: To make the students familiar with the concept of sorting given elements and also
introduce different types of sorting.
Algorithm:
Consider an array with N elements.
Step 1: A[1] by itself is sorted
Step 2: A[2] is inserted before or after A[1], so that A[1] and A[2] are sorted.
Step 3: Similarly A[3] is inserted so that A[1], A[2] and A[3] are sorted.
Step 4: This process is continued till all the elements are sorted.
Expected Outcome: The user should input the list of elements to be sorted as input. The
sorted list of elements will be displayed as output.
Sample:
Enter the number of elements in array: 6
Enter the elements of array:
8 5 7 3 9 2
The sorted array is:
2
3
5
7
8
9
Code:
/* C Program for Insertion Sort */
#include <stdio.h>
int main()
{
int a[100], number, i, j, temp;
printf("\n Please Enter the total Number of Elements : ");
scanf("%d", &number);
printf("\n Please Enter the Array Elements : ");
for(i = 0; i< number; i++)
scanf("%d", &a[i]);
for(i = 1; i<= number - 1; i++)
{
for(j = i; j > 0 && a[j - 1] > a[j]; j--)
{
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
printf("\n Insertion Sort Result : ");
for(i = 0; i< number; i++)
{
printf(" %d \t", a[i]);
}
printf("\n");
return 0;
}
Experiment 7 C
Aim: Write a program in C to implement merge sorting.
Objective: To make the students familiar with the concept of sorting given elements and also
introduce different types of sorting.
Algorithm:
Merge(A, B, N, M, C)
Given two sorted arrays A and B containing N and M elements respectively. This algorithm
merges these arrays and produces the sorted array C which contains N+M elements.
Step 1: P := 1, Q := 1 and R:= 1
Step 2: Repeat while(P< =N) and (Q < = M)
If A[P]< B[Q] then
C[R] := A[P]
P := P+1
R := R+1
Else
C[R] := B[Q]
Q:= Q+1
R := R+1
Step 3: If P<N then
Repeat while(Q< = M)
C[R] := B[Q]
R := R+1
Q := Q+1
Else
Repeat while( P< = N)
C[R] :=A[P]
P := P+1
R := R+1
Step 4: Exit.
Code:
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i<= high; i++)
a[i] = b[i];
}
void sort(int low, int high) {
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main() {
int i;
printf("List before sorting\n");
for(i = 0; i<= max; i++)
printf("%d ", a[i]);
sort(0, max);
printf("\nList after sorting\n");
for(i = 0; i<= max; i++)
printf("%d ", a[i]);
}
Expected outcome : The user should input two sorted arrays and these sorted arrays are
merged as a third array which is also sorted.
Sample:
Enter the size of the first array: 4
Enter the elements of first array;
3 9 11 15
Enter the size of second array: 3
Enter the elements of second array:
4 7 13
The merged array is
3 4 7 9 11 13 15
Experiment 7 D
Aim: Write a program in C to implement heap sorting.
Objective: To make the students familiar with the concept of sorting given elements and also
introduce different types of sorting.
Algorithm:
PQInser(A[],N,key)
BEGIN:
A[N+1]=key
i=N+1
WHILE i>1 AND A[i]<A[i/2] DO
Exchange(A[i],A[i/2])
I=i/2
N=N+1
END;
Time Complexity: ϴ(LogN)
Space Complexity:ϴ(1)
ALGORITHM PQDelete (A[],N)
BEGIN:
x=A[i]
A[i]=A[N]
Adjust(A[],1,N-1)
RETURN x
END;
Time Complexity: ϴ(logN)
Space Complexity:ϴ(1)
ALGORITHM Adjust(A[],i,N)
BEGIN:
WHILE 2*i<=N DO
j=2*i
IF j+1<=N THEN
IF A[j+1]>A[j]
j=j+1
IF A[j]>A[i] THEN
Exchange(A[j],A[i])
ELSE
BREAK
i=j
END;
Time Complexity: ϴ(logN)
Space Complexity:ϴ(1)
Code:
#include<stdio.h>
#include <conio.h>
void Adjust(int Heap_of_Numbers[],int i) /*Function to arrange the elements in the heap*/
{
int j;
int copy;
int Number;
int Reference = 1;
Number=Heap_of_Numbers[0];
while(2*i<=Number && Reference==1)
{
j=2*i;
if(j+1<=Number &&Heap_of_Numbers[j+1] >Heap_of_Numbers[j])
j=j+1;
if( Heap_of_Numbers[j] <Heap_of_Numbers[i])
Reference=0;
else
{
copy=Heap_of_Numbers[i];
Heap_of_Numbers[i]=Heap_of_Numbers[j];
Heap_of_Numbers[j]=copy;
i=j;
}
}
}
void Make_Heap(int heap[])
{
int i;
int Number_of_Elements;
Number_of_Elements=heap[0];
for(i=Number_of_Elements/2;i>=1;i--)
Adjust(heap,i);
}
int main()
{
int heap[30];
int NumberofElements;
int i;
int LastElement;
int CopyVariable;
printf("Enter the number of elements present in the unsorted Array:");
scanf("%d",&NumberofElements);
printf("nEnter the members of the array one by one:"); /* Asking for the elements of the
unsorted array*/
for(i=1;i<=NumberofElements;i++)
scanf("%d",&heap[i]);
heap[0]=NumberofElements;
Make_Heap(heap);
while(heap[0] > 1) /*Loop for the Sorting process*/
{
LastElement=heap[0];
CopyVariable=heap[1];
heap[1]=heap[LastElement];
heap[LastElement]=CopyVariable;
heap[0]--;
Adjust(heap,1);
}
printf("nSortedArray:n");/*Printing the sorted Array*/
for(i=1;i<=NumberofElements;i++)
printf("%d ",heap[i]);
return 0;
}
