Question 1a bubble sort in ascending order1 pseudo

Assignment Help Data Structure & Algorithms

Reference no: EM13380149

Question 1:

(a) Bubble sort in ascending order.

1. Pseudo code:

FUNCTION BubbleSortIMPORT array EXPORT array

FOR pass ¬ 0 TO (array.length-1)-1 DO¬Need N-1 passes to guarantee sorted

FOR ii ¬ 0 TO (array.length-1 - pass)-1 DO¬NOTE: 0-based array indexing

IF (array[ii] > array[ii+1]) THEN¬Avoid >= to keep the sort stable

temp ¬ array[ii]¬Swap out-of-order elements ii and ii+1

array[ii] ¬ array[ii+1]

array[ii+1] ¬ temp

ENDIF

ENDFOR

ENDWHILE

(b) Quick sort in ascending order, with partition choosing pivot in the middle of the sub-array.

2. Pseudo code:

FUNCTION QuickSort IMPORT array, leftIdx, rightIdx EXPORT array

IF (rightIdx > leftIdx) THEN¬Check that the array is > one element in size

pivotIdx¬ (leftIdx+rightIdx) / 2¬Pivot selection strategy: middle element

newPivotIdx¬ doPartitioning(array, leftIdx, rightIdx, pivotIdx)

QuickSort(array, leftIdx, newPivotIdx-1)¬Recurse: Sort left partition

QuickSort(array, newPivotIdx+1, rightIdx)¬Recurse: Sort right partition

//ELSE

// Base case: array is 1 element or smaller in size - already sorted

ENDIF

ENDFUNCTION

FUNCTION doPartitioning IMPORT array, leftIdx, rightIdx, pivotIdx EXPORT newPivotIdx

pivotVal¬ array[pivotIdx]

array[pivotIdx] ¬ array[rightIdx]¬Swap the pivotVal with the right-most element

array[rightIdx] ¬ pivotVal

// Find all values that are smaller than the pivot

// and transfer them to the left-hand-side of the array

currIdx¬ leftIdx

FOR (ii ¬ leftIdx TO rightIdx-1)

IF (array[ii] <pivotVal) THEN¬Find the next value that should go on the left

temp¬ array[ii]¬Put this value to the left-hand-side

array[ii] ¬ array[currIdx]

array[currIdx] ¬ temp

currIdx¬ currIdx + 1

ENDIF

ENDFOR

newPivotIdx¬ currIdx

array[rightIdx] ¬ array[newPivotIdx]¬Put the pivot into its rightful place (the value at

array[newPivotIdx] ¬ pivotVal[newPivotIdx] is >= pivotVal, so it can be put to the end)

ENDFUNCTION

3. Pseudo code:

FUNCTIONShellSortIMPORTsize

for (inc¬size/2 inc>0inc /= 2)

for (i¬inci< sizei++)

j¬i - inc

while (j >= 0)

if (a[j] > a[j+inc])

swap a[j] and a[j+inc]

j -¬inc

else

j¬-1

ENDFUNCTION

(d) Heap sort in ascending order.

4. Pseudo code:

FUNCTIONHeapSortIMPORTsize

for (i¬ size/2 i>= 0i--)

ReHeap(size, i)

for (i¬ size-1 i> 0i--)

swap a[i] and a[0]

ReHeap(i, 0)

ENDFUNCTION

FUNCTIONReHeapIMPORTlen, parent

temp¬a[parent]

child¬2*parent + 1

while (child <len)

if (child<len-1 and a[child]<a[child+1])

child++

if (temp >= a[child])

break

a[parent] = a[child]

parent¬child

child ¬2*parent + 1

a[parent] ¬temp

ENDFUNCTIONTime Analysis of Mergesort

Assumption: N is a power of two.

For N = 1: time is a constant (denoted by 1)

Otherwise: time to mergesort N elements = time to mergesort N/2 elements plus time to merge two arrays each N/2 elements.

Time to merge two arrays each N/2 elements is linear, i.e. N

Thus we have:

(1) T(1) = 1

(2) T(N) = 2T(N/2) + N

Next we will solve this recurrence relation. First we divide (2) by N:

(3) T(N) / N = T(N/2) / (N/2) + 1

N is a power of two, so we can write

(4) T(N/2) / (N/2) = T(N/4) / (N/4) +1

(5) T(N/4) / (N/4) = T(N/8) / (N/8) +1

(6) T(N/8) / (N/8) = T(N/16) / (N/16) +1

(7) ......
(8) T(2) / 2 = T(1) / 1 + 1

Now we add equations (3) through (8) : the sum of their left-hand sides
will be equal to the sum of their right-hand sides:

T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + T(2)/2 =

T(N/2) / (N/2) + T(N/4) / (N/4) + T(2) / 2 + T(1) / 1 + LogN

(LogN is the sum of 1s in the right-hand sides)

After crossing the equal term, we get

(9) T(N)/N = T(1)/1 + LogN

T(1) is 1, hence we obtain

(10) T(N) = N + NlogN = O(NlogN)

Hence the complexity of the MergeSort algorithm is O(NlogN).

Reference no: EM13380149

Questions Cloud

What kind of measurement scales ratio interval etc : what kind of measurement scales ratio interval etc. characterizes the following software measuresi. number of lines of

You are the cio of a successful accounting firm with : you are the cio of a successful accounting firm with offices in cities across the nation.nbsp you recently attended a

Submit your programs by email the program should have as : submit your programs by email. the program should have as many comments as necessary. the top comments should explain

You must have at least these entities region factory : you must have at least these entities region factory employee department training class. you should use the attributes

Question 1a bubble sort in ascending order1 pseudo : question 1a bubble sort in ascending order.1. pseudo codefunction bubblesortimport array export arrayfor pass not 0 to

Question 1you are required to create a detailed analysis : question 1you are required to create a detailed analysis for each of the following array-based sorting algorithmsa

Determine if a word is a palindrome using a doubly link : determine if a word is a palindrome. using a doubly link list read in a word character by character store each

Using a random number generator create an input file that : using a random number generator create an input file that contains 25 numbers ranging from 50 to 100 store those

You have been asked to be the project manager for the : you have been asked to be the project manager for the development of an information technology it project. the system

User Account

All Pages