Sorting Algorithms

Question 1

A sorting algorithm is ______________ if its sorts by comparing the items

Answer 1

Comparison based sorting

Question 2

Bubble sort Best, Average, and Worst Case

Answer 2

O(n^2)

Question 3

Selection Sort Best, Average, and Worst Case

Answer 3

O(n^2)

Question 4

Heapsort Best, Average, and Worst Case

Answer 4

O(n log n)

Question 5

divides the array to sorted and unsorted sections, and keeps on inserting elements to the sorted section from the unsorted part

Answer 5

Insertion Sort

Question 6

An algorithm that doesn’t require extra proportional space.,

Answer 6

in-place algorithm (eg. Insertion Sort)

Question 7

divide and conquer sorting algorithms

Answer 7

Merge Sort & Quick Sort

Question 8

Insertion Sort Pseudo code

Answer 8

insertionsort(int a[], int n){

int i,j;
for(i=1;i<n;i++)
for(j=i: j>0; j–)
if(a[j-1] > a[j])
swap(&a[j-1],&a[j]_)
else
break;
}

Question 9

Merge Sort Pseudo codeO(n log n)

Answer 9

mergesort(int a[], int
lower, int upper){

int mid;
if(upper-lower>0){
mid = (lower + upper)/2;
mergesort(a,lower,mid);
mergesort(a,mid+1,upper);
merge(a, lower,mid,upper);

Question 10

Merge sort runs in ____________ time.

Answer 10

O(n log n)

Question 11

T or F:

Merge sort sorts in-place.

Answer 11

False. Merge sort uses extra memory

Question 12

QuickSort Pseudo code

Answer 12

QUICKSORT(A,start,pivot):

if start < pivot:
q = PARTITION(A,start,pivot)
QUICKSORT(A,start,q-1)
QUICKSORT(A,q+1,pivot)

PARTITION(A,start,pivot):
x = A[pivot]
i = start-1
for j = start to pivot-1:
if A[j] <= x:
i = i+1
swap A[i] with A[j]

swap A[i+1] with A[PIVOT]

return i+1

Question 13

Quicksort runs in ______ time in the worst-case

Answer 13

O(n^2)

Question 14

Quicksort runs in the ____________ time for best and average cases.

Answer 14

O(n log n)

Question 15

T or F

Quicksort sorts in-place

Answer 15

T

Question 16

Insertion sort Best, Average, and Worst Case Run Time

Answer 16

BEST: O(n)
AVERAGE: O(n^2)
WORST: O(n^2)

Question 17

Merge sort Best, Average, and Worst Case Run Time

Answer 17

O(n log n) for all

Question 18

Quicksort Best, Average, and Worst Case Run Time

Answer 18

BEST: O(n log n)
AVERAGE: O(n log n)
WORST: O(n^2)

Question 19

Examples of non comparison-based Sorting

Answer 19

Counting Sort
Radix Sort

Question 20

__________________ assumes that the elements are integers that range from 0 to k, for some integer k.

Answer 20

Counting sort

Question 21

Counting Sort Pseudo code

Answer 21

COUNTING-SORT(A,n,k):
let B[1:n] and C[0:k] be arrays

for i=0 to k: //init
C[i] = 0
for j=1 to n: //freq
C[A[j]] = C[A[j]] + 1
for i=1 to k: //position
C[i] = C[i] + C[i-1]
//copy A to B, start from end of A
for j=n downto 1:
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]]-1

return B

Question 22

Counting sort runtime

Answer 22

O(n+k) time

Question 23

A sorting algorithm is said to be _________, when elements with the same value appear in the output array in the same order as they did in the input array

Answer 23

Stable (ie. Counting Sort)

Question 24

Used by card-sorting machines for punch cards

Answer 24

Radix Sort

Question 25

Radix sort counterintuitively sorts on the ________________ digit first.

Answer 25

least significant

Question 26

For radix sort to work correct, the sort must be _________.

Answer 26

stable

Question 27

Radix sorts assumes that the elements in the array has d digits

Answer 27

TRUE

Question 28

Radix Sort pesudocode

Answer 28

Radix-Sort(A,n,d):
for i=1 to d:
use a stable sort to sort the array on digit i (egg. COUNTING-SORT)