Sorting Techniques - Bubble Sort and Quick Sort


Arranging a list of elements in an order (ascending or descending) is called sorting. There are different types of sorting techniques in which one technique is better than its predecessor. In this article, I am going to discuss the two sorting techniques bubble sort and quick sort with their algorithms and C programs.

Bubble Sort


Bubble Sort is a sorting technique which comes under the category of sorting by exchange. The procedure of bubble sort is as follows. Compare first and second elements, second and third elements, third and fourth elements and so on. Make sure that all these pairs are in ascending (descending) order by swapping them if necessary. As the largest (smallest) element in the list will be greater than or equal to (less than or equal to) any number in the considered pairs, it will be shifted to the end of the list. Now, apply the same procedure to all the elements of the list except the largest (smallest) element reached to the end now. In every iteration, largest (smallest) elements get shifted to the right and therefore the list will get sorted in ascending (descending) order. To understand bubble sort clearly, let us perform bubble sort on the list 34, 12, 55, 67, 23, 77, 32 to obtain ascending order.

Iteration 1 shifts largest number to position 1 from last.
34 12 55 67 23 77 32
12 34 55 67 23 77 32 (34>12 - Swap 34 and 12)
12 34 55 67 23 77 32 (34<=55 - No change)
12 34 55 67 23 77 32 (55<=67 - No change)
12 34 55 23 67 77 32 (67>23 - Swap 67 and 23)
12 34 55 23 67 77 32 (67<=77 - No change)
12 34 55 23 67 32 77 (77>32 - Swap 77 and 32)
Iteration 2 shifts next largest number to position 2 from last.
12 34 55 23 67 32
12 34 55 23 67 32 (12<=34 - No change)
12 34 55 23 67 32 (34<=55 - No change)
12 34 23 55 67 32 (55>23 - Swap 55 and 23)
12 34 23 55 67 32 (55<=67 - No change)
12 34 23 55 32 67 (67>32 - Swap 67 and 32)
Iteration 3 shifts next largest number to position 3 from last.
12 34 23 55 32
12 34 23 55 32 (12<=34 - No change)
12 23 34 55 32 (34>23 - Swap 34 and 23)
12 23 34 55 32 (34<=55 - No change)
12 23 34 32 55 (55>32 - Swap 55 and 32)
Iteration 4 shifts next largest number to position 4 from last.
12 23 34 32
12 23 34 32 (12<=23 - No change)
12 23 34 32 (23<=34 - No change)
12 23 32 34 (34>32 - Swap 34 and 32)
Iteration 5 shifts next largest number to position 5 from last.
12 23 32
12 23 32 (12<=23 - No change)
12 23 32 (23<=32 - No change)
Iteration 6 shifts next largest number to position 6 from last.
12 23
12 23 (12<=23 - No change)
Obviously, the element with minimum value will be shifted to first.
12 23 32 34 55 67 77

Algorithm for Bubble Sort


BubbleSort


Input : A list a[1], a[2], …… a[n].
Output : The list a[1], a[2], …… a[n] after sorting (in ascending order).

1 : START
2 : for i=1 to n-1 do
3 : if(a[j]>a[j+1]) then
4 : Swap(a[j],a[j+1])
5 : endIf
6 : endFor
7 : endFor
8 : STOP

Swap


Input : Two variables X and Y.
Output : Value of X changed to Value of Y and vice versa.

1 : START
2 : temp=X
3 : X=Y
4 : Y=temp
5 : STOP

C Program for Bubble Sort


Program
#include<stdio.h>
#include<conio.h>
void main()
{
int i,j,n,temp,a[25];
clrscr();
printf("Enter number of elements : ");
scanf("%d",&n);
printf("Enter the list before sorting :");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=n-2;i>=0;i--)
{
for(j=0;j<=i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("The list after sorting is :");
for(i=0;i<n;i++)
printf(" %d",a[i]);
getch();
}

Output
Enter number of elements : 7
Enter the list before sorting : 34 12 55 67 23 77 32
The list after sorting is : 12 23 32 34 55 67 77

Time complexity for bubble sort is O(n) in best case and O(n2) in average and worst cases. Space complexity for bubble sort is O(1) in the worst case. Bubble sort is also called sinking sort.

Quick Sort


Quick Sort is a sorting technique which comes under the category of sorting by exchange. The procedure of quick sort is as follows.
1) Consider a pivot element and two pointers first and last.
2) Initialise first and last to minimum and maximum indexes of the list of elements respectively.
3) If element at first is less than pivot element, increment first. Repeat this until it cannot be done.
4) If element at last is greater than pivot element, decrement last. Repeat this until it cannot be done.
5) If first is less than last, swap the elements at first and last.
6) Repeat the above three steps until first exceeds last.
7) Swap the pivot element and the element at last to get elements less than pivot element to its left and elements greater than pivot element to its right.
To understand quick sort clearly, let us perform quick sort on the list 34, 12, 55, 67, 23, 77, 32 by taking the first element of the list as pivot element.

