Sorting

Sorting
NEED FOR SORTING
Insertion Sort
Illustration of Insertion Sort
Insertion Sort algorithm
code for Insertion Sort
advantages & disadvantages of Insertion Sort
best case and worst case of Insertion Sort
Selection sort
Illustration of Selection sort
Selection sort algorithm
code for Selection sort
worst case for selection Sort

1. Chapter 7Chapter 7
sortingsorting
01/31/18BY MS. SHAISTA QADIR 1
PRESENTED BY
Shaista Qadir
Lecturer king khalid university

2. ContentsContents
sorting
neeD For sorting
insertion sort
illustration oF insertion sort
insertion sort algorithm
CoDe For insertion sort
aDvantages & DisaDvantages oF insertion
sort
best Case anD worst Case oF insertion sort
seleCtion sort
illustration oF seleCtion sort
seleCtion sort algorithm
CoDe For seleCtion sort
 worst Case For seleCtion sort
01/31/18BY MS. SHAISTA QADIR 2

3. ContentsContents
bubble sort
illustration oF bubble sort
bubble sort algorithm
CoDe For bubble sort
best, average anD worst Case For bubble
sort
 DisaDvantages oF insertion sort
merge sort
illustration oF merge sort
example oF merge sort
merge sort algorithm
01/31/18BY MS. SHAISTA QADIR 3

4. sortingsorting
01/31/18BY MS. SHAISTA QADIR 4
Sorting refers to the process of arranging the elements of
an Array in increasing
order or decreasing order.
i.e., A[0]< A[1]< A[2]<………< A[N-1] or
A[0]> A[1]> A[2]>………> A[N-1]
SORTING ELEMENTS OF AN ARRAY:
Here N is the number of elements in the Array.
Eg: If Array A is
After sorting array A becomes

5. neeD For sortingneeD For sorting
01/31/18BY MS. SHAISTA QADIR 5
Data handling efficiency increases if they are Sorted
according to some ordering criteria.
If telephone directory is not properly ordered, it is very
difficult to find a name from it.
Examples of sorted data: Telephone directory,
Payroll
Students list
Book Index

6. neeD For sortingneeD For sorting
01/31/18BY MS. SHAISTA QADIR 6
There are many types of sorting algorithms.
1) Bubble sort
2) Linear/Sequential sort
3) Selection sort
4) Insertion sort
5) Shell sort
6) Merge sort
7) Quick sort
8) Heap sort, etc.,

7. neeD For sortingneeD For sorting
01/31/18BY MS. SHAISTA QADIR 7
Sorting is categorized in 2 types:
◦ Elementary Sorting Algorithm (Insertion Sort, Selection
Sort and Bubble Sort etc.)
◦Efficient Sorting Algorithm (Quick Sort, Merge Sort etc.).

8. insertion sort insertion sort
01/31/18BY MS. SHAISTA QADIR 8
Insertion Sort
◦ An insertion sort starts by considering the first two
elements of array data[0] and data[1].
◦ If they are out of order, i.e., if data [1] < data [0], change
their positions.
◦ Then the third element, data [2], is considered and
compared with the previous data elements in positions 1
and 0.
if data [2] < data [1] and data[0],
change the positions of

9. insertion sort insertion sort
01/31/18BY MS. SHAISTA QADIR 9
 Insertion Sort
data [1] to position 2 and
data[0] to position 1 and
insert data[2] to position 0.
◦if data [2] < data [1] only,
◦change the positions of
data[1] to position 2 and
insert data[2] to position 1.
◦if data[2]> data [1] and data [0]
◦do not change the position of data[2]

10. illustration oF insertion illustration oF insertion
sort sort
01/31/18BY MS. SHAISTA QADIR 10
Each element in data[i] is inserted is inserted in proper position j
such that 0 <= j <= i and all elements greater than data [i] are
moved by one position.
Illustration

11. InsertIon sort algorIthmInsertIon sort algorIthm
01/31/18BY MS. SHAISTA QADIR 11
Algorithm to sort elements of an array A using Insertion Sort
whose number of elements is len.
◦Step:1 Set i=1
◦Step:2 Repeat 3 to 9 until i<len
◦Step:3 Copy the content of array A in position i to a
variable copy
◦Step:4 Set j=i
◦Step:5 Repeat 6 and 7 until j>0 and while A[j-1]> copy.
◦Step:6 A[j]=A[j-1]
◦Step:7 Decrement j
◦Step:8 A[j]=copy
◦Step:9 Increment i
◦Step:10 Exit

