#### Transcript of Bubble sort - Group 1

Index

Definition.

Idea.

flow chart.

*Example

Peseudo code.

*Code for integer.

*Code for String (On Borland).

Big O Notation.

code for integer

void main()

{

int a[30],n,i;

clrscr();

printf("Enter no of elements :");

scanf("%d",&n);

printf("Enter array elements :");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

bubble_sort(a,n);

getch();

}

live example

What is Bubble Sort ?!

It is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted ..

How

By comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary. until the elements is sorted.

{

int i,j,k,temp,flag=1;

printf("unsorted Data:\t");

for(k=0;k<n;k++)

printf("%d\t",a[k]);

for(i=0;i<n;i++)

{

flag=0;

for(j=0;j<n-i;j++)

{

if(a[j]>a[j+1]

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

flag=1;

}

}

if(flag==0)

break;

}

for(k=0;k<n;k++)

printf("%d\t",a[k]);

}

The bubble sort gets its name from elements moving up into the correct order like bubbles rising to the surface.

Idea :

bubble sort pseudo code

**Bubble Sort.**

code for string

**Thank You**

Big-O Notation

BubbleSort

( int a[], int n)

Begin

for

i = 1 to n-1

sorted = true

for

j = 0 to n-i-1

if a[j] > a[j+1]

temp = a[j]

a[j] = a[j+1]

a[j+1] = temp

sorted = false

end for

if sorted

break from i loop

end for

End

bubble_sort(

int a[]

,

int n

)

Definition:

An algorithm is a sequence of well-defined steps to be followed to solve a problem .

What is An Algorithm ?

*The Big-O notation is Commonly used to represent asymptotic upper bounds. It describes relevant time or space complexity of algorithms(memory usage of an algorithm).

* Big-O analysis provides a simplified estimate of a problem difficulty.

*Usually describes the worst-case running time of algorithm .

The Big-O Notation

bubble_sort(int a[] , int n)

{

int I ,j ,k ,temp, flag=1;

for(i=0 ; i<n ; i++)

{

flag=0;

for(j=0 ; j<n-i-1 ; j++)

{

if(a[j]>a[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

flag=1;

}

}

Bubble Sort (Big-O)

*It is possible to compare of two algorithms with running times

Running Times of Algorithm A and B

TA(N) = 1000 N = O(N)

TB(N) = N2 = O(N2)

A is asymptotically faster than B !

*Constants can be ignored.

-Units are not important

O(7n2) = O(n2)

*Lower order terms are ignored

-O(n3+7n2+3) = O(n3)

Advantages of O Notation

Full transcript