Sorting

Question 1

when does insertion sort run in linear time?

Answer 1

when the number of inversions is order of N

Question 2

This is the algorithm of choice for up to moderately large input.

Answer 2

Shell sort

Question 3

What is the mergeSort caller algorithm?

Answer 3

• mergeSort(array [] a)
  
  • Array [] b = new Array[a.length];
  • Mergesort(a, b, 0, a.length-1);

Question 4

Derive the runtime analysis of Mergesort

Answer 4

Question 5

The number of comparisons is nearly optimal for these two algorithms.

Answer 5

heapsort, mergesort

Question 6

What is the recurrence analysis of Mergesort?

Answer 6

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

Question 7

Describe the partitioning algorithm for quicksort

Answer 7

• The first step of the partitioning strategy gets the pivot elements out of the way by swapping it with the last element.
  
  • I starts at the first element and j starts at the second to last element.
  • While I is to the left of j, we move I right, skipping over elements that are smaller than the pivot.
  • We move j left, skipping over elements that are larger than the pivot.
  • When I and j have stopped, I is pointing at a large element and j is pointing at a small element (relative to the pivot).
  • If I is to the left of j, those elements are swapped.
    
    • We repeat this process until I and j cross.
  • The final part of the partitioning is to swap the pivot element with the element pointed to by i.

Question 8

what is the form of sedgewicks sequence?

Answer 8

9*4^i -9*2^i + 1, this is most easily implemented using an array.

Question 9

Analysis of recursive algorithms always requires what?

Answer 9

Solving a recurrence relation

Question 10

What is the recurrence relation for quicksort?

Answer 10

T(N) = T(i) +T(N-i-1) + cN, where i equal the size of the first partition

Question 11

How many comparisons are used by heapsort in the absolute worst case?

Answer 11

2NlogN-O(N)

Question 12

What is the worst possible choice for a pivot and why?

Answer 12

The first and last element, because if the input is already sorted, quicksort will take quadratic time to do nothing

Question 13

Quicksort is commonly used in what language?

Answer 13

C++

Question 14

Describe Radix sort

Answer 14

Radix sort assumes we know the range of integers to be sorted.

We choose a radix, say r = 10.

We create r temporary lists.

In the first pass we go through the original list, copying values into the linked lists, based on their least significant digit.

We concatenate the temporary lists and restart the process based on the second digit, and so on.

Question 15

What is the worst case runtime and average run time of quickselect?

Answer 15

O(N^2) and O(N)

Question 16

What is the merge algorithm?

Answer 16

• Merge(array[] a, array[] b, int left, int rightPos, int rightEnd)
  
  • Int leftEnd = rightPos -1;
  • Int bcounter = left;
  • Int numElements = rightEnd - left + 1;
  • While(leftPos <= leftEnd && rightPos <= rightEnd)
    
    • If(a[leftPos] < a[rightPos]) b[bcounter++] = a[leftPos++];
    • Else b[bcounter++] = a[rightPos++];
  • While(leftPos<= leftEnd) b[bcounter++] = a[leftPos++];
  • While(rightPos<= rightEnd) b[bcounter++] = a[rightPos++];
  • For(int i = 0; i < numElements; i++, rightEnd–) a[rightEnd] = b[rightEnd];

Question 17

What is the mergesort algorithm?

Answer 17

• Mergesort(array [] a, tempArray b[], int left, int right)
  
  • If(left < right) // this is the base case
    
    • Int center = (left+right)/2;
    • mergeSort(a, b, left, center)
    • mergeSort(a, b, center+1, right)
    • Merge(a, b, left, center+1, right)

Question 18

What is external sorting?

Answer 18

sorting that takes place on external memory because the items are too numerous to fit in main memory.

Question 19

Using a priority queue, we can find the kth largest number in what time?

Answer 19

O(N + klogN)

Question 20

Prove that the comparisons needed for any comparison based sorting algorithm is NlogN

Answer 20

Question 21

Describe insertion sort:

Answer 21

Insertion sort consists of N-1 passes. For pass p =1 through N-1, insertion sort ensures that the elements in positions 0 through p are in sorted order. Insertion sort makes use of the fact that elements in positions 0 through p-1 are already known to be in sorted order.

Question 22

Information-theoretic lower bound states what?

Answer 22

Information-theoretic lower bound- if there are P different possible cases to distinguish, and the questions are of the form Yes/No, then ceiling(log P) questions are always required to solve the problem.

Question 23

What is a stable sorting algorithm?

Answer 23

Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

Question 24

What is the best case scenario for quick sort?

Answer 24

In the best case, the pivot picked always belongs in the middle of the array creating two equal subarrays.

Question 25

What is the Simple Quick Sort algorithm?

Answer 25

