DATA STRUCTURE : ASSIGNMENT-3:SORTING TECHNIQUES(RECURSIVE)
PRACTICE PROGRAM:
1) Write a C program to create a integer array with elements {888,111,666,444,222,999,333}
and sort the given array using Merge sort.
ANS:
#include <stdio.h>
#include <conio.h>
void merge(int a[], int first, int mid, int last)
{
int i, j, k, b[20];
i = first;
j = mid + 1;
k = 0;
while (i <= mid && j <= last)
{
if (a[i] < a[j])
{
b[k++] = a[i++];
}
else
{
b[k++] = a[j++];
}
}
while (i <= mid)
{
b[k++] = a[i++];
}
while (j <= last)
{
b[k++] = a[j++];
}
for (j = first, k = 0; j <= last; j++, k++)
{
a[j] = b[k];
}
}
void merge_sort(int a[], int first, int last)
{
int mid;
if (first < last)
{
mid = (first + last) / 2;
merge_sort(a, first, mid);
merge_sort(a, mid + 1, last);
merge(a, first, mid, last);
}
}
int main()
{
int a[] = {888, 111, 666, 444, 222, 999, 333};
int i;
printf("\n the unsorted array is:");
for (i = 0; i < 7; i++)
{
printf("\t%d", a[i]);
}
merge_sort(a, 0, 6);
printf("\n the sorted array is:");
for (i = 0; i < 7; i++)
{
printf("\t%d", a[i]);
}
}
-----------------------------------------------------------------------------------------------
2) Write a C program to sort a random array of n integers (value of n is accepted from user)
by using quick Sort algorithm in ascending order.
ANS:
#include <stdio.h>
#include <conio.h>
int partition(int a[], int lb, int ub)
{
int pivot = a[lb];
int temp;
int i = lb + 1;
int j = ub;
do
{
while ((a[i] < pivot) && (i <= ub))
{
i++;
}
while ((a[j] > pivot) && (j > lb))
{
j--;
}
if (i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} while (i < j);
a[lb] = a[j];
a[j] = pivot;
return j;
}
void quick_sort(int a[], int lb, int ub)
{
int j;
if (lb < ub)
{
j = partition(a, lb, ub);
quick_sort(a, lb, j - 1);
quick_sort(a, j + 1, ub);
}
}
int main()
{
int a[10], n, i;
printf("\n enter array limit:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
printf("\n enter element of index[%d]", i);
scanf("%d", &a[i]);
}
printf("\n the unsorted array is:");
for (i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
quick_sort(a, 0, n - 1);
printf("\n the sorted array is:");
for (i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
}
---------------------------------------------------------------------------------
3) Write a C program to sort a random array of n integers (value of n accepted from user) by
using merge Sort algorithm in ascending order.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
// function declaration
void merge(int arr[], int firstIndex, int midIndex, int lastIndex);
void mergeSort(int arr[], int firstIndex, int lastIndex);
int main()
{
int a[20], i, n;
printf("Enter the size of Array : ");
scanf("%d", &n);
printf("Enter the array element : \n");
for (i = 0; i < n; i++)
{
printf("Array index[%d] : ", i);
scanf("%d", &a[i]);
}
mergeSort(a, 0, n - 1);
printf("Sorted Array is : \n");
for (i = 0; i < n; i++)
{
printf("\t %d", a[i]);
}
getch();
return 0;
}
// Function definition
void merge(int arr[], int firstIndex, int midIndex, int lastIndex)
{
int i, j, k, b[20];
i = firstIndex;
j = midIndex + 1;
k = 0;
while (i <= midIndex && j <= lastIndex)
{
if (arr[i] < arr[j])
{
b[k++] = arr[i++];
}
else
{
b[k++] = arr[j++];
}
}
while (i <= midIndex)
{
b[k++] = arr[i++];
}
while (j <= lastIndex)
{
b[k++] = arr[j++];
}
// copy the b array into original array (arr[])
for (j = firstIndex, k = 0; j <= lastIndex; j++, k++)
{
arr[j] = b[k];
}
}
void mergeSort(int arr[], int firstIndex, int lastIndex)
{
int mid;
if (firstIndex < lastIndex)
{
mid = (firstIndex + lastIndex) / 2;
mergeSort(arr, firstIndex, mid);
mergeSort(arr, mid + 1, lastIndex);
merge(arr, firstIndex, mid, lastIndex);
}
}
----------------------------------------------------------------------------------------------
SET A:
1) Write a C program to accept and sort n elements in ascending order by using merge sort.
ANS:
#include <stdio.h>
#include <conio.h>
void display(int a[], int n)
{
for (int i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
}
void merge(int a[], int low, int mid, int high)
{
int i, j, k, b[20];
i = low;
j = mid + 1;
k = 0;
while ((i <= mid) && (j <= high))
{
if (a[i] < a[j])
{
b[k++] = a[i++];
}
else
{
b[k++] = a[j++];
}
}
while (i <= mid)
{
b[k++] = a[i++];
}
while (j <= high)
{
b[k++] = a[j++];
}
for (j = low, k = 0; j <= high; j++, k++)
{
a[j] = b[k];
}
}
void merge_sort(int a[], int low, int high)
{
int mid;
if (low < high)
{
mid = (low + high) / 2;
merge_sort(a, low, mid);
merge_sort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
int main()
{
int a[20], i, n;
printf("\n Enter array limit:");
scanf("%d", &n);
printf("\n Enter array elements:");
for (i = 0; i < n; i++)
{
printf("\n Enter %d index array element:", i);
scanf("%d", &a[i]);
}
printf("\n the unsorted array is:");
display(a, n);
merge_sort(a, 0, n - 1);
printf("\n the sorted array is:");
display(a, n);
}
---------------------------------------------------------------------------------
2) Write a C program to accept and sort n elements in ascending order by using quick sort.
ANS:
#include <stdio.h>
#include <conio.h>
void display(int a[], int n)
{
for (int i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
printf("\n");
}
int partition(int a[], int first, int last)
{
int pivot = a[first];
int temp;
int i = first + 1;
int j = last;
do
{
while ((a[i] < pivot) && (i <= last))
{
i++;
}
while ((a[j] > pivot) && (j > first))
{
j--;
}
if (i < j) // when it will cross itself!
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} while (i < j);
a[first] = a[j];
a[j] = pivot;
return j;
}
void quick_sort(int a[], int first, int last)
{
int j;
if (first < last)
{
j = partition(a, first, last);
quick_sort(a, first, j - 1);
quick_sort(a, j + 1, last);
}
}
int main()
{
int a[10], i, n;
printf("\n Enter array limit:");
scanf("%d", &n);
printf("\n Enter array elements:");
for (i = 0; i < n; i++)
{
printf("\n Enter %d array element:", i);
scanf("%d", &a[i]);
}
printf("\n The un-sorted array is:");
display(a, n);
quick_sort(a, 0, n - 1);
printf("\n The sorted array is:");
display(a, n);
}
--------------------------------------------------------------------
3) Modify the Quick sort program of SET A to sort the integers in descending order?
ANS:
/*3) Modify the Quick sort program of SET A to sort the integers in descending order?*/
#include <stdio.h>
#include <conio.h>
void display(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
}
int partition(int a[], int first, int last)
{
int pivot, temp;
pivot = a[first];
int i, j;
i = first + 1;
j = last;
do
{
while (a[i] > pivot && i <= last)
{
i++;
}
while (a[j] < pivot && j > first)
{
j--;
}
if (i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} while (i < j);
a[first] = a[j];
a[j] = pivot;
return j;
}
void quick_sort(int a[], int first, int last)
{
int j;
if (first < last)
{
j = partition(a, first, last);
quick_sort(a, first, j - 1);
quick_sort(a, j + 1, last);
}
}
int main()
{
int a[20], i, n;
printf("\n Enter array limit:");
scanf("%d", &n);
printf("\n Enter array elements:");
for (i = 0; i < n; i++)
{
printf("\n Enter [%d] index element:", i);
scanf("%d", &a[i]);
}
printf("\n The original array is:");
display(a, n);
quick_sort(a, 0, n - 1);
printf("\n The sorted elements are:");
display(a,n);
}
----------------------------------------------------------------
SET B:
1) Write a C program to create a string array with months (accept atleast 6 month) and sort
them using Quick sort.
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
void display(char a[][30], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("\t%s", a[i]);
}
}
int partition(char a[][30], int first, int last)
{
char pivot[10], temp[20];
strcpy(pivot, a[first]);
int i, j;
i = first + 1;
j = last;
do
{
while (strcmp(pivot, a[i]) > 0 && i < last)
{
i++;
}
while (strcmp(a[j], pivot) > 0 && j > first)
{
j--;
}
if (i < j)
{
strcpy(temp, a[i]);
strcpy(a[i], a[j]);
strcpy(a[j], temp);
}
} while (i < j);
strcpy(a[first], a[j]);
strcpy(a[j], pivot);
return j;
}
void quick_sort(char a[][30], int first, int last)
{
int j;
if (first < last)
{
j = partition(a, first, last);
quick_sort(a, first, j - 1);
quick_sort(a, j + 1, last);
}
}
int main()
{
char month[12][30];
int i, n;
printf("\n Enter how many months you want to store in array:");
scanf("%d", &n);
printf("\nEnter months of the year:");
for (i = 0; i < n; i++)
{
printf("\nEnter [%d] index month:", i);
scanf("%s", &month[i]);
}
printf("\nThe un-sorted string array is:\n");
display(month, n);
quick_sort(month, 0, n - 1);
printf("\nThe sorted string array is:\n");
display(month, n);
}
----------------------------------------------------------------------------------
2) Write a C program to create a string array with atlaest 5 elements which contains word
ending with ‘at’ and ‘an’ sound and sort them using Merge sort.
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
void display(char a[][30], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("\t%s", a[i]);
}
}
void merge(char a[][30], int first, int mid, int last)
{
int i, j, k;
char b[10][30];
i = first;
j = mid + 1;
k = 0;
while ((i <= mid) && (j <= last))
{
if (strcmp(a[j], a[i]) > 0)
{
strcpy(b[k++], a[i++]);
}
else
{
strcpy(b[k++], a[j++]);
}
}
while (i <= mid)
{
strcpy(b[k++], a[i++]);
}
while (j <= last)
{
strcpy(b[k++], a[j++]);
}
for (j = first, k = 0; j <= last; j++, k++)
{
strcpy(a[j], b[k]);
}
}
void merge_sort(char a[][30], int first, int last)
{
int mid;
if (first < last)
{
mid = (first + last) / 2;
merge_sort(a, first, mid);
merge_sort(a, mid + 1, last);
merge(a, first, mid, last);
}
}
int main()
{
int i, n;
printf("\n how many string you want to store:");
scanf("%d", &n);
char a[n][30];
printf("\n Enter array elements in string format:");
for (i = 0; i < n; i++)
{
printf("\nEnter [%d] index string:", i);
scanf("%s", &a[i]);
}
printf("\n The unsorted array is:");
display(a, n);
merge_sort(a, 0, n - 1);
printf("\nThe sorted string array is:");
display(a, n);
}
---------------------------------------------------------------------
3) Modify the Merge sort program of Set B to sort the integers in descending order?
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
void display(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
}
void merging(int a[], int first, int mid, int last)
{
int b[20], i, j, k;
i = first;
j = mid + 1;
k = 0;
while (i <= mid && j <= last)
{
if (a[i] < a[j])
{
b[k++] = a[j++];
}
else
{
b[k++] = a[i++];
}
}
while (i <= mid)
{
b[k++] = a[i++];
}
while (j <= last)
{
b[k++] = a[j++];
}
for (j = first, k = 0; j <= last; k++, j++)
{
a[j] = b[k];
}
}
void merge_sort(int a[], int first, int last)
{
int mid;
if (first < last)
{
mid = (first + last) / 2;
merge_sort(a, first, mid);
merge_sort(a, mid + 1, last);
merging(a, first, mid, last);
}
}
int main()
{
int a[20], i, n;
printf("\n Enter array limit:");
scanf("%d", &n);
printf("\n Enter array elements:");
for (i = 0; i < n; i++)
{
printf("\n Enter [%d] index element:", i);
scanf("%d", &a[i]);
}
printf("\n The unsorted array is:");
display(a, n);
merge_sort(a, 0, n - 1);
printf("\nThe sorted array is:");
display(a, n);
}
------------------------------------------------------------------------
SET C:
1) Write a C program to read the data from the file “person.txt” which contains personno,
name and personage and sort the data on age in ascending order using merge Sort.
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
typedef struct person
{
int p_no;
char name[20];
int age;
} person;
void merge(person a[], int first, int mid, int last)
{
person b[10];
int i, j, k;
i = first;
j = mid + 1;
k = 0;
while (i <= mid && j <= last)
{
if (a[i].age > a[j].age)
{
b[k++] = a[j++];
}
else
{
b[k++] = a[i++];
}
}
while (i <= mid)
{
b[k++] = a[i++];
}
while (j <= last)
{
b[k++] = a[j++];
}
for (j = first, k = 0; j <= last; j++, k++)
{
a[j] = b[k];
}
}
void merge_sort(person a[], int first, int last)
{
int mid;
if (first < last)
{
mid = (first + last) / 2;
merge_sort(a, first, mid);
merge_sort(a, mid + 1, last);
merge(a, first, mid, last);
}
}
int main()
{
struct person p[10];
FILE *ptr;
int i, n;
ptr = fopen("person.txt", "r");
if (ptr == NULL)
{
printf("\n File are not exist!");
exit(0);
}
printf("\n The original data:\n");
for (i = 0; !feof(ptr); i++)
{
fscanf(ptr, "%d%s%d", &p[i].p_no, &p[i].name, &p[i].age);
printf("\n%d %s %d", p[i].p_no, p[i].name, p[i].age);
}
n = i;
merge_sort(p, 0, n - 1);
printf("\n The sorted data is:\n");
for (i = 0; i < n; i++)
{
printf("\n%d %s %d", p[i].p_no, p[i].name, p[i].age);
}
ptr = fopen("person.txt", "a");
fprintf(ptr, "\n the sorted data is:\n");
for (i = 0; i < n; i++)
{
fprintf(ptr, "\n%d %s %d", p[i].p_no, p[i].name, p[i].age);
}
fclose(ptr);
}
TEXT FILE:
1 omkar 76
2 rahul 21
3 ramesh 87
4 rohan 32
5 rakesh 13
6 krishna 12
7 gopal 19
8 ravindra 55
9 siddharth 20
10 samir 65
-----------------------------------------------------------------------------------------
2) Write a C program to read the data from the file “student.txt” which contains rollno, name
and age and sort the data on age in ascending order using quick Sort.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student
{
int r_no;
char name[30];
int age;
} student;
int partition(student a[], int first, int last)
{
student pivot;
student swap;
pivot = a[first];
int i, j;
i = first + 1;
j = last;
do
{
while (a[i].age < pivot.age && i <= last)
{
i++;
}
while (a[j].age > pivot.age && j > first)
{
j--;
}
if (i < j)
{
swap = a[i];
a[i] = a[j];
a[j] = swap;
}
} while (i < j);
a[first] = a[j];
a[j] = pivot;
return j;
}
void quick_sort(student a[], int first, int last)
{
int j;
if (first <= last)
{
j = partition(a, first, last);
quick_sort(a, first, j - 1);
quick_sort(a, j + 1, last);
}
}
int main()
{
student s[10];
FILE *ptr;
int i, n = 0;
ptr = fopen("student1.txt", "r");
if (ptr == NULL)
{
printf("\n The file does not exist!");
exit(0);
}
i = 0;
while (!feof(ptr))
{
fscanf(ptr, "%d%s%d", &s[i].r_no, &s[i].name, &s[i].age);
i++;
n++;
}
printf("\n The un-sorted data is:\n");
for (i = 0; i < n; i++)
{
printf("\n%d %s %d", s[i].r_no, s[i].name, s[i].age);
}
quick_sort(s, 0, n - 1);
printf("\n The sorted data is:\n");
for (i = 0; i < n; i++)
{
printf("\n%d %s %d", s[i].r_no, s[i].name, s[i].age);
}
ptr = fopen("student1.txt", "a");
fprintf(ptr, "\n The sorted data is:\n");
for (i = 0; i <= n - 1; i++)
{
fprintf(ptr, "\n%d %s %d", s[i].r_no, s[i].name, s[i].age);
}
fclose(ptr);
}
TEXT FILE:
101 ganesh 15
102 rahul 25
103 rohan 13
104 krishna 29
105 ram 23
---------------------------------------------------------------------------------------
3) Read the data from the file student.txt and sort on names in alphabetical order (use strcmp)
using Merge sort / Quick sort. Write the sorted data to another file 'sortstudentname.txt'.
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
int partition(char a[][30], int first, int last)
{
char pivot[20];
char temp[20];
int i, j;
strcpy(pivot, a[first]);
i = first + 1;
j = last;
do
{
while (strcmp(pivot, a[i]) > 0 && i <= last)
{
i++;
}
while (strcmp(pivot, a[j]) < 0 && j > 0)
{
j--;
}
if (i < j)
{
strcpy(temp, a[i]);
strcpy(a[i], a[j]);
strcpy(a[j], temp);
}
} while (i < j);
strcpy(a[first], a[j]);
strcpy(a[j], pivot);
return j;
}
void quick_sort(char a[][30], int first, int last)
{
int j;
if (first <= last)
{
j = partition(a, first, last);
quick_sort(a, first, j - 1);
quick_sort(a, j + 1, last);
}
}
int main()
{
char name[10][30];
FILE *ptr;
int i, n = 0;
ptr = fopen("student.txt", "r");
if (ptr == NULL)
{
printf("\n File are not exist!");
exit(0);
}
i = 0;
while (!feof(ptr))
{
fscanf(ptr, "%s", &name[i]);
printf("\n%s", name[i]);
i++;
n++;
}
quick_sort(name, 0, n - 1);
printf("\n The sorted data is:\n");
for (i = 0; i < n; i++)
{
printf("\n%s", name[i]);
}
fclose(ptr);
ptr = fopen("sort_student_name.txt", "w");
fprintf(ptr, "\n The sorted data is:\n");
for (i = 0; i < n; i++)
{
fprintf(ptr, "\n%s", name[i]);
}
fclose(ptr);
}
TEXT FILE:
rajesh
ganesh
rahul
rohan
krishna
ram
gopal
aniket
om
omkar
------------------------------------------------------------------------------------
Comments
Post a Comment
Enter comment here!