# A Guide To The Practice Of Sorting Algorithms Engineering Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

SortingAlgorithmsBasic idea of sorting algorithm is arranging fundamentals of a list in a firm order. Sorting algorithms

is mainly done according to the quantitative complexity which means worst case, best case and

average case. Efficiency of an algorithm mostly depends on the size of the list.

Run-timeAnalysisPseudo codefor each kinds ofSortCostBest-

CaseAverage-

CaseWorse-

CaseSelection SortSelection sort (int[] sort) C1 1 1 1

n . array_length C2 1 1 1

temp = 0 C3 1 1 1

for( j from 0 to n-2) C4 (n) (n) (n)

do temp=sort[j] C5 (n-1) (n-1) (n-1)

min = j C6 (n-1) (n-1) (n-1)

for (i from j+1 to n-1) C7

do if( sort[min]>sort[i]) C8

do min=i C9 0 0 0

sort[j]=sort[min] C10 (n-1) (n-1) (n-1)

sort[min]=temp C11 (n-1) (n-1) (n-1)

return sort C12 1 1 1

Bubble SortBubble sort (int[] sort) C1 1 1 1

n . array_length C2 1 1 1

temp = 0 C3 1 1 1

for(( i from n-1 to 1) C4 (n) (n) (n)

for (j from 1 to i) C5

if( sort[min]>sort[i]) C6

min=i C7 0

sort[j]=sort[min] C8 0

sort[min]=temp C9 0

return sort C10 (n) (n) (n)

Insertion SortInserting sort (int[] sort) C1 1 1 1

n . array_length C2 1 1 1

Temp,j = 0 C3 1 1 1

for( i from 1 to n) C4 (n+1) (n+1) (n+1)

temp=sort[i] C5 (n) (n) (n)

j = i C6 (n) (n) (n)

while (j > 0 And sort[j-1] >

temp)

C7 -1 -1

sort[j] = sort[j-1] C8 0

j--C9 0

sort[j] = temp C10 (n) (n) (n)

return sort C11 (n) (n) (n)

-1

SortingAlgorithmsBasic idea of sorting algorithm is arranging fundamentals of a list in a firm order. Sorting algorithms

is mainly done according to the quantitative complexity which means worst case, best case and

average case. Efficiency of an algorithm mostly depends on the size of the list.

Run-timeAnalysisPseudo codefor each kinds ofSortCostBest-

CaseAverage-

CaseWorse-

CaseSelection SortSelection sort (int[] sort) C1 1 1 1

n . array_length C2 1 1 1

temp = 0 C3 1 1 1

for( j from 0 to n-2) C4 (n) (n) (n)

do temp=sort[j] C5 (n-1) (n-1) (n-1)

min = j C6 (n-1) (n-1) (n-1)

for (i from j+1 to n-1) C7

do if( sort[min]>sort[i]) C8

do min=i C9 0 0 0

sort[j]=sort[min] C10 (n-1) (n-1) (n-1)

sort[min]=temp C11 (n-1) (n-1) (n-1)

return sort C12 1 1 1

Bubble SortBubble sort (int[] sort) C1 1 1 1

n . array_length C2 1 1 1

temp = 0 C3 1 1 1

for(( i from n-1 to 1) C4 (n) (n) (n)

for (j from 1 to i) C5

if( sort[min]>sort[i]) C6

min=i C7 0

sort[j]=sort[min] C8 0

sort[min]=temp C9 0

return sort C10 (n) (n) (n)

Insertion SortInserting sort (int[] sort) C1 1 1 1

n . array_length C2 1 1 1

Temp,j = 0 C3 1 1 1

for( i from 1 to n) C4 (n+1) (n+1) (n+1)

temp=sort[i] C5 (n) (n) (n)

j = i C6 (n) (n) (n)

while (j > 0 And sort[j-1] >

temp)

C7 -1 -1

sort[j] = sort[j-1] C8 0

j--C9 0

sort[j] = temp C10 (n) (n) (n)

return sort C11 (n) (n) (n)

-1

Run Time of Best-Case

Selection

Sort

Run-Time(Best-Case) = C1+ C2+ C3+ C4.(n+1)+ C5.n+ C6.n+ C7. +C8. +C9.0+

C10.n+ C11.n+ C12.1 =T(n2)

Bubble

Sort

Run-Time = C1.1+ C2.1+ C3.1+ C4.(n)+ C5. + C6. + 0(C7 + C8+ C9) + C10.n = T (n2)

Insertion

Sort

Run-Time = C1.1+ C2.1+ C3.1+ C4.(n)+ C5. + C6. + 0(C7 + C8+ C9) + C10.1 = T (n2)

Run Time of Average

Case

Selection

Sort

Run-Time(Best-Case) = C1+ C2+ C3+ C4.(n+1)+ C5.n+ C6.n+ C7. +C8. +C9.0+

C10.n+ C11.n+ C12.1 =T(n2)

Bubble

Sort

Run-Time = C1.1+ C2.1+ C3.1+ C4.(n)+ C5. + C6. + 0(C7 + C8+ C9) + C10.n = T (n2)

Insertion

Sort

Run-Time = C1.1+ C2.1+ C3.1+ C4.(n)+ C5. + C6. + 0(C7 + C8+ C9) + C10.1 = T (n2)

Run Time of Worse-Case

Selection

Sort

Run-Time(Best-Case) = C1+ C2+ C3+ C4.(n+1)+ C5.n+ C6.n+ C7. +C8. +C9.0+

C10.n+ C11.n+ C12.1 =T(n2)

Bubble

Sort

Run-Time = C1.1+ C2.1+ C3.1+ C4.(n)+ C5. + C6. + 0(C7 + C8+ C9) + C10.n = T (n2)

Insertion

Sort

Run-Time = C1.1+ C2.1+ C3.1+ C4.(n)+ C5. + C6. + 0(C7 + C8+ C9) + C10.1 = T (n2)

Summary of Run-times Analysis.

In this table, n is the number of records to be sorted. The columns give the time complexity in

each case, under the supposition that the length of each key is constant, and that therefore all

needed operations can proceed in constant time. These are all comparison sorts.

Algorithm

Best-Case

Average-Case

Worse-Case

Selection Sort T (n2) T (n2) T (n2)

Bubble Sort T (n2) T (n2) T (n2)

Insertion Sort T (n) T (n2) T (n2)

Comparison of sorting algorithms

Among simple average-case T(n2) algorithms, selection sort always outperforms bubble sort

and outperformed by insertion sort. Insertion sort is very similar in that after the ith iteration,

the first i

elements in the array are in sorted order. Advantage of insertion sort is that it only

checks as many elements as it needs in order to place the i

+ 1st element, while selection sort

must check all remaining elements to find the i

+ 1st element. Usually insertion sort will

execute about half as many comparisons as selection sort, although it can perform just as

many or far fewer depending on the order the array was in prior to sorting. It can be seen as

an advantage for some real-time applications that selection sort will perform identically in

spite of the order of the array, while insertion sort's running time can differ significantly.

2009CS032-S.K.Edwin Page 2

Another difference is that selection sort always performs T(n) swaps, while insertion sort

performs T(n2) swaps in the average and worst cases. Finally, selection sort is greatly

outperformed on larger arrays by T(n log n) as merge sort algorithms. However, insertion

sort or selection sort are both usually faster for small arrays (fewer than 10-20 elements).

Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case,

but the two algorithms differ greatly in the number of swaps necessary.

Enhanced Algorithms

Enhanced selection

sort

if size > 1 then

var index, temp, max

index := size-1

max := array(index)

for a:= 0 to size-2 do

if array(a) = max then

max := array(a)

index := a

end if

end for

if index . size-1 then

temp := array(size-1)

array(size-1) := max

array(index) := temp

end if

size := size-1

return Enhanced Selection Sort (array , size)

else

return array

end if

By comparing the selection sort with enhanced selection sort algorithm, the main advantage

is, if the input array is already sorted, the enhanced selection sort does not perform any swap

operation, but selection sort performs n swap operations. If the array is stored in a secondary

memory; then the selection sort will operate in relatively low performance as compared with

enhanced selection sort. That means the specific data sets are already sorted arrays.

Enhanced bubble

sort

Boolean sortedï¿½

false

for (i from 1 to n AND !sorted)

Sortedï¿½true

for (j from 0 to n-1)

if array[j] > array[j+1] then

tempï¿½array[j]

array[j]ï¿½array[j+1]

array[j+1]ï¿½temp

sortedï¿½false

end if

end for

2009CS032-S.K.Edwin Page 3

SCS1006-Assignment02

end for

The main point of determine the performance of bubble sort is positions of the elements.

Large elements at the beginning of the list are quickly swapped, while small elements at the

beginning move to the top extremely slowly. Bubble sort algorithm makes n comparisons at

the first time, and then it makes n-1 comparisons, and so on. In enhanced bubble sort

algorithm, decreasing the number of comparisons by two each call led the complexity to be

O(n) which is very much better than O(n2). The difference between enhanced bubble sort and

bubble sort may not be clear with a small size of the input array, but with a large size it is

very clear that enhanced bubble sort is faster than bubble sort. The specific data sets are

already sorted arrays.

Enhanced insertion

sort

Inserting sort (int[] sort)

n ï¿½ array_length

Temp,j ï¿½

0

for( i from 2 to n)

if array[i] < array[i - 1] then

tempï¿½array[i]

j ï¿½ i

while (j > 0 And array[j-1] > temp)

array[j] ï¿½

array [j-1]

j-end

while

array [j] ï¿½

temp

end if

end for

return sort

The insertion sort does not perform any comparison or swap if the array is already sorted.

Loops Invariant of above algorithms

Insertion

Sort

In insertion sort, the outer loop is,

for (outer = 1; outer < array. length; outer++) {...}

The invariant is that all the elements to the left of outer are sorted with respect to one another.

For all i < outer, j < outer, if i < j then a[i] <= a[j]

This does not mean they all are in their final correct place, the remaining array elements may

need to be inserted. When we increase outer, a[outer-1] becomes to its left; we must keep the

invariant true by inserting a[outer-1] into its proper place. This means, finding the elementï¿½s

proper place, making room for the inserted element (by shifting over other elements) and

inserting the element.

Selection

Sort

In Selection Sort always there are two loops. In the inner loop, it searches through the array,

incrementing inner from its initial value of outer+1 up to array.length-1. As the loop

proceeds, min is set to the index of the smallest number found so far. The invariant is that for,

all i, such that outer <= i <= inner, a[min] <= a[i]

2009CS032-S.K.Edwin Page 4

SCS1006-Assignment02

In the outer (enclosing) loop, it counts up from outer = 0. Each time through the loop, the

minimum remaining value is put in a[outer].The invariant for that is for,

all i <= outer, if i < j then a[i] <= a[j].

Bubble

Sort

In Bubble Sort, usually put the largest elements at the end and once put them there, donï¿½t

move them again. The variable outer starts at the last index in the array and decreases to 0.

The invariant is that every element to the right of outer is in the correct place. That is for,

All j > outer, if i < j, then a[i] <= a[j]

When this is combined with the loop exit test, outer == 0, could be known that all

elements

of the array are in the correct place.

2009CS032-S.K.Edwin Page 5