Comparison Of Sorting Algorithms Information Technology Essay

Published:

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

Consider the first item to be a sorted sub list (of one item). Insert the second item into the sorted sub list, shifting the first item as needed to make room to insert the new addition.

- Insert the third item into the sorted sub list (of two items),shifting items as necessary

- Repeat until all items are inserted into their proper positions.

Pseudo code

for ( i .1 to n-1 ){

temp . Array[ i ]

j = i-1;

while (j=0 & Array[j]>temp){

Array [j+1] . Array [j]

3x

j--;

}

Array [j+1] . temp;

}

Run time = C[ 3(n-1)(n)/2 + n + 3(n-1) ]

C [(3/2) (n(n-1)) + 4n -3) ] f1(n)= 1.5 n2 + 3.5n � 3

Best-case analysis

The best case is when data items are initially in sorted order.

No of comparisons = n-1,No of data moves = 2(n-1),Complexity: (n-1) +2(n-1) = O (n)

Worst-case analysis

The Worst case is when data items are initially in reverse sorted order.

No of comparisons = 1+2+�+ (n-1) =n (n-1)/2

No of data moves = No of comparisons +2(n-1) = n (n-1)/2 +2(n-1)

Complexity: n (n-1)/2 + n (n-1)/2 +2(n-1) = O (n2)

� Advantages

2009CS033 E.M.S.C.B Ekanayake

Page 1

Assignment 2

� Good running time for �almost sorted� arrays Q(n)

� Disadvantages

� Q(n2) running time in worst and average case

� � n2/2 comparisons and exchanges

Selection Sort

Selection sort works by putting each item in its final sorted position, one at a time.

- Find the largest item in the list.

- Switch it with the item in the last position.

- Scan the rest of the list to find the largest item.

- Switch it with the item in the second last position.

- Continue this process for all but the first position in the list(which will end up containing

the smallest item).

No of comparisons = (n-1) + (n-2) +�+1=n (n-1)/2

No of data moves = 3(n-1)

Running time = n (n-1)/2 + 3(n-1) = O (n2)

Pseudo code

for (i . 0 to n-2){

mini;

for (j . i+1 to n-1){

n(n-1)/2

if( Arry[mini]> Array[j] ){

mini = j;

}

}

If (mini != i)

swap(mini)

}

2009CS033 E.M.S.C.B Ekanayake

Page 2

Assignment 2

swap(loc){

temp = Array [i] ;

Array [i] = Array [mini];

Array [mini] = temp;

}

Run time = C [n+ 6(n-1) + 3/2 n (n-1)] f2(n) = 1.5 n2 + 5.5n � 6

Worst-Case

n-1 swaps, n2/2 comparisons. Worst case occurs if the elements are already sorted in the

non-ascending order, because for each iteration the smallest element needs to be swapped

and thus the Worst Case is O (n2).

Best-Case

0 swaps (n-1 as written), n2/2 comparisons. Best case occurs if the elements are already

sorted in non-descending order, because current element is smallest and no element needs

to be swapped and thus the Best Case is O (n2).

Average Case: O (n) swaps and n2/2 comparisons

Disadvantage:

� Running time depends only slightly on the amount of order in the file

Bubble Sort

Bubble sort works by successively comparing adjacent items and exchanging them if they are out

of order.

- The 1st pass runs through all the n items (n-1 pairs of adjacent items).Starting from the 1st

two items through to the last two items in the list. By the end of the 1st pass, the largest

item would have been bubbled to the last position of the list.

2009CS033 E.M.S.C.B Ekanayake

Page 3

Assignment 2

- The 2nd pass runs through first n-1 items (n-2 pairs of adjacent items).By the end of the

2nd pass, the second largest item would have been bubbled to the next-to-last position of

the list.

- Repeat this process for a total of n-1 passes.

Pseudo code

for (i . 0 to n-2)

for (j . n-1 down to i+1)

if (Array [j-1] > Array [j])

swap( j )

swap(loc){

temp = Array [j] ;

Array [j] = Array [j-1];

Array [j-1] = temp;

}

Run time = C [n+ n-1 + 2{n(n-1)}] f3(n) = 2n2 + 1

Best-case analysis

The best case is when the data items are initially in sorted order.

No of comparisons =( n-1) + (n-2)+�+1= n(n-1),No of data moves = 0

Complexity: n(n-1)/2+0= O(n2)

Worst-case analysis

- The Worst case is when data items are initially in reverse sorted order.

No of comparisons = 1+2+�+ (n-1) =n (n-1)/2

No of data moves = 3(No of comparisons)= 3n (n-1)/2

Complexity: n (n-1)/2 +3 n (n-1)/2 = O (n2)

2009CS033 E.M.S.C.B Ekanayake

Page 4

Assignment 2

Name Best Average Worst Memory Stable Method

Insertion sort O(n) O(n

+ d) O(n2) O(1) Yes Insertion

Selection sort O(n2) O(n2) O(n2) O(1) No Selection

Bubble sort O(n) � O(n2) O(1) Yes Exchanging

Loop invariants of the above algorithms.

Insertion Sort

Insertion sort takes one element and compares it with all the other elements in the array

and then puts it in to the place it fits. Therefore until the final element is placed at the

right position we cannot give an exact place to any of the elements in the array. But with

each iteration the sub array is sorted, although the elements are not in fixed positions. The

loop invariant in this is the condition that at least one element in the sub array is sorted

accordingly.

Selection Sort

The outer loop of the algorithm counts up from j = 0 each time through the loop, the

minimum remaining value is put in a[j] Our invariant is: for all i <= outer, if i < j then a[i]

<= a[j]The inner loop of this algorithm searches through the array, incrementing i from

its initial value of j+1 up to array lengh-1as the loop proceeds, min is set to the index of

the smallest number found so far in our invariant.

Bubble Sort

Bubble sort works by comparing two neighboring elements and interchanging them if

they are not in a specified order. This process is done repeatedly with each iteration, from

one end to the other end of the list until no swaps are needed to be done. Therefore one

end of the sub array consists of sorted elements which won�t change their positions

during the lifetime of the loop. Other end of it consists of elements which are to be sorted

in the up-coming iterations.

Conclusion

According to above definitions can get the idea about three sorting algorithm. So

2009CS033 E.M.S.C.B Ekanayake

Page 5

Assignment 2

Performs as many comparisons as selection sort. If the input array is already sorted, insertion

sorts. Performs as few as n-1 comparisons, thus making insertion sort more efficient when given

sorted or "nearly-sorted" arrays.

There exist many sorting algorithms with substantially better worst-case or average complexity

of O (n log n). Even other . (n2) sorting algorithms, such as Insertion sort, tend to have better

performance than bubble sort. Therefore bubble sort is not a practical sorting algorithm when n is

large.

2009CS033 E.M.S.C.B Ekanayake

Page 6

Assignment 2

2009CS033 E.M.S.C.B Ekanayake

Page 7

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.