SORTING
1.BUBBLE SORT
Write a C program to perform bubble sort on an array of n elements.
Input Format:
Input consists of n+1 integers. The first integer corresponds to n, the number of elements in the array. The next n integers correspond to the elements in the array.
Output Format:
Refer sample output for formatting specs.
Sample Input and Output:
[All text in bold corresponds to input and the rest corresponds to output]
Enter the number of elements :
5
Enter element 1
34
Enter element 2
23
Enter element 3
67
Enter element 4
34
Enter element 5
2
Unsorted list is :
34 23 67 34 2
After Pass 1 elements are :23 34 34 2 67
After Pass 2 elements are :23 34 2 34 67
After Pass 3 elements are :23 2 34 34 67
After Pass 4 elements are :2 23 34 34 67
Sorted list is :
2 23 34 34 67
Note: stop the process if u find that the list is sorted in any intermediate point.
SOLUTION:-
Write a C program to perform bubble sort on an array of n elements.
Input Format:
Input consists of n+1 integers. The first integer corresponds to n, the number of elements in the array. The next n integers correspond to the elements in the array.
Output Format:
Refer sample output for formatting specs.
Sample Input and Output:
[All text in bold corresponds to input and the rest corresponds to output]
2.SELECTION SORT
Write a C program to perform selection sort on an array of n elements.
Selection sort algorithm starts by comparing first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, leave the elements as it is. Then, again first element and third element are compared and swapped if necessary. This process goes on until first and last element of an array is compared. This completes the first step of selection sort.(Refer below diagram ....)
Input Format:
Input consists of n+1 integers. The first integer corresponds to n, the number of elements in the array. The next n integers correspond to the elements in the array.
Output Format:
Refer sample output for formatting specs.
Sample Input and Output1:
[All text in bold corresponds to input and the rest corresponds to output]
Selection sort algorithm starts by comparing first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, leave the elements as it is. Then, again first element and third element are compared and swapped if necessary. This process goes on until first and last element of an array is compared. This completes the first step of selection sort.(Refer below diagram ....)
Input Format:
Input consists of n+1 integers. The first integer corresponds to n, the number of elements in the array. The next n integers correspond to the elements in the array.
Output Format:
Refer sample output for formatting specs.
Sample Input and Output1:
[All text in bold corresponds to input and the rest corresponds to output]
Enter the number of elements in the array
6
Enter element 1
2
Enter element 2
7
Enter element 3
3
Enter element 4
8
Enter element 5
5
Enter element 6
1
Selection sort.
array before sorting:
2 7 3 8 5 1
After Iteration 1
1 7 3 8 5 2
After Iteration 2
1 2 7 8 5 3
After Iteration 3
1 2 3 8 7 5
After Iteration 4
1 2 3 5 8 7
After Iteration 5
1 2 3 5 7 8
After Iteration 6
1 2 3 5 7 8
array after sorting:
1 2 3 5 7 8
Sample Input and Output2:
[All text in bold corresponds to input and the rest corresponds to output]
Enter the number of elements in the array
5
Enter element 1
13
Enter element 2
9
Enter element 3
7
Enter element 4
4
Enter element 5
2
Selection sort.
array before sorting:
13 9 7 4 2
After Iteration 1
2 13 9 7 4
After Iteration 2
2 4 13 9 7
After Iteration 3
2 4 7 13 9
After Iteration 4
2 4 7 9 13
After Iteration 5
2 4 7 9 13
array after sorting:
2 4 7 9 13
array before sorting:
13 9 7 4 2
After Iteration 1
2 13 9 7 4
After Iteration 2
2 4 13 9 7
After Iteration 3
2 4 7 13 9
After Iteration 4
2 4 7 9 13
After Iteration 5
2 4 7 9 13
array after sorting:
2 4 7 9 13
SOLUTION:-
3.INSERTION SORT
Write a C program to perform insertion sort on an array of n elements.
Input Format:
Input consists of n+1 integers. The first integer corresponds to n, the number of elements in the array. The next n integers correspond to the elements in the array.
Output Format:
Refer sample output for formatting specs.
Sample Input and Output:
[All text in bold corresponds to input and the rest corresponds to output]
Enter the number of elements in the array
5
Enter element 1
4
Enter element 2
2
Enter element 3
7
Enter element 4
3
Enter element 5
1
Insertion sort.
array before sorting:
4 2 7 3 1
After Iteration 1
2 4 7 3 1
After Iteration 2
2 4 7 3 1
After Iteration 3
2 3 4 7 1
After Iteration 4
1 2 3 4 7
array after sorting:
1 2 3 4 7
SOLUTION:-
4.Ascending Order:-
Write a program to find whether the given array is sorted in ascending order.
Input Format:
Input consists of n+1 integers. The first integer corresponds to ‘n’ , the size of the array. The next ‘n’ integers correspond to the elements in the first array. Assume that the maximum value of n is 15.
Output Format:
Print yes if the array is sorted in asecending order. Print no if the array is not sorted in ascending order.
Sample Input 1:
5
2
3
6
8
1
Sample Output 1:
no
Sample Input 2:
5
2
3
6
8
10
Sample Output 2:
yes
SOLUTION:-
#include<stdio.h>
int checkAscending(int a[],int n)
{
int i,z=1;
for(i=0;i<n-1;i++)
{
if(a[i]>a[i+1])
{z=0;
break;}
}
return (z);
}
int main(void)
{
int a[15],i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int flag=checkAscending(a,n);
if(flag==0)
printf("\nno");
else printf("\nyes");
return 0;
}
5.Descending Order Check
Write a program to find whether the given array is sorted in descending order.
Input Format:
Input consists of n+1 integers. The first integer corresponds to ‘n’ , the size of the array. The next ‘n’ integers correspond to the elements in the first array. Assume that the maximum value of n is 15.
Output Format:
Print yes if the array is sorted in descending order. Print no if the array is not sorted in descending order.
Sample Input 1:
5
2
3
6
8
1
Sample Output 1:
no
Sample Input 2:
5
20
13
6
4
1
Sample Output 2:
yes
SOLUTION:-
#include<stdio.h>
int checkDescending(int a[],int n)
{
int i,flag=0;
for(i=0;i<n-1;i++)
{
if(a[i+1]>a[i])
{
flag=1;
break;
}
}
return (flag);
}
int main(void)
{
int a[15],i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int z=checkDescending(a,n);
if(z==1)
printf("\nno");
else printf("\nyes");
return 0;
}
6.Sorted Order Check
Write a program to find whether the given array is sorted in ascending or descending order.
Input Format:
Input consists of n+1 integers. The first integer corresponds to ‘n’ , the size of the array. The next ‘n’ integers correspond to the elements in the first array. Assume that the maximum value of n is 15.
Output Format:
Print yes if the array is sorted in ascending or descending order. Print no if the array is not sorted in ascending or descending order .
Sample Input 1:
5
2
3
6
8
10
Sample Output 1:
yes
Sample Input 2:
5
20
13
6
4
1
Sample Output 2:
yes
Sample Input 2:
5
20
13
6
4
10
Sample Output 3:
no
SOLUTION:-
#include<stdio.h>
#include<stdlib.h>
int checkAscorDsc(int *a,int n)
{
int i,flag=1;
int d=a[n-1]-a[0];
if(d>0)
{
for(i=0;i<n-1;i++)
if(a[i]>a[i+1])
{flag=0;
break;}
}
else if(d<0)
for(i=0;i<n-1;i++)
{
if(a[i]<a[i+1])
{flag=0;
break;}
}
else if(d==0)
{
flag=1;
}
return (flag);
}
int main(void)
{
int *a,n,i;
scanf("%d",&n);
a=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int z=checkAscorDsc(a,n);
if(z==0)
printf("no");
else printf("yes");
return 0;
}