• SimpleQuicksort(List items)
• If(items.size() > 1)
  
  • List smaller = new ArrayList<>();
  • List same = new ArrayList<>();
  • List larger = new ArrayList<>();
  • Integer chosenItem = items.get(items.size()/2)
  • For(Integer I : items)
    
    • If(I < chosenItem)
      
      • Smaller.add(i)
    • Else if(I > chosenItem)
      
      • Larger.add(i)
    • Else
      
      • Same.add(i)
  • Items.clear();
  • Items.addAll(smaller);
  • Items.addAll(same);
  • Items.addAll(larger);

Question 26

any algorithm that sorts by exchanging adjacent elements requires what time on average?

Answer 26

N²

Question 27

What kind of pivot selection can guarantee linear time of quickselect?

Answer 27

The median of median of five.

Question 28

What was one of the first algorithms to break the quadratic barrier?

Answer 28

Shell Sort

Question 29

Describe Shell sort

Answer 29

• Shellsort compares elements that are distant; the distance between comparisons decreases as the algorithm runts until the last phase, in which adjacent elements are compared.
  
  • For this reason, Shellsort is sometimes referred to as diminishing increment sort.
  • Shellsort starts with an increment sequence. Any increment sequence will do so long has it ends with 1.
    
    • After a phase of some increment k, we have a[i] <= a[i + k].

Question 30

What is the average runtime of quicksort?

Answer 30

O(N log N)

Question 31

What is the worst case runtime of quicksort?

Answer 31

O(N^2)

Question 32

Analyze the best case runtime of Quicksort

Answer 32

Question 33

What algorithm uses the lowest number of comparisons?

Answer 33

mergesort

Question 34

When using quicksort, what should happen when elements equal to the pivot are encountered and why?

Answer 34

• If an element is encountered that is equal to the pivot, I and j should both stop.
  
  • This will cause many swaps between identical objects, if all elements in the array are identical.
  • If neither stop, the pivot will swap with the last element I touched, which will be the next to last element, creating uneven subarrays and an O(N^2) runtime.
  • If both stop, and all items are identical, the sorting algorithm will have O(N log N) runtime.

Question 35

What is a good cutoff for quicksort?

Answer 35

N = 10;

Question 36

What is shellSort?

Answer 36

a simple to code sorting algorithm that runs in O(n^2), and is efficient in practice.

Question 37

the median of a group of N numbers is

Answer 37

The N/2th largest number

Question 38

Describe bucket sort

Answer 38

We keep an array called count of size M initialized to all zeros. Linearly run through the array[] incrementing count: ++count[array[i]]. We then scan the count array and print in order.

Question 39

What is the number of worst case comparisons for merging?

Answer 39

N-1

Question 40

what is the runtime of heapsort?

Answer 40

O(n log N)

Question 41

What are the four steps to quick sort?

Answer 41

• If the number of elements in S is 0 or 1, then return;
• Pick any element v in S. This is called the pivot.
• Partition S- the pivot into two disjoint sets of respectively larger and smaller arrays.
• Return quicksort on both disjoint sets.

Question 42

When is radix sort optimal?

Answer 42

When we know a range of the values M, and log_r M < log₂ N

Question 43

Describe the merging algorithm of mergesort

Answer 43

• The basic merging algorithm takes to arrays A and B, and an output array with three counters. The first two counters progress up A and B comparing the two and placing the lesser in C. Whichever counter was placed in C is then incremented, and the process continues until either input list is exhausted, and the remainder of the other list is copied into C.

Question 44

Describe the quicksort algorithm

Answer 44

• Arbitrarily choose any item, and then form three groups: those smaller than the chosen item, those equal to the chosen item, and those larger than the chosen item.
• Recursively sort the first and third group, and then concatenate the three groups.
  
  • The result is a guaranteed sorted list.

Question 45

What is the main problem with heap sort and how can we correct it?

Answer 45

• The main problem with heap sort is that it uses an extra array, but this can be avoided by taking advantage of the open spot in the original array after a deleteMin has occurred. Each object that is ejected after a deleteMin operation can then be placed in the last position of the original array.
  
  • We can create a maxHeap to have the original array end in increasing order, rather than decreasing order.

Question 46

What is an inversion?

Answer 46

an inversion in an array of numbers is any ordered pair (i, j) having the property that i < j, but array[i] > array[j].

Question 47

describe heapsort

Answer 47

First a binary heap of N elements is built in O(N) time, followed by N deleteMin operations, each of which take O(log N ) time.

Question 48

Any general-purpose sorting algorithm requires how many comparisons?

Answer 48

a simple to code sorting algorithm that runs in O(n^2), and is efficient in practice.

Question 49

After quickselect terminates, the kth largest/smallest element is in what position?

Answer 49

k-1

Question 50

What is the insertion sort algorithm?

Answer 50

