Assignment: #2 Solution

$30.00

Description

1. XSort Algorithm

(a)

EX AM P LE AX EM P LE AEX M P LE AEEM P LX

AEELP M X AEELM P X

(b) Time Efficiency: O(n2 ) Space Efficiency: O(1)

(c) Stability in an algorithm refers to the ordering of elements of same values in the final sorted list. A stable algorithm will keep elements of the same value in the same order as they appeared in the unordered list. This algorithm is not stable. This is shown when givent the list [2, 2, 1]; the first 2 element is swapped with 1 resulting in [1, 2, 2] and the original order of the equal elements is now changed.

2. Bubble Sort

(a)

EX AM P LE EAX M P LE EAM X P LE EAM P X LE

EAM P LX E EAM P LEX AEM P LEX AEM P LEX

AEM P LEX AEM LP EX AEM LEP X AEM LEP X

AEM LEP X AELM EP X AELEM P X AELEM P X

AELEM P X AEELM P X AEELM P X AEELM P X

AEELM P X

(b) Bubble sort works by progressively swapping larger elements with smaller elements to the right. If no swaps occur during the pass through the array, then the list is sorted.

(c) This sort is stable because the comparison is testing to see if alist[x] > alist[x + 1] rather than list[x] list[x + 1]. Thus, a swap is only made if element x is larger than element x+1.

3. Show that n2 O(n2 + 10n), n 0

Choose c = 1

n2 n2 + 10n, while n > 0

0 c10n

because this holds true, n2 O(n2 + 10n)

4. Show that n 6 Ω(n2 )

if f (n) Ω(g(n)), then f (n) cg(n)

n cn2, while c > 0

c

1 cn n 1

c

because n > 1 , then n 6 Ω(n2)