Bubble sort and quick sort in ascending order

Assignment Help Data Structure & Algorithms

Reference no: EM13189279

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: EM13189279

Questions Cloud

Characteristic of a realigning election : All of the following are characteristic of a realigning election except

What is the maximum number of whole gallons of paint : If one gallon of paint has a volume of approximately 4000 cm3, what is the maximum number of whole gallons of paint that can be poured into the bucket?

What percent of gdp does the us spend on health care : What percent of GDP does the US spend on Health care The UK Canada Do you think the United States spends too much on medical care Explain your reasoning using the PPF model List and explain the 3 reasons for this increase.

Is rare condition in which brain fails to develop at levels : Is a rare condition in which the brain fails to develop at levels above the

Bubble sort and quick sort in ascending order : Quick sort in ascending order, with partition choosing pivot in the middle of the sub-array.

Find the mean of the distribution shown : Find the mean of the distribution shown.

How to set up and solve equations and inequalities : What is the importance of understanding how to set up and solve equations and inequalities.

How the program to impact the firms bottom line : Ford executives announced that the company would extend its most dramatic consumer incentive program in the company's long history-- the Ford Drive America Program. The program provides consumers with either cash back or zero percent financing for..

What about the second equation : How are they different? Find a problem in the text that is similar to examples 2, 3, and 4. Post the problem for your classmates to solve.

User Account

All Pages