12. code for code for InsertIon sort InsertIon sort
01/31/18BY MS. SHAISTA QADIR 12
Code for Insertion Sort whose number of elements is len.
public void insertionsort()
{
int i, j;
for(i=1; i<arr.length; i++)
{
int copy = arr[i];
for(j=i; j>0 && copy < arr[j-1]; j--)
arr[j] = arr[j-1];
arr[j] = copy;
}}

13. advantages & advantages &
dIsadvantages of InsertIon dIsadvantages of InsertIon
sort sort
01/31/18BY MS. SHAISTA QADIR 13
ADVANTAGE of Insertion sort:
◦It sorts the array only when it is really necessary.
◦ If the array is already in order, no substantial moves are
made.
DISADVANTGE:
◦ If an item is begin inserted, all elements greater than the one
begin inserted have to be moved.

14. best case and worst case of best case and worst case of
InsertIon sort InsertIon sort
01/31/18BY MS. SHAISTA QADIR 14
BEST CASE:
◦ best case is when the data are already in order.
◦ only one comparison is to be made for each position.
◦ so there are n-1 comparisons. (n=len in previous
algorithm)
◦The best time is of the order of n
WORST CASE:
◦ The worst case is when the data are in reverse order.
◦ For each i, the item data[i] is less than every item data
[0] … data[i-1] and each of them is moved by one
position.

15. selectIon sort selectIon sort
01/31/18BY MS. SHAISTA QADIR 15
Selection Sort
◦ An selection sort finds the first smallest element in the
array and puts in the first position of array.
◦ Then it finds the second smallest number and puts in the
second position and so on.

16. IllustratIon of selectIon IllustratIon of selectIon
sort sort
01/31/18BY MS. SHAISTA QADIR 16
Illustration

17. selectIon sort algorIthmselectIon sort algorIthm
01/31/18BY MS. SHAISTA QADIR 17
Algorithm to sort elements of an array A using Selection
Sort whose number of elements is len.
◦Step:1 Set out=0
◦Step:2 Repeat 3 to 5 until out<len-1
◦Step:3 Find position, minposi of minimum element from
the elements A[out],….., A[len-1]
◦Step:4 Swap A[out] and A[minposi]
◦Step:5 Increment out
◦Step:6 Exit

18. code for code for selectIon sort selectIon sort
01/31/18BY MS. SHAISTA QADIR 18
Code for Insertion Sort whose number of elements is len.
public void selectionsort()
{
int out, in, minposi;
for(out=0; out<arr.length-1; out++)
{
minposi = out;
for(in=out+1; in<arr.length; in++)
if(arr[in] < arr[minposi] )
minposi = in;
swap(out, minposi);
}}

19. worst case for worst case for selectIon selectIon
sort sort
01/31/18BY MS. SHAISTA QADIR 19
WORST CASE:
◦The worst case time happens when the array is in reverse
order.
◦Then the outer loop executes n-2 times and for each
i,=out, the inner loop executed for n-1-i times.
◦(here n=arr.length, i=out)
◦So the time complexity of the algorithm is

20. bubble sort bubble sort
01/31/18BY MS. SHAISTA QADIR 20
A Bubble sort bubbles the smallest element to the top.
It compares data[N-1] and data[N-2] and arrange them in
order such that data[N-2]< data[N-1].
Then compare data[N-3] and data[N-2] and arrange such
that data [N-3]< data [N-2].
Continue this until data [0]<data[1]. This pass bubbles out
the smallest number in position 0.
 Repeat this comparison with the elements from data[N-1]
to data [1] and so on

21. bubble Sort illuStrationbubble Sort illuStration
01/31/18BY MS. SHAISTA QADIR 21

22. bubble Sort illuStrationbubble Sort illuStration
01/31/18BY MS. SHAISTA QADIR 22

23. bubble Sort illuStrationbubble Sort illuStration
01/31/18BY MS. SHAISTA QADIR 23

24. bubble Sort algorithmbubble Sort algorithm
01/31/18BY MS. SHAISTA QADIR 24
Algorithm to sort elements of an array A using Bubble Sort
whose number of elements is n.
◦Step:1 Set i=0
◦Step:2 Repeat 3 to 7 until i<n-1
◦Step:3 Set j=n-1
◦Step:4 Repeat 5 to 6 until j>i
◦Step:5 If data[j]<data[j-1], swap (data[j], data[j-1])
◦Step:6 Decrement j
◦Step: 7Increment i
◦Step:8 Exit