○ insertionSort(array [])
§ Int j;
§ For (int p = 1; p < array.size(); p++)
□ Object Temp = array[p];
□ For(j = p; j > 0 && array[j] < array[j-1]; j–)
® a[j] = a[j-1]
□ a[j] = tmp;

Question 51

What is the runtime of bucket sort?

Answer 51

• The runtime is O(M+N), and if M is O(N) then the total is O(N)

Question 52

What is the time to merge two sorted lists?

Answer 52

Linear

Question 53

What is the quickselect algorithm?

Answer 53

• quickSelect(array [] a, int left, int right, int k)
  
  • If(left + cutoff < right)
    
    • Pivot = median3(a, left, right);
    • Int i = left, int j = right -1
    • For(;;)
      
      • While(a[++i] < pivot){}
      • While(a[–j] > pivot){}
      • If(i < j) swap(i, j)
      • Else break;
    • Swap(i, right -1);
    • If(k <= i)
      
      • Quickselect(a, left, i-1, k)
    • If(k>i+1)
      
      • Quickselect(a, i+1, right, k)
  • Else
    
    • InsertionSort(a, left, right)

Question 54

• Sorting: 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15 with a {1, 3, 5] increment sequence:

Answer 54

• 35, 17, 11, 28, 12, 41, 75, 15, 96, 58, 81, 94, 95
• 28, 12, 11, 35, 15, 41, 58, 17, 94, 75, 81, 96, 95
  
  • 11, 12, 15, 17, 28, 35, 41, 58, 75, 81, 94, 95, 96

Question 55

What are Hibbard’s suggested increments for Shellsort, and what is the running time using them?

Answer 55

O(N^1.5), 1, 3, 7, ….2^k-1

Question 56

List the inversions for {3, 1, 9, 5, 4, 2}

Answer 56

(3,1) (3,2) (9,5) (9,4) (9,2) (5,4) (5,2) (4,2)

Question 57

What is the worst case scenario for quick sort?

Answer 57

The worst case for quicksort: The pivot is the smallest element, all the time.

Question 58

compare quicksort to mergesort

Answer 58

• Quicksort uses more comparisons with relatively fewer data movements than Mergesort.

Question 59

What is the average number of in version in an array of N distinct elements?

Answer 59

N(N-1)/4

Question 60

What conditions are needed to run a bucket sort?

Answer 60

the input must consist of only positive integers smaller than M, so we must know that all input is smaller than some number M.

Question 61

When does quicksort not perform as well as insertion sort?

Answer 61

when N ≤ 20.

Question 62

For what two functions does java uses mergesort currently?

Answer 62

Arrays.sort and collections.sort()

Question 63

What is the median-of-three algorithm?

Answer 63

• Int median3(array [] a, int left, int right)
  
  • Int center = (left+right)/2;
  • If(a[center] < a.left) swap;
  • If(a[right] < a[left]) swap;
  • If(a[right] < a[center]) swap;
  • Swap center and right-1;
  • Return right-1

Question 64

What is the full quicksort routine?

Answer 64

• Quicksort
  
  • Quicksort(array[] a, int left, int right)
    
    • If(left + cutoff <= right)
      
      • Int pivot = median3(a, left, right)
      • Int I = left, j = right -1;
      • For(; ; )
        
        • While(a[++i] < pivot){}
        • While (a[j–] > pivot){}
        • If(I < j) swap a[i] and a[j];
        • Else break
      • Swap a[i] and a[right-1]
      • Quicksort(a, left, i-1);
      • Quicksort(a, i+1, right);
    • Else do insertion sort

Question 65

Derive the worst case of Quicksort

Answer 65

Telescope the recurrence relation T(N-1) + cN to N^2

Question 66

What is comparison bases sorting?

Answer 66

the only operation allowed on the input data, besides assignments, is comparison.

Question 67

When should quicksort be used?

Answer 67

• Quicksort is a better option for generic sorting in C++ because java is pass by reference, however the copying of generic objects can become expensive in C++.

Question 68

Shellsort runtime is dependent on what?

Answer 68

the choice of increment sequence.

Question 69

The number of inversions is exactly what the number of what in insertion sort?

Answer 69

swaps

Question 70

What are the four steps to quickselect?

Answer 70

1. If |S| = 1, then k =1 and return the element in s as the answer. If a cutoff for small arrays is being used and |S| <= cutoff, then sort S using insertion sort and return the kth element.
2. Pick a pivot element in S.
3. Partition S into two other arrays just like quick sort.
4. If k <= |, then the kth smallest element must be in S1, so we return quickselect(k, S1). If k = 1+|S1| then the pivot is the kth smallest element and we can return it as the answer. Otherwise the kth element is in S2 and it is the k -|s1|-1 smallest element, so we return quickselect(k, k-|s1|-1).