Print Email Download Reference This Send to Kindle Reddit This
submit to reddit

Comparison Of Sorting Algorithms Information Technology Essay

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

Print Email Download Reference This Send to Kindle Reddit This

Share This Essay

To share this essay on Reddit, Facebook, Twitter, or Google+ just click on the buttons below:

Request Removal

If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please click on the link below to request removal:

Request the removal of this essay.


More from UK Essays