SORTING
Sorting is an operation of data structure to arrange the
data elements in an order either in increasing (ascending) order or decreasing
(descending) order.
Example:
{2, 1, 5,
3, 2} ®{1,
2, 2, 3, 5} ascending order
{2, 1, 5,
3, 2} ®{5, 3, 2, 2, 1} descending order
Types of Sorting
Algorithm
There are several sorting algorithms are used.
• Bubble
sort
• Selection
sort
• Insertion
sort
• Merge
sort
• Quick
sort
• Heap
sort
• Radix
Sort
• Address
Calculation Sort
Bubble Sort
Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using
pair-wise comparisons and swapping.
After one pass only the largest value is correctly placed. All other
values are still out of order.
So we need to repeat this process. If we have N elements and if each time
we bubble an element, we place it in its correct location. Then we repeat the
“bubble up” process N – 1 times.
Arrange the following elements in ascending order using
bubble sort
12, 36, 27, 11, 40, 24, 23, 30
Pass 0:
- Compare 12 with 36, no
change
- Compare 36 with 27,
swap so elements are :- 12, 27, 36,
11, 40, 24, 23, 30
- Compare 36 with 11, swap
so elements are :- 12, 27, 11, 36, 40, 24, 23, 30
- Compare 36 with 40, no
change
- Compare 40 with 24, swap
so elements are :- 12, 27, 11, 36, 24, 40, 23, 30
- Compare 40 with 23, swap
so elements are :- 12, 27, 11, 36, 24, 23, 40, 30
- Compare 40 with 30, swap
so elements are :- 12, 27, 11, 36, 24, 23, 30, 40
At the end of pass 1 the largest element store at last index
number.
Pass 1:
12, 27, 11, 36,
24, 23, 30, 40 - no change
12, 27, 11, 36,
24, 23, 30, 40 - swap
12, 11, 27, 36,
24, 23, 30, 40 - no change
12, 11, 27, 36, 24,
23, 30, 40 - swap
12, 11, 27, 24, 36,
23, 30, 40 - swap
12, 11, 27, 24, 23, 36,
30, 40 - swap
12, 11, 27, 24, 23, 30, 36, 40
Pass 2:
12, 11, 27, 24,
23, 30, 36, 40
11, 12, 27, 24,
23, 30, 36, 40
11, 12, 27, 24,
23, 30, 36, 40
11, 12, 24, 27, 23,
30, 36, 40
11, 12, 24, 23, 27,
30, 36, 40
11, 12, 24, 23, 27, 30, 36, 40
Pass 3:
11, 12, 24, 23,
27, 30, 36, 40
11, 12, 24, 23,
27, 30, 36, 40
11, 12, 24, 23,
27, 30, 36, 40
11, 12, 23, 24, 27,
30, 36, 40
11, 12, 23, 24, 27, 30, 36, 40
Pass 4:
11, 12, 23, 24,
27, 30, 36, 40
11, 12, 23, 24,
27, 30, 36, 40
11, 12, 23, 24,
27, 30, 36, 40
11, 12, 23, 24, 27, 30, 36, 40
Pass 5:
11, 12, 23, 24,
27, 30, 36, 40
11, 12, 23, 24,
27, 30, 36, 40
11, 12, 23, 24, 27, 30, 36, 40
Pass 6:
11, 12, 23, 24,
27, 30, 36, 40
11, 12, 23, 24, 27, 30, 36, 40 - elements are in increasing order
So we need n number of passes start from 0 to n-1
In each pass we ( n-1-pass) number of comparisons.
WAP to sort an array
using bubble sort.
#include<stdio.h>
void bubble_sort(int [], int);
void main()
{ int a[20],n,i;
printf(“\nenter
number of elements to store in array”);
scanf(“%d”,&n);
printf(“\nenter %d
elements”,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“\nbefore
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
bubble_sort(a,n);
printf(“\nafter
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
}
void bubble_sort(int a[],int n)
{ int pass, i, t;
for(pass=0;pass<n-1;pass++)
{ for(i=0;i<n-1-pass;i++)
{ if(a[i]>a[i+1])
{ t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
}
}
Selection Sort
Selection sort algorithm is easy
to understand. Sorts an array by making several passes through the array,
selecting the next smallest item in the array each time and placing it where it
belongs in the array. From the array find out the smallest element from a[0] to
a[n-1] and replace with a[0] location, then find out the smallest element from
a[1] to a[n-1] and replace with a[1] location and so on.
Time complexity is O(n2).
Arrange the following elements in ascending order using
bubble sort
12, 36, 27, 11, 40, 24, 23, 30
Pass 0 :- 12, 36, 27, 11, 40, 24, 23, 30
Pass 1 :- 11, 36, 27, 12, 40, 24, 23, 30
Pass 2 :- 11, 12, 27, 36, 40, 24, 23, 30
Pass 3 :- 11, 12, 23, 36, 40, 24, 27, 30
Pass 4 :- 11, 12, 23, 24, 40, 36, 27, 30
Pass 5 :- 11, 12, 23, 24, 30, 36, 27, 40
Pass 6 :- 11, 12, 23, 24, 30, 27, 36, 40
Pass 7 :- 11, 12, 23, 24, 30, 27, 36, 40
Elements after pass 7 - 11, 12, 23, 24, 30, 27, 36, 40 are
in increasing order.
WAP to sort an array
using selection sort.
#include<stdio.h>
void selection_sort(int [], int);
void main()
{ int a[20],n,i;
printf(“\nenter
number of elements to store in array”);
scanf(“%d”,&n);
printf(“\nenter %d
elements”,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“\nbefore
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
selection_sort(a,n);
printf(“\nafter
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
}
void selection_sort(int a[],int n)
{ int i,j,pos,min;
for(i=0;i<n-1;i++)
{ min=a[i];
pos=i;
for(j=i+1;j<n;j++)
{ if(a[j]<min)
{ min=a[j];
pos=j;
}
}
a[pos]=a[i];
a[i]=min;
}}
Insertion Sort
Based on technique of card players
to arrange a hand
• Player
keeps cards picked up so far in sorted order
• When
the player picks up a new card
– Makes
room for the new card
– Then
inserts it in its proper place
For each array element from the second to the last
(nextIndex = 1), Insert the element at nextIndex where it belongs in the array,
increasing the length of the sorted sub array by 1.
The number of shifts performed during an insertion is one
less than the number of comparisons or, when the new value is the smallest so
far, the same as the number of comparisons.
WAP to sort an array
using insertion sort.
#include<stdio.h>
void insertion_sort(int [], int);
void main()
{
int a[20],n,i;
printf(“\nenter
number of elements to store in array”);
scanf(“%d”,&n);
printf(“\nenter %d
elements”,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“\nbefore
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
insertion_sort(a,n);
printf(“\nafter
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
}
void insertion_sort(int a[],int n)
{
int i,index,key;
for(index=1;index<n;index++)
{
key=a[index];
i=index-1;
while((i>-1)&&(a[i]>key))
{
a[i+1]=a[i];
i--;
}
a[i+1]=key;
}
}
Divide and Conquer
Technique
- Divide the problem into two or more
similar and smaller subproblems
- Recursively solve the subproblems
- Combine solutions to the subproblems
The following two sorting method use this technique.
- Quick Sort
- Merge Sort
Quick sort
• Quick
sort divided an array into two parts so that all the elements in the left sub
array are less than or equal to a specified value, called the pivot and all
elements in the right sub array are greater than from the pivot element.
• We
can take any element p as the pivot (generally we take the first
element as pivot element).
Partition the remaining elements
into two part:-
First Part, which contains all elements < p
Second Part, which contains all elements ≥ p
• Recursively sort the First Part and
Second Part
Algorithm for Quick sort
Quick_Sort(A, low, high)
Step 1:- if low <
high then
Step 2:- mid=
Partition (A, low, high)
Step 3:- Quick_Sort(A, low, mid–1 )
Step 4:- Quick_Sort(A,
mid+1, high)
[End if ]
Step 5:- end
Algorithm for Partitioning
Partitioning (A, low, high)
- Set
pivot value to A[low]
- Set i to low and j to high
- While
(i<j)
-
While A[i] < pivot, Increment i
- While A[j] >= pivot, Decrement j
- If i < j, swap A[i] and A[j]
End Loop
- Swap
A[low] and A[j]
- Return
j
Arrange the following elements in ascending order using
quick sort.
50, 30, 20, 60,
40, 10, 30, 55
Pass - 1
Select 50 as pivot element. Comparison starts from left to
right to find the element greater than from 50. So 60 > 50 (i = 3). Comparison start from right to left and finds
the element less than from 50. So 30 < 50 (j = 5). Then swap between 60 and 30.
So elements are 50, 30, 20, 30, 40, 10, 60, 55
Again repeat. 60 > 50 ( I = 6 ), and 10 < 50 ( j= 5 ),
but i is not less than j. so swap between 10 and 50. So after pass – 1 elements
are:-
10, 30, 20, 30, 40, 50,
60, 55
Pass 2:- 10, 30, 20, 30, 40, 50, 60, 55
Pass 3:- 10, 20,
30, 30, 40, 50, 55, 60
WAP to sort an array
using quick sort.
#include<stdio.h>
void quick_sort(int [], int, int);
int partition(int [ ], int, int);
void main()
{ int a[20],n,i;
printf(“\nenter
number of elements to store in array”);
scanf(“%d”,&n);
printf(“\nenter %d
elements”,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“\nbefore
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
quick_sort(a,n);
printf(“\nafter
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
}
void quick_sort(int a[],int low,int high)
{ int mid;
if(low<high)
{ mid=partition(a,low,high);
quick_sort(a,low,mid-1);
quick_sort(a,mid+1,high);
}
}
int partition(int a[ ], int low, int high)
{ int pivot, i, j, t;
pivot=a[low];
i=low+1;
j=high;
while(i<j)
{
while(a[i]<pivot)
i++;
while(a[j]>pivot)
j--;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[low]=a[j];
a[j]=pivot;
return j;
}
Merge Sort
Merge Sort: Algorithm
Merge_Sort (A, low, high)
Step -1:- if (low < high )
Step- 2:- mid =
(low + high)/2
Step- 3:- Merge_Sort(A,
low, mid)
Step- 4:- Merge_Sort(A,
mid+1,high)
Step- 5:- Merge(A,
low, mid, high)
[End
if]
Step-6:- End
Merge Algorithm
•
Access the first item from both sequences
•
While not finished with either sequence
– Compare
the current items from the two sequences, copy the smaller current item to the
output sequence, and access the next item from the input sequence whose item
was copied
•
Copy any remaining items from the first sequence
to the output sequence
•
Copy any remaining items from the second
sequence to the output sequence
WAP to sort an array
using merge sort.
#include<stdio.h>
#define SIZE 20
void merge_sort(int [], int, int);
void merge(int [],int, int, int);
void main()
{
int a[SIZE],n,i;
printf(“\nenter
number of elements to store in array”);
scanf(“%d”,&n);
printf(“\nenter %d
elements”,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“\nbefore
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
merge_sort(a,n);
printf(“\nafter
sort the elements are:\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
}
void merge_sort(int a[], int low, int high)
{ if (low < high)
{
mid = (low + high)/2 ;
merge_sort(a, low, mid);
merge_sort(a, mid+1,high);
merge(a, low, mid, high);
}
}
void merge(int a[],int low,int
mid,int high)
{
int b[SIZE],i,j,k;
i=low;
j=mid+1;
k=low;
while((i<=mid) && (j<=high))
{
if(a[i] < a[j])
{
b[k]=a[i];
k++;
i++;
}
else
{
b[k]=a[j];
k++;
j++;
}
}
while(i<=mid)
{
b[k]=a[i];
k++;
i++;
}
while(j<=high)
{
b[k]=a[j];
k++;
j++;
}
for(i=low;i<=high;i++)
a[i]=b[i];
}
THANK YOU
