Sorting

“Sorting refers to the operation of rearranging data in either in ascending or descending

order”.
* the data may be numerical data or character data.
The sorting methods are classified into two types. They are ' Internal Sorting' and 'External
Sorting'. In internal sorting, all the data elements to be sorted are present in the main
memory. External sorting techniques are applied to large data sets which reside on
secondary storage devices and cannot be completely fit in main memory.
There are many sorting methods available. But no method for sorting is best in all cases.
The factors to be considered while choosing a sorting technique are,
 Programming time of the sorting technique
 Execution time of the sorting technique
 No. of comparisons required for sorting the list.
 Main or secondary memory space needed for sorting technique.
Different applications require different sorting methods. The different sorting methods are,
 Bubble Sort ( or) Exchange Sort
 Selection Sort
 Quick Sort (or) Partition Exchange Sort
 Insertion Sort
 Merge Sort
Note: A sorting method is said to be stable when it has the minimum no. of swaps.
 Stable sorting methods are - Bubble Sort, Selection Sort & Quick Sort
 Unstable Sorting methods are – Insertion Sort, Merge Sort
Bubble Sort (or) Exchange Sort
The simplest and the most widely used sorting technique is ' Bubble Sort'.
This method compares the two adjacent(consecutive) elements of the list. If thesy are not
in order, th two elemtns will be interchanged. If they are in order, the two elements remains
the same. This process continues (n-1) times for sorting an array of size n. There ends
one pass. During the first pass the largest/smallest will be moved to Nth position. The
second pass will be continued with first (N-1) elements. Repeat this process till all the
elemtns are in sorted order.
* Since, each pass places one element into its proper position, a list of N elements
requires (N-1) passes.
The procedure for bubble sort to sort 'N' elements in ascending order is,
Step 1: First compare two elements at time starting with the first tow elements.
Step 2: If the first element is larger than second element then exchange the two elements
Step 3: Go down one element and compare that element to the element that follows it.
Step 4: Continue this process till the end of list. ( During this process the largest element
moved to
Nth position)
Step 5: Repeat steps 1 thru 4 (N-1) times by leaving the last element of sorting list each
time.
For example, consider the list of 5 elements,

A[0] A[1] A[2] A[3] a[4]

23 56 42 35 18

The following comparisons are made in each pass:

“ The first largest element is placed in proper position i.e. at A[N-1] after the first pass” . In
general “ Kth largest element is placed in its proper position i.e. at A[n-k] after pass 'k' ”.
The complete set of passes in bubble sort method is,
Algorithm: Bubble_Sort(A,N)
// A is an array of N elements
{
 for i:= 1 to N-1 do
{
for j:=0 to N-i-1 do
if( A[j] > A[j+1] ) then
swap( A[j],A[j+1]);
}
}
/* Program for BUBBLE SORT */ void Bubble_Sort(int a[],int n)
#include<stdio.h> {
#include<stdlib.h> int i,j,temp;
#include<conio.h> for(i=1;i<n;i++)
void Bubble_Sort( int[], int) {
void main() for(j=0;j<n-i;j++)
{ {
int a[10],n,i; if(a[j]>a[j+1])
clrscr(); {
printf("\n Enter Array size :"); temp=a[j];
scanf("%d",&n); a[j]=a[j+1];
printf("\n Enter elements \n"); a[j+1]=temp;
for (i=0;i<n;i++) }
scanf("%d",&a[i]); }
bubblesort(a,n); }
printf("\n Array elements after sorting: }
\n");
for (i=0;i<n;i++)
printf("%d ",a[i]);
getch();
}

Analysis (or) Time Complexity for Bubble Sort:

 To sort N elements Bubble Sort requires (N-1) passes.
◦ Pass 1 requires (n-1) comparisons
◦ Pass 2 requires (n-2) comparisons
◦ ..
◦ ..
◦ Pass k requires (n-k) comparisons
◦ ..
◦ ..
◦ Pass (n-1) performs 1 comparison
 The total no. of comparisons = 1+2+3+ ...... + n-1
= n(n-1)/2 = (n2-n)/2
= O(n2)

Selection Sort
Selection Sort is the easiest method to sort list of elements.
In selection sort method first find the smallest(largest) element in the list and swap it with
the first element. Then find the second smallest(largest) element in the list and swap it with
the second element of the list. The process of searching and swapping the next smallest is
repeated until all the elements in the list have been sorted in ascending (descending)
order.
i.e the Selection Sort searches all of the elements in a list until it finds the smallest
element. It swaps this with the first element in the list.
Next it finds the smallest of the remaining elements and swaps it with the second element
and so on.
The procedure to sort 'n' elements in ascending order is,
Pass 1: Find the position (minpos) of the smallest element in the list of 'n' elements. Then
interchange A[minpos] & A[0]. i.e. A[0] is sorted means it is in proper place.
Pass 2: Find position (minpos) of the smallest element in the sublist of (n-1) elements then
interchange A[minpos] & A[1]. Now A[0] & A[1] are sorted i.e. A[0] ≤ A[1].
..
..
pass (n-1) : Find the position (minpos) of the smallest element in A[n-2] & A[n-1] then
interchange A[minpos] & A[n-2]. Now A[0], A[1],...., A[n-2] are sorted means A[n-1] is also
in proper place.
Thus “ the list of n elements are sorted after (n-1) passes”.
For example, suppose an array A contains 5 elements: 65 32 43 14 26
In first pass, the smallest element is searched by making of 4 comparisons and the
smallest element is 14. Then it is swapped with the first element i.e. 65. After the first pass
the elements are : 14 32 43 65 26.
The complete set of passes in selection sort are:
Algorithm: Selection_Sort( A, n)
// A is an array of n elements
{
for i:= 0 to n-2 do
{
min := A[i]; minpos := i;
for j:= i+1 to n-1 do
if(a[j]< min) then
{ min := a[j] ; minpos := j; }
swap(A[i], A[minpos]);
}
}

/* Program for Selection Sort */

#include<stdio.h> void Selection_Sort(int a[], int n)

#include<stdlib.h> {
#include<conio.h> int i,j,min,temp;
void Selection_Sort(int[], int); for(i=0;i<n-1; i++)
void main() {
{ min=i;
int a[10],n,i; for(j=i+1; j<n; j++)
clrscr(); {
printf("\n Enter Array size :"); if(a[j]<a[min])
scanf("%d",&n); min=j;
printf("\n Enter elements \n"); }
for (i=0;i<n;i++) temp=a[i];
scanf("%d",&a[i]); a[i]=a[min];
Selection_Sort(a,n); a[min]=temp;
printf("\n Array elements after sorting: \n"); }
for (i=0;i<n;i++) }
printf("%d ",a[i]);
}

Analysis of Selection Sort:

Analysis (or) Time Complexity for Bubble Sort:
 To sort N elements Bubble Sort requires (N-1) passes.
◦ Pass 1 requires (n-1) comparisons
◦ Pass 2 requires (n-2) comparisons
◦ ..
◦ ..
◦ Pass k requires (n-k) comparisons
◦ ..
◦ ..
◦ Pass (n-1) performs 1 comparison
 The total no. of comparisons = 1+2+3+ ...... + n-1
= n(n-1)/2 = (n2-n)/2
= O(n2)
 Insertion Sort
The main idea of Insertion Sort is to consider each element at a time, into the appropriate
position relative to the sequence of previously ordered elements, such that the resulting
sequence is also ordered.
In each pass an element is compared with its predecessors and if it is not in the right
position, it is placed in the right place among the elements being compared.
Suppose an array 'A' with 'n' elements A[0],A[1],....A[n-1]. The insertion sort algorithm
scans A from A[0] to A[n-1], inserting each element A[k] into proper position in the
previously sorted subarray A[0], A[1], ... , A[k-1].
The procedure is, consider the first element, for only one element no sort is required
because it is trivially sorted. So the procedure starts with second element.
Pass 1: A[1] is inserted either before or after A[0] so that A[0] & A[1] are sorted.
Pass 2: A[2] is inserted into proper position by comparing with A[0],A[1] so that A[0],A[1] &
A[2] are sorted.
..
..
Pass n-1: A[n-1] is inserted into its proper positioning A[0], A[1],...., A[n-2] so that all the n
elements are sorted
* Simply, in Pass k, A[k] is compared with its previous elements (A[0],A[1],...., A[k-1]) and
inserted after the element which is less than or equal to the A[k].
Example: consider the list of elements - 5 3 7 2 8 1 4
To sort this list in ascending order using insertion method, the passes are:
Algorithm: Insertion_Sort(A,n)
// A is an array of n elements
{
for i:= 1 to n-1 do
{
key:=A[i]; j := i-1;
while ((j ≥ 0) and (A[j] > key)) do
{
A[j+1] := A[j]; j := j-1;
}
a[j+1] := key;
}
}
 /* Program for INSERTION SORT */

#include<stdio.h> void Insertion_Sort(int a[],int n)

#include<stdlib.h> {
#include<conio.h> int i,j,key;
void Insertion_Sort(int[], int); for(i=1;i<n;i++)
void main() {
{ key=a[i];j=i-1;
int a[10],n,i; while((j>=0)&&(a[j]>key))
clrscr(); {
printf("\n Enter Array size :"); a[j+1]=a[j];
scanf("%d",&n); j--;
printf("\n Enter elements \n"); }
for (i=0;i<n;i++) a[j+1]=key;
scanf("%d",&a[i]); }
Insertion_Sort(a,n); }
printf("\n Array elements after sorting: \n");
for (i=0;i<n;i++)
printf("%d ",a[i]);
getch();
}

Analysis:
It is easiest sorting method. If list is already sorted, only one comparison is made on each
pass so that (n-1) passes requires (n-1) comparisons. Hence the time complexity is O(n)
i.e. Best case.
In worst case i.e if the list is sorted in reverse order ( unsorted) then the total no. Of
comparisons are ,
1 + 2 + 3 + ... + (n-1) = n(n-1)/2 = (n2-n)/2 = O(n2).
So, the Worst Case time complexity is : O(n2)
and the Best Case time complexity is : O(n)