34 12 55 67 23 77 32
34ip 12 55 67 23 77 32j (List - Initialize pivot(p), first(i) and last(j))
34p 12i 55 67 23 77 32j (34<=34 - Increment first)
34p 12 55i 67 23 77 32j (12<=34 - Increment first)
34p 12 32i 67 23 77 55j (first<last - Swap 55 and 32)
34p 12 32 67i 23 77 55j (32<=34 - Increment first)
34p 12 32 67i 23 77j 55 (55>34 - Decrement last)
34p 12 32 67i 23j 77 55 (77>34 - Decrement last)
34p 12 32 23i 67j 77 55 (first<last - Swap 67 and 23)
34p 12 32 23 67ij 77 55 (23<=34 - Increment first)
34p 12 32 23j 67i 77 55 (67>34 - Decrement last)
23p 12 32 34j 67i 77 55 (first>last - Swap 34 and 23)
Now, elements less than pivot element are to the left of it and elements greater than pivot element are to the right of it. Let us apply quick sort for the sub lists left and right to the pivot element.
23ip 12 32j (Left Sub List - Initialize pivot(p), first(i) and last(j))
23p 12i 32j (23<=23 - Increment first)
23p 12 32ij (12<=23 - Increment first)
23p 12j 32i (32>23 - Decrement last)
12p 23j 32i (first>last - Swap 23 and 12)
67ip 77 55j (Right Sub List - Initialize pivot(p), first(i) and last(j))
67p 77i 55j (67<=67 - Increment first)
67p 55i 77j (first<last - Swap 55 and 77)
67p 55 77ij (55<=67 - Increment first)
67p 55j 77i (77>67 - Decrement last)
55p 67j 77i (first>last - Swap 67 and 55)
12 23 32 34 55 67 77

Algorithm for Quick Sort


QuickSort


Input : A list 'a' and part under consideration i.e. between 'start' and 'stop'.
Output : The list 'a' i.e. a[1], a[2], …… a[n] after sorting (in ascending order).

1 : START
2 : if(start<stop) then
3 : pivot=Partition(a,start,stop)
4 : QuickSort(a,start,pivot-1)
5 : QuickSort(a,pivot+1,stop)
6 : endIf
7 : STOP

Partition


Input : A part of list 'a' between 'left' and 'right'.
Output : The position of pivot element to be considered.

1 : START
2 : pivot=left
3 : while(left<right) do
4 : while(a[pivot]<=a[right] and pivot<right) do
5 : right--
6 : endWhile
7 : if(a[pivot]>a[right]) then
8 : Swap(a[pivot],a[right])
9 : pivot=right
10 : left++
11 : endIf
12 : while(a[pivot]>=a[left] and pivot>left) do
13 : left++
14 : endWhile
15 : if(a[pivot]<a[left]) then
16 : Swap(a[pivot],a[left])
17 : pivot=left
18 : right--
19 : endIf
20 : endWhile
21 : return pivot
22 : STOP

Swap


Input : Two variables X and Y.
Output : Value of X changed to Value of Y and vice versa.

1 : START
2 : temp=X
3 : X=Y
4 : Y=temp
5 : STOP

C Program for Quick Sort


Program
#include<stdio.h>
#include<conio.h>
void quicksort(int a[],int,int);
void main(void)
{
int i,n,a[25];
clrscr();
printf("Enter number of elements : ");
scanf("%d",&n);
printf("Enter the list before sorting : ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1);
printf("The list after sorting is :");
for(i=0;i<n;i++)
printf(" %d",a[i]);
getch();
}
void quicksort(int a[],int first,int last)
{
int i,pivot,j,temp;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(a[i]<=a[pivot]&&i<last)
i++;
while(a[j]>a[pivot])
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
quicksort(a,first,j-1);
quicksort(a,j+1,last);
}
}

Output
Enter number of elements : 7
Enter the list before sorting : 34 12 55 67 23 77 32
The list after sorting is : 12 23 32 34 55 67 77

Time complexity for quick sort is O(n2) in the worst case and O(nlogn) in average and best cases. Space complexity for quick sort is O(n) in the worst case.


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: