University:
College
Course:
College Computer Science
Academic year:

2023
Views:

28

Pages:

8
Author:

dhruvil5011

Subject code: 3150703 Subject Name: Analysis and Design of Algorithms Date: 27/07/2022 Enrollment No: 200420107127 Name: Lathiya Dhruvil ---------------------------------------------------------------------------------------------------------------------------------- Practical -1 Aim- Implementation and Time analysis of sorting algorithms. : Bubble sort, Selection sort, Insertion sort, Merge sort and Quick sort. Program1) Bubble sort #include #include void bubblesort(int a[],int n) { int i,j,temp; for(i=0; ia[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } } void printarr(int a[],int n) { int i; for(i=0; i0; i--) { a[n-i]=i; } clock_t begin=clock(); bubblesort(a,n); // printarr(a,n); clock_t end = clock(); time_spent+=(double)(end - begin) / CLOCKS_PER_SEC; printf("The elapsed time is %f seconds \n", time_spent); } SCET/CO/2022-23/Odd/BE Div-I/Sem-V Page No.- 1 Subject code: 3150703 Subject Name: Analysis and Design of Algorithms Date: 27/07/2022 Enrollment No: 200420107127 Name: Lathiya Dhruvil ---------------------------------------------------------------------------------------------------------------------------------- 2) Selection sort #include #include void selectionsort(int a[],int n) { int i,j,temp; for(i=0; ia[j]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } } void printarr(int a[],int n) { int i; for(i=0; i0; i--) { a[n-i]=i; } clock_t begin=clock(); selectionsort(a,n); // printarr(a,n); clock_t end = clock(); time_spent+=(double)(end - begin) / CLOCKS_PER_SEC; printf("The elapsed time is %f seconds \n", time_spent); } 3) Insertion sort #include #include void insertionsort(int a[],int n) { int i, key, j; for (i = 1; i < n; i++) { key = a[i]; SCET/CO/2022-23/Odd/BE Div-I/Sem-V Page No.- 2 Subject code: 3150703 Subject Name: Analysis and Design of Algorithms Date: 27/07/2022 Enrollment No: 200420107127 Name: Lathiya Dhruvil ---------------------------------------------------------------------------------------------------------------------------------j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j = j - 1; } a[j + 1] = key; } } void printarr(int a[],int n) { int i; for(i=0; i0; i--) { a[n-i]=i; } clock_t begin=clock(); insertionsort(a,n); // printarr(a,n); clock_t end = clock(); time_spent+=(double)(end - begin) / CLOCKS_PER_SEC; printf("The elapsed time is %f seconds \n", time_spent); } 4) Merge sort #include #include #include void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) SCET/CO/2022-23/Odd/BE Div-I/Sem-V Page No.- 3 Subject code: 3150703 Subject Name: Analysis and Design of Algorithms Date: 27/07/2022 Enrollment No: 200420107127 Name: Lathiya Dhruvil ---------------------------------------------------------------------------------------------------------------------------------R[j] = arr[m + 1 + j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } void printArray(int A[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", A[i]); printf("\n"); } void main() SCET/CO/2022-23/Odd/BE Div-I/Sem-V Page No.- 4 Subject code: 3150703 Subject Name: Analysis and Design of Algorithms Date: 27/07/2022 Enrollment No: 200420107127 Name: Lathiya Dhruvil ---------------------------------------------------------------------------------------------------------------------------------{ double time_spent=0.0; int i,n; int a[100000]; printf("Enter size of array: "); scanf("%d",&n); for(i=n; i>0; i--) { a[n-i]=i; } clock_t begin=clock(); mergeSort(a,0,n-1); clock_t end = clock(); time_spent+=(double)(end - begin) / CLOCKS_PER_SEC; printf("The elapsed time is %f seconds \n", time_spent); } 5) Quick sort #include #include void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int partition (int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { SCET/CO/2022-23/Odd/BE Div-I/Sem-V Page No.- 5 Subject code: 3150703 Subject Name: Analysis and Design of Algorithms Date: 27/07/2022 Enrollment No: 200420107127 Name: Lathiya Dhruvil ---------------------------------------------------------------------------------------------------------------------------------int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } void main() { double time_spent=0.0; int i,n; int a[100000]; printf("Enter size of array: "); scanf("%d",&n); for(i=n; i>0; i--) { a[n-i]=i; } clock_t begin=clock(); quickSort(a,0,n-1); clock_t end = clock(); time_spent+=(double)(end - begin) / CLOCKS_PER_SEC; printf("The elapsed time is %f seconds \n", time_spent); } 6) Heap sort #include #include void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void heapify(int arr[], int N, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < N && arr[left] > arr[largest]) largest = left; if (right < N && arr[right] > arr[largest]) largest = right; if (largest != i) { swap(&arr[i], &arr[largest]); SCET/CO/2022-23/Odd/BE Div-I/Sem-V Page No.- 6 Subject code: 3150703 Subject Name: Analysis and Design of Algorithms Date: 27/07/2022 Enrollment No: 200420107127 Name: Lathiya Dhruvil ---------------------------------------------------------------------------------------------------------------------------------heapify(arr, N, largest); } } void heapSort(int arr[], int N) { for (int i = N / 2 - 1; i >= 0; i--) heapify(arr, N, i); for (int i = N - 1; i >= 0; i--) { swap(&arr[0], &arr[i]); heapify(arr, i, 0); } } void main() { double time_spent=0.0; int i,n; int a[100000]; printf("Enter size of array: "); scanf("%d",&n); for(i=n; i>0; i--) { a[n-i]=i; } clock_t begin=clock(); heapSort(a,n); clock_t end = clock(); time_spent+=(double)(end - begin) / CLOCKS_PER_SEC; printf("The elapsed time is %f seconds \n", time_spent); } n Bubble sort Selection sort Insertion sort Merge Sort Quick sort Heap sort Time complexity 10 100 0.000 0.000 1000 0.118 10000 0.975 50000 6.657 0.000 0.000 0.005 0.290 7.545 0.000 0.000 0.002 0.177 4.577 0.000 0.000 0.0002 0.0030 0.0115 0.000 0.000 0.000 0.000 0.0048 0.0001 0.2156 0.0035 5.3881 0.0121 SCET/CO/2022-23/Odd/BE Div-I/Sem-V Page No.- 7 Subject code: 3150703 Subject Name: Analysis and Design of Algorithms Date: 27/07/2022 Enrollment No: 200420107127 Name: Lathiya Dhruvil ---------------------------------------------------------------------------------------------------------------------------------- Graph analysis for different sorting algorithm 1) Bubble sort 60000 60000 50000 50000 40000 40000 30000 30000 20000 20000 10000 10000 0 0 -10000 2) Selection sort 1 2 3 4 5 1 -10000 2 3) Insertion sort 4 5 4) Merge sort 60000 60000 50000 50000 40000 40000 30000 30000 20000 20000 10000 10000 0 0 1 2 3 4 1 -10000 5 2 3 4 5 -20000 -10000 6) Heap sort 5) Quick sort 60000 60000 50000 50000 40000 40000 30000 30000 20000 20000 10000 10000 0 -10000 3 1 2 3 4 -20000 SCET/CO/2022-23/Odd/BE Div-I/Sem-V 5 0 1 2 3 4 5 -10000 Page No.- 8