Search

Tuesday, December 24, 2013

Bubble Sort Algorithm in Computer Programming: C

2:09 AMTuesday, December 24, 2013
More often in computer programming, programmers works with large amount of data and it may be necessary to arrange them in ascending or descending order. This process of arranging the given elements in a order is called sorting, the order may be ascending or descending.

For example, consider the unsorted elements:
10, 60, 50, 20, 30, 70, 40
After arranging them in ascending order, the elements are rearranged as shown below:
10, 20, 30, 40, 50, 60, 70
After arranging them in descending order, the elements are rearranged as shown below:
70, 60, 50, 40, 30, 20, 10

The two important and simple sorting techniques are described below with example:

Bubble sort

This is the simplest and easiest sorting technique. In this technique, the two successive items or elements arr[i] and arr[i+1] are exchanged whenever the condition arr[i]>arr[i+1] will be true. For example, consider the elements shown below:

In the first pass 50 is compared with 40 and they are exchanged since 50 is greater than 40. Next 50 is compared with 30 and they are exchanged since 50 is greater than 30. If we proceed in the same manner, at the end of the first pass the largest item occupies the last position. On each successive pass, the items with the next largest value will be moves to the bottom and thus elements are arranged in ascending order.

Note: Observe that after each pass, the larger values sink to the bottom or next position of the array and hence it is also called sinking sort. The following figure shows the output of each pass:

Note: Observe that at the end of each pass, smaller values gradually "bubble" up to the top (like air bubble moving to surface of water). So, this sorting technique is called bubble sort.

The comparisons that are performed in each pass are as follows:

In general, we can say i = 0 to n-(j+1) or i=0 to n-j-1. Here, j=1 to 4 represent pass numbers. In general j=1 to n-1. So, the partial code can be written as follows:
for(j=1; j<n; j++)
{
for(i=0; i<n-j; i++)
{
if(arr[i]>arr[i+1])
{
exchange (arr[i], arr[i+1])
}
}
}

Algorithm

Step 1:    [Input number of items]
for I = 0 to n-1
[End of for]
Step 3:    for j = 1 to n-1 do
for i = 0 to n-j do
if(arr[i] >= arr[i+1])
temp = arr[i]
arr[i] = arr[i+1]
arr[i+1] = temp
[End of if]
[End of for]
[End of for]
Step 4:    for i = 0 to n-1
Write: arr[i]
[End of for]
Step 5:    Exit

C Program.

main()
{
int n,i,j,temp,arr[10];
clrscr();
printf("Enter the number of items:");
scanf("%d",&n);
printf("Enter the items:");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
for(j=0;j<n;j++)
{
for(i=0;i<n-j;i++)
{
if(arr[i]>=arr[i+1])
{
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
}
printf("The sorted items are:\n");
for(i=0;i<n;i++)
printf("%d\n",arr[i]);
getch();
}

• Very simple and easy to program
• Straight forward and approach

• It runs slowly and hence it is not efficient. More efficient sorting techniques are present.
• Even if the elements are sorted, n-1 passes are required to sort.

Selection Sort in C