Understanding Bubble Sort Algorithm
This content explains the Bubble Sort algorithm, discussing its working principle through examples and code. It covers the process of sorting elements, visual representations, time complexity analysis, and ways to improve sorting efficiency through different techniques.
Uploaded on Sep 11, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
PDS (Week-6) Sorting and Example Programs Jayanta Mukhopadhyay jay@cse.iitkgp.ernet.in
Bubble Sort In every iteration heaviest element drops at the bottom. The bottom moves upward.
Example Pass -1 x: x: 3 -5 6 12 72 21 -7 45 3 12 -5 6 72 21 -7 45 x: x: 3 -5 6 12 21 72 -7 45 3 12 -5 6 72 21 -7 45 x: x: 3 -5 12 6 72 21 -7 45 3 -5 6 12 21 -7 72 45 x: x: 3 -5 6 12 72 21 -7 45 3 -5 6 12 21 -7 45 72
Bubble Sort int pass,j,a[100],temp; /* read number of elements as n and elements as a[] */ for(pass=0; pass<n; pass++) { for(j=0; j<n-1; j++) { if(a[j]>a[j+1]) { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; } } } /* print sorted list of elements */
Example Pass: 1 x: x: 3 -5 6 12 72 21 -7 45 3 12 -5 6 72 21 -7 45 x: x: 3 -5 6 12 21 72 -7 45 3 12 -5 6 72 21 -7 45 x: x: 3 -5 12 6 72 21 -7 45 3 -5 6 12 21 -7 72 45 x: x: 3 -5 6 12 72 21 -7 45 3 -5 6 12 21 -7 45 72
Example Pass: 2 x: x: -5 3 6 12 21 -7 45 72 3 -5 6 12 21 -7 45 72 x: x: -5 3 6 12 -7 21 45 72 -5 3 6 12 21 -7 45 72 x: -5 3 6 12 21 -7 45 72 x: x: -5 3 6 12 21 -7 45 72 -5 3 6 12 -7 21 45 72
Time Complexity Number of comparisons : o Worst Case? 1+2+3+ +(n-1) = n(n-1)/2 o Best Case? Same How do you make best case with (n-1) comparisons only?
Bubble Sort int pass,j,a[100],temp,swapflag; /* read number of elements as n and elements as a[] */ for(pass=0; pass<n; pass++) { swapflag=0; for(j=0; j<n-1; j++) { if(a[j]>a[j+1]) { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; swapflag=1; } } if(swapflag==0) break; } /* print sorted list of elements */
Basis of efficient sorting algorithms Two of the most popular sorting algorithms are based on divide-and-conquer approach. Quick sort Merge sort Basic concept: sort (list) { if the list has length greater than 1 { Partition the list into lowlist and highlist; sort (lowlist); sort (highlist); combine (lowlist, highlist); } }
Example x: 3 12 -5 6 72 21 -7 45 3 12 -5 6 72 21 -7 45 Splitting arrays 3 12 -5 6 72 21 -7 45 3 12 -5 6 72 21 -7 45 3 12 -5 6 21 72 -7 45 Merging two sorted arrays -7 21 45 72 -5 3 6 12 -7 -5 3 -7 -5 3 6 12 21 45 72
Merge Sort C program #include<stdio.h> void mergesort(int a[],int i,int j); void merge(int a[],int i1,int j1,int i2,int j2); void mergesort(int a[],int i,int j) { int mid; int main() { int a[30],n,i; printf("Enter no of elements:"); scanf("%d",&n); printf("Enter array elements:"); if(i<j) mid=(i+j)/2; { /* left recursion */ mergesort(a,i,mid); /* right recursion */ mergesort(a,mid+1,j); /* merging of two sorted sub-arrays */ merge(a,i,mid,mid+1,j); } } for(i=0;i<n;i++) scanf("%d",&a[i]); mergesort(a,0,n-1); printf("\nSorted array is :"); for(i=0;i<n;i++) printf("%d ",a[i]); return 0; }
Merge Sort C program void merge(int a[],int i1,int j1,int i2,int j2) { int temp[50]; //array used for merging int i=i1,j=i2,k=0; while(i<=j1 && j<=j2) { if(a[i]<a[j]) temp[k++]=a[i++]; else temp[k++]=a[j++]; } //while elements in both lists while(i<=j1) temp[k++]=a[i++]; //copy remaining elements of the first list while(j<=j2) temp[k++]=a[j++]; //copy remaining elements of the second list for(i=i1,j=0;i<=j2;i++,j++) a[i]=temp[j]; //Transfer elements from temp[] back to a[] }
Splitting Trace -56 23 43 -5 -3 0 123 -35 87 56 75 80 123 -35 87 56 75 80 -56 23 43 -5 -3 0 56 75 80 123 -35 87 -5 -3 0 -56 23 43 -35 87 75 80 123 -3 0 56 87 23 43 -35 -56 -3 0 80 75 43 23 -56 -35 -5 -3 0 23 43 56 75 80 87 123 Worst Case: O(n.log(n))
Quicksort At every step, we select a pivot element in the list (usually the first element). We put the pivot element in the final position of the sorted list. All the elements less than or equal to the pivot element are to the left. All the elements greater than the pivot element are to the right.
Partitioning size-1 0 x: pivot Values smaller Values greater Perform partitioning Perform partitioning
Quick Sort program #include <stdio.h> void quickSort( int[], int, int); int partition( int[], int, int); void main() { int i,a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9}; printf("\n\nUnsorted array is: "); for(i = 0; i < 9; ++i) printf(" %d ", a[i]); quickSort( a, 0, 8); printf("\n\nSorted array is: "); for(i = 0; i < 9; ++i) printf(" %d ", a[i]); } void quickSort( int a[], int l, int r) { int j; if( l < r ) { // divide and conquer j = partition( a, l, r); quickSort( a, l, j-1); quickSort( a, j+1, r); } } int partition( int a[], int l, int r) { int pivot, i, j, t; pivot = a[l]; i = l; j = r+1; while( 1) { do { } while(a[i]<=pivot && i<=r); do { --j; } while( a[j] > pivot ); if( i >= j ) break; t = a[i]; a[i] = a[j]; a[j] = t; } t = a[l]; a[l] = a[j]; a[j] = t; return j; } ++i;
Trace of Partitioning Input: 45 -56 78 90 -3 -6 123 0 -3 45 69 68 45 -56 78 90 -3 -6 123 0 -3 45 69 68 -6 -56 -3 0 -3 -6 -56 45 123 90 78 45 69 68 68 90 78 45 69 123 68 45 -3 0 -3 0 -3 -3 -3 0 78 90 69 69 90 78 Output: -56 -6 -3 -3 0 45 45 68 69 78 90 123
Time Complexity Partitioning with n elements. - No. of comparisons: n-1 Choice of pivot element affects the time complexity. Worst Case Performance: (n-1)+(n-2)+(n-3)+ . +1= n(n-1)/2 Best Case performance: (n-1)+2((n-1)/2-1)+4(((n-1)/2-1)-1)/2-1) .. k steps = O(n. log(n)) 2k=n
Exercise Implement non-recursive version of quick sort and merge sort.
Example 1 Determine the value of x which causes the function y = x cos(x) to be maximized within a specified interval.
/* find the maximum of a function within a specified interval */ #include <stdio.h> double a,b,xl,yl,xr,yr,cnst=0.0001; /* external variable declaration */ extern void reduce(void); /* external function prototype */ extern double curve(double xl); /* external function prototype */ int main() { double xmax, ymax; printf("\na= "); scanf("%lf",&a); printf("\nb= "); scanf("%lf",&b); do reduce(); while((yl!=yr) && ((b-a)>3*cnst)); xmax=0.5*(xl+xr); ymax=curve(xmax); printf("\nxmax= %8.6lf ymax= %8.6lf\n",xmax,ymax); } mainFile.c
extern double a,b,xl,yl,xr,yr,cnst; extern double curve(double xl); #include <math.h> extern double curve(double x) { return (x*cos(x)); } extern void reduce(void) { xl=a+0.5*(b-a-cnst); xr=xl+cnst; yl=curve(xl); yr=curve(xr); if(yl>yr) { b=xr; return; } if(yl<yr) a=xl; return; } evalFunc.c intReduce.c
Example 1 Compile and Execute $ cc -c -Wall mainFile.c intReduce.c evalFunc.c $ cc mainFile.o intReduce.o evalFunc.o -lm $ ./a.out a= 0 b= 3.141593 xmax= 0.860394 ymax= 0.561096
Example Write a complete C program that will read N (to be read from the user) number of integers and sort them. User will input his/her choice of sorting technique from a pool of Selection/Insertion/Bubble technique will be implemented as separate function. User choice will pick right sorting function using switch- case statement. sort. Each sorting
Example #include <stdio.h> #define SIZE 100 switch(choice) { case 'I': case 'i': insSort(x,size); break; case 'S': case 's': selSort(x,size); break; case 'B': case 'b': bubbleSort(x,size); break; default: printf( No Sorting"); } void selSort(int a[],int n); void insSort(int a[],int n); void bubbleSort(int a[],int n); int main() { char choice; int k,x[SIZE],size; do { printf("Enter the number of elements: "); scanf("%d",&size); printf("Enter the elements: "); for(k=0;k<size;k++) scanf("%d",&x[k]); printf("Sorting method [I/S/B]: "); getchar(); choice=getchar(); for(k=0;k<size;k++) printf("%d ",x[k]); printf("\Continue [Y/N]: "); getchar(); choice=getchar(); } while(choice=='Y' || choice=='y'); return 0; }
void selSort(int x[],int size) { int k,j,pos,temp; void bubbleSort(int a[],int n) { int pass,j,temp,swapflag; for (k=0; k<size-1; k++) { pos = k; for (j=k+1; j<size; j++) { if (x[j] < x[pos]) { pos = j; } } temp = x[k]; x[k] = x[pos]; x[pos] = temp; } } for(pass=0; pass<n; pass++) { swapflag=0; for(j=0; j<n-1; j++) { if(a[j]>a[j+1]) { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; swapflag=1; } } if(swapflag==0) break; } } void insSort(int x[],int size) { int i,j,temp; for (i=1; i<size; i++) { temp = x[i] ; for (j=i-1; (j>=0)&& (x[j] > temp); j--) x[j+1] = x[j]; x[j+1] = temp ; } }
EXAMPLE PROBLEMS
Problem 1 Write a C program to print a Geometric Progression (GP) series and its sum till N terms. Expression for a GP Series: where, a is the first term r is the common ratio n is the number of terms
Problem 1 (Gp-sum) #include <stdio.h> #include <math.h> int main() { float a, r, sum, term; int n, i; printf("Give the first term, common ratio, and number of terms: \n"); scanf("%f%f%d",&a,&r,&n); sum=0; term=a; for (i=0; i<n; i++) { sum=sum+term; term=term*r; } printf("Sum=%f \n",sum); return 0; }
Problem 2 Write a C program to generate a FLOYD's triangle. 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21
C Program Code (Floyd Triangle) #include <stdio.h> int main() { int rows, a, b, number = 1; printf("Number of rows of Floyd's triangle to print:"); scanf("%d",&rows); for ( a = 1 ; a <= rows ; a++ ) { for ( b = 1 ; b <= a ; b++ ) { printf("%d ", number); number++; } printf("\n"); } return 0; }
Problem 3 Write a C program to check whether a number is a strong number or not. What is a strong number ? A number whose sum of the factorial of its digit is equal to the number itself. Example: 145 = 1! +4! +5! = 1 + 24 + 120 = 145 is a strong number.
Problem 3 (Strong Number) #include <stdio.h> int factorial(int k); int main() { int number, tmpnum, i, sum, digit; if (sum==number) printf("The number %d is a strong number \n",number); else printf("The number is NOT a strong number \n"); return 0; } /* End of main() */ printf("Input the number: \n"); scanf("%d",&number); sum=0; tmpnum=number; /* Get digits one by one and add their factorials cumulatively */ while(tmpnum>0) { digit=tmpnum%10; tmpnum=tmpnum/10; sum=sum+factorial(digit); } int factorial(int k) { int prod=1, i; for(i=1; i<=k;i++) prod=prod*i; return(prod); }
Problem 4 Write a C program to arrange elements in an array in ascending order.
Problem 5 Write a C program to reverse a string (array of characters) without using any extra array.
Problem 5 (String reversal w/o extra array) /* String reversal without using extra array */ #include <stdio.h> #include <string.h> int main() { char S[100],tmpChar; int i,j; while(i<j) { tmpChar=S[i]; S[i]=S[j]; S[j]=tmpChar; i++; j--; } printf("The output string %s \n", S); return(0); } printf("Read the string \n"); scanf("%s",S); printf("The input string %s \n", S); i=0; j=strlen(S)-1;
Problem 6 Write a C program to concatenate two strings without using library function.
Problem 6 (String concatenation) #include <stdio.h> i=0; while(S2[i]!='\0') { S3[j]=S2[i]; i++; j++; } int main() { char S1[100], S2[100], S3[200]; int i,j; printf("Read two strings \n"); scanf("%s%s",S1,S2); S3[j]='\0'; /* Denote end of string */ i=0; j=0; while(S1[i]!='\0') { S3[j]=S1[i]; i++; j++; } printf("Concatenated string %s \n",S3); return(0); }
Problem 7 Given 2 positive numbers n and r, n>=r , write a C function to compute the number of combinations(nCr) and the number of permutations(nPr). Permutations formula is P(n,r)=n!/(n-r)! Combinations formula is C(n,r)=n!/(r!(n-r)!)
Problem 7- Program for testing permutaion and combination #include <stdio.h> int permute(int n, int m); printf("Give n and r for n choose r \n"); scanf("%d%d",&n,&r); int choose(int n,int r); combVal=choose(n,r); printf("Number of combinations=%d \n",combVal); int main() { int n,m,r; int permVal,combVal; return(0); } printf("Give n and m for n permute m \n"); scanf("%d%d",&n,&m); permVal=permute(n,m); printf("Number of permutations=%d \n",permVal);
permute() and choose() functions int permute(int n,int m) { int i, val; int choose(int n,int r) { int i; float val; val=n; for(i=n-1;i>=n-m+1;i--) val=val*i; val=n; for(i=1;i<r;i++) val=val* (float) (n-i)/ (float) (i+1); return(val); } return((int) val); }
Problem 8 Scope of variable: What is the output of the following code snippet? #include <stdio.h> int main(){ printf( i=%d \n ,i); return 0; } int i = 10; for(int i = 5; i < 15; i++) printf( i is %d\n , i);
Problem 9 Scope of variable: What is the output of the following code snippet? #include <stdio.h> int a = 20; int sum(int a, int b) { printf ("value of a in sum() = %d\n", a); printf ("value of b in sum() = %d\n", b); return a + b; } int main () { int a = 10; int b = 20; int c = 0; printf ("value of a in main() = %d\n", a); c = sum( a, b); printf ("value of c in main() = %d\n", c); return 0; }
Problem 10 Write a C program which display the entered number in words. Example: Input: Enter a number: 7 Output: Seven
Problem 11 Write a C program to delete duplicate elements in an array without using another auxiliary array. Example: Input: 5 8 5 5 6 9 8 2 1 1 3 3 Output: 5 8 6 9 2 1 3
Problem 12 Write a C program to print PASCAL s triangle.
Problem 13 Given 2 numbers a and b, write a C program to compute the Greatest Common Divisor(GCD) of the 2 numbers. The GCD of 2 numbers is the largest positive integer that divides the numbers without a remainder. Example: GCD(2,8)=2; GCD(3,7)=1