25. bubble Sort algorithmbubble Sort algorithm
01/31/18BY MS. SHAISTA QADIR 25
Algorithm to sort elements of an array A using Bubble Sort
whose number of elements is n.
◦Step:1 Set i=0
◦Step:2 Repeat 3 to 7 until i<n-1
◦Step:3 Set j=n-1
◦Step:4 Repeat 5 to 6 until j>i
◦Step:5 If data[j]<data[j-1], swap (data[j], data[j-1])
◦Step:6 Decrement j
◦Step: 7Increment i
◦Step:8 Exit

26. code Segment for code Segment for bubble bubble
Sort Sort
01/31/18BY MS. SHAISTA QADIR 26
Code for Bubble Sort
public void bubblesort()
{
int i,n,j;
for(i=0;i<n-1;i++)
{
for(j=n-1;j>i;--j)
if(data[j] < data[j-1])
swap(j,j-1);
}
}

27. beSt, average andbeSt, average and
WorSt caSe for WorSt caSe for bubble Sort bubble Sort
01/31/18BY MS. SHAISTA QADIR 27
◦The number of comparisons is the same in each case (best,
average, and worst) and equals the total number of iterations
of the inner for loop:
◦The best case, when all elements are already ordered, requires
no swaps.
◦And in average case the number of swaps can be any number
between zero and i – 1.
◦The worst case time happens when the array is in reverse
order. Then the outer loop executes n-2 times and for each i,
the inner loop execute for n-1-i times.
◦So the time complexity of the algorithm is

28. diSadvantage of bubble Sort diSadvantage of bubble Sort
01/31/18BY MS. SHAISTA QADIR 28
The main disadvantage of bubble sort is if an element has to be
moved from the bottom to the top, it is exchanged with every
element in the array. It does not skip them as selection sort did.

29. merge Sort merge Sort
01/31/18BY MS. SHAISTA QADIR 29
MERGE SORT (Divide and Conquer)
Merge Sort divides the unsorted array into half repeatedly
until arrays with one element each is obtained.
 Then the divided parts are sorted and then the sorted right
and left parts are merged together.
The key to Merge Sort is merging two sorted arrays into
one, such that
◦if you have two arrays X (x1 < x2 < … < xm) and Y(y1 < y2 < … < yn)
◦the resulting list is Z(z1 < z2 < … < zm+n).

30. illuStration of merge Sort illuStration of merge Sort
01/31/18BY MS. SHAISTA QADIR 30
Divide

31. illustration of merge sort illustration of merge sort
01/31/18BY MS. SHAISTA QADIR 31
Sorting & Merging

32. example of merge sort example of merge sort
01/31/18BY MS. SHAISTA QADIR 32
Example x= {3,10,23,54,1,5,25,75}

33. example of merge sort example of merge sort
01/31/18BY MS. SHAISTA QADIR 33
Example x= {3,10,23,54,1,5,25,75}

34. example of merge sort example of merge sort
01/31/18BY MS. SHAISTA QADIR 34
Example x= {3,10,23,54,1,5,25,75}

35. example of merge sort example of merge sort
01/31/18BY MS. SHAISTA QADIR 35
Example x= {3,10,23,54,1,5,25,75}

36. example of merge sort example of merge sort
01/31/18BY MS. SHAISTA QADIR 36
Example x= {3,10,23,54,1,5,25,75}

37. merge sort algorithmmerge sort algorithm
01/31/18BY MS. SHAISTA QADIR 37
Algorithm to sort elements of sorted arrays X of size m and Y of
size n using Merge Sort in to another array of size m+n.
◦Step:1 Set i=0, j=0,k=0
◦Step:2 If x[i]<=y[j] Go to Step:3 else Go to Step:5
◦Step:3 Set z[k]=x[i], k=k+1, i=i+1, if i<=m, Go to Step:2
◦Step:4 Set z[k],……,z[m+n]=y[j],….y[n]
◦Step:5 Set z[k]=y[j], k=k+1, j=j=j+1, if j<=n, Go to Step:2
◦Step:6 Set z[k],……,z[m+n]=x[i],….x[m]
◦Step:7 Exit

38. 01/31/18BY MS. SHAISTA QADIR 38
THANK YOUTHANK YOU