Bubble Sort – Bubble sort is a simple sorting algorithm. The
algorithm starts at the beginning of the data set. It compares the first two
elements, and if the first is greater than the second, it swaps them. It
continues doing this for each pair of adjacent elements to the end of the data
set. It then starts again with the first two elements, repeating until no swaps
have occurred on the last pass.
•
Let
n = array length = size of the array
•
The
outer loop is executed n-1 times
•
Each
time the outer loop is executed, the inner loop is executed
–
Inner
loop executes n-1 times at first, linearly dropping to just once
–
On
average, inner loop executes about n/2 times for each execution of the outer
loop
–
In
the inner loop, the comparison is always done (constant time), the swap might
be done (also constant time)
•
Result is n * n/2 * k, that is, O(n2/2 + k) = O(n2)
Complexity :
Best-Case Analysis
•
If the elements start in sorted order, the for loop will compare
the adjacent pairs but not make any changes
•
So the swapped Elements variable will still be false
and the while loop is only done once
•
There are N – 1 comparisons in the best case
Worst-Case Analysis
•
If in the best case the while loop is done once, in the worst
case the while loop must be done as many times as possible
•
Each pass of the for loop must make at least one swap of the
elements
•
The number of comparisons will be:
Average-Case Analysis
•
We can potentially stop after any of the (at most) N – 1 passes
of the for loop
•
This means that we have N – 1 possibilities and the average
case is given by where C(i) is the work done in the first i passes
•
On the first pass, we do N – 1 comparisons
•
On the second pass, we do N – 2 comparisons
Bubble Sort Source Code and Algorithm.
#include <stdio.h>
#include <conio.h>
//BUBBLE SORT
//Function to Sort the List
void
BubbleSort(int a[],int size)
{
int i,j,tmp;
for(i=0;i<size;i++)
{
for(j=0;j<size-i-1;j++)
{
if(
a[j]>a[j+1] )
{
tmp
= a[j];
a[j]
= a[j+1];
a[j+1]
= tmp;
}
}
}
}
//Main Function
int
main()
{
int
i,n,c=0;
int
a[20];
printf("\n\tEnter
size of Array [Below 20] : ");
scanf("%d",&n);
for(i=0 ;i<n;i++)
{
printf("\tEnter Nos. at
[%d] : ",i);
scanf("%d",&a[i]);
}
printf("\n\tBefore Sort : ");
for(i=0 ;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n\tAfter Bubble Sort : ");
BubbleSort(a,n);
for(i=0 ;i<n;i++)
{
printf("%d ",a[i]);
}
getch();
}
Algorithm
for
i ← 0 to n-1
do
for
j ← 0 to n-i-1
do
If
A[j] > A[j-1] then
A[j-1]↔ A[j]
end
for j
end for
i
Sorting string using bubble sort
technique.
#include <stdio.h>
#include <conio.h>
#include <string.h>
//String Sorting
int
main()
{
char
arr[5][20]={"Delhi ","Kolkata","Bangalore ","Agra
char
temp[20];
int
n=5,i,j;
printf("\n\n\tOriginal : ");
for(i=0;i<n;i++)
{
printf("%s ",arr[i]);
}
for(i=0; i<n-1; i++)
{
for(j = 0; j<n-i-1;j++)
{
if(strcmpi(arr[j],arr[j+1])>0)
{
strcpy(temp,arr[j]);
strcpy(arr[j],arr[j
+ 1]);
strcpy(arr[j + 1] ,temp);
}
}
}
printf("\n\n\tSorted
List : ");
for(i=0;i<n;i++)
{
printf("%s
",arr[i]);
}
getch();
}
Bubble Sort Using Recursive
Function.
#include <stdio.h>
#include <conio.h>
//Recursive Bubble Sort
int
n;
//Recursive Function for Second
Loop
void
bsort(int a[],int j,int k)
{
int
t;
if(k<n-j-1)
{
if(a[k]>a[k+1])
{
t=a[k];
a[k]=a[k+1];
a[k+1]=t;
}
bsort(a,j,k+1);
}
}
//Recursive Function for First
Loop
void
sort(int a[],int i)
{
if(i<n-1)
{
bsort(a,i,0);
sort(a,i+1);
}
}
//Main Function
int
main()
{
int a[50],i;
printf("\n\tEnter the Size [Below 20] :
");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the Element at
[%d] ",i+1);
scanf("%d",&a[i]);
}
printf("\n\tOriginal :
");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
sort(a,0);
printf("\n\tAfter Sort : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
getch();
}
Selection Sort – This form of sorting
algorithms finds the minimum value, swaps it with the value in the first position,
and repeats these steps for the remainder of the list. It does no more than n
swaps.
•
Let
n = array length = size of the array
•
The
outer loop is executed n-1 times
•
Each
time the outer loop is executed, the inner loop is executed
–
Inner
loop executes n-1 times at first. On average, inner loop executes about n/2
times for each execution of the outer loop.
–
Every
time inner loop executer it find the least value from the list then swap it
with the value in ‘i’ position.
•
Result is n * n/2 * k, that is, O(n2/2 + k) = O(n2)
The Complexity of Selection Sort
will be same as Bubble Sort.
Selection Sort Source code and
Algorithm.
#include <stdio.h>
#include <conio.h>
// SELECTION SORT
//Function for Sorting the list
void
SelectionSort(int a[],int size)
{
int
i,j,min,pos,t;
for(i
= 0;i<size-1;i++)
{
min
= a[i];
pos
= i;
for(j
= i+1;j<size;j++)
{
if(a[j]<min)
{
min = a[j];
pos = j;
}
t=a[i];
a[i]=a[pos];
a[pos]=t;
}
}
}
//Main Function
int
main()
{
int
i,n,c=0;
int
a[20];
printf("\n\tEnter
size of Array [Below 20] : ");
scanf("%d",&n);
for(i=0 ;i<n;i++)
{
printf("\tEnter Nos. at
[%d] : ",i);
scanf("%d",&a[i]);
}
printf("\n\tBefore Sort : ");
for(i=0 ;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n\tAfter Selection Sort : ");
SelectionSort(a,n);
for(i=0 ;i<n;i++)
{
printf("%d ",a[i]);
}
getch();
}
Algorithm
for i ←1 to n-1
min ← i;
x ← A[i]
for j = i + 1 to n
do
If
A[j] < min then
m← j
x← A[j]
end
if
end
for j
A[i]
↔ A [m]
end
for i
Selection Sort using Recursive
Function
#include <stdio.h>
#include <conio.h>
//Recursive Selection Sort
int
n,p;
//Function for First Loop
void
ssort(int a[],int min,int j,int k,int p)
{
int
t;
if(k<n)
{
if(a[k]<min)
{
min=a[k];
p=k;
}
ssort(a,min,j,k+1,p);
}
else
{
t=a[j];
a[j]=a[p];
a[p]=t;
}
}
// Function for Second loop
void
sort(int a[],int i)
{
p=i;
if(i<n-1)
{
ssort(a,a[i],i,i+1,p);
sort(a,i+1);
}
// Main Function
int
main()
{
int a[20],i,c,k=0;
printf("\n\tSize of Array [below
20] : ");
scanf("%d",&n);
printf("Enter the no.");
for(i=0;i<n;i++)
{
printf("\tEnter the value
for [%d] Position ",i+1);
scanf("%d",&a[i]);
}
printf("\n\tOriginal
: ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
sort(a,0);
printf("\n\tAfter
Sort : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
getch();
}
No comments:
Post a Comment