Sorting

Question 1

An Ideal Sorting Algorithm

Answer 1

Stable: Equal keys aren’t reordered

Extra Space: Operates in place, requireing O(1) extra space

Worst Case Comparisons: O( n log n ) comparisons

Worst Case Moves: O( n ) moves

Adaptive: Speeds up to O( n ) when data is nearly sorted

** There is no algorithm that has all these properties

Question 2

Insertion Sort Characteristics

Answer 2

Stable: Yes

Best Case: O(n)*

Average Case: O(n²)

Worst Case: O(n²)

* Iif list is already sorted

Question 3

Insertion Sort Algorithm

Answer 3

insertionSort(data[], n) for i=1 to n-1 mov all elements data[j] greater than data[i] by one position; place data[i] in its proper position;

`
// C++ example
template< typename T >
void insertionSort(T data[], int n) 
{
    for (int i = 1,j; i < n; i++) 
    { 
        T intemToInsert = data[i];
        for (j = i; j > 0 && intemToInsert < data[j-1]; j--) 
            data[j] = data[j-1];
        data[j] = intemToInsert; 
    }
}
`

Question 4

Selection Sort Summary

Answer 4

Stable: No

Best Case: O(n²)

Average Case: O(n²)

Worst Case: O(n²)

Question 5

Selection Sort Algorithm

Answer 5

// n-2 explanation on description card selectionSort(data[], n) for i=0 *to* n-2 *select the smallest el among* data[i],...,data[n-1] ; *swap it with* data[i];

`// C++ example
template< typename T >
void selectionSort(T data[], int n) 
{
   for (int i = 0,j,least; i < n-1; i++) 
   { 
      for (j = i+1, least = i; j < n; j++)
          if (data[j] < data[least])
              least = j;
      swap(data[least],data[i]); 
   }
}`

Question 6

Bubble Sort Summary

Answer 6

Stable: Yes*

Best Case: O(n²)

Average Case: O(n²)

Worst Case: O(n²)

* Implentations vary, and may affect stability

Question 7

Bubble Sort Algorithm

Answer 7

bubbleSort(data[], n) for i=0 *to* n-2 for j = n-1 *down to* i+1 *swap elements in positions* j *and* j-1 *if they are out of order;*

// C++ example
template< typename T >
void bubbleSort(T data[], int n) 
{
   for (int i = 0; i < n-1; i++)
      for (int j = n-1; j > i; --j)
         if (data[j] < data[j-1]) 
            swap(data[j],data[j-1]);
}

Question 8

Bubble Sort’s comparison to Insertion and Selection

Answer 8

In the average case

Bubble Sort

• makes approximately twice as many comparisons as insertion sort
• the same number of moves as insertion sort
• as many comparisons as selection sort
• and n times more moves than selection sort

Question 9

_______ sort starts from the end of the array by finding the largest elements, wheras ________ sort starts from the beginning using the smallet elements.

Answer 9

Heap, Selection

Question 10

Heap Sort Algorithm

Answer 10

heapSort(data[],n) *transform* data *into a heap*; for i = *down to* 2 *swap the root with the element in position* i; *restore the heap property for the tree* data[0], . . . , data[i-1];

// C++ example
template< typename T >
void heapsort(T data[], int n) 
{
   for (int i = n/2 - 1; i >= 0; --i) // create a heap
      heapDown(data,i,n-1);
   for (int i = n-1; i >= 1; --i) 
   {
      swap(data[0],data[i]); // move the largest item to data[i]; 
      heapDown(data,0,i-1); // restore the heap property;
   } 
}

Question 11

Heap Sort Summary

Answer 11

Stable: No

Best Case: O( n log n)

Average Case: O( n log n )

Worst Case: O( n log n )

Question 12

Mergesort Summary

Answer 12

Stable: Yes*

Extra Space: O( n )

Best Case: O( n log n)

Average Case: O( n log n )

Worst Case: O( n log n )

* Implentations vary, and may affect stability

Question 13

Mersort Algorithm (dividing arrays)

Answer 13

mergeSort(data[], first, last) if first \< last mid = (first + last) / 2; mergeSort(data, first, mid); mergeSort(data, mid+1, last); merge(data, first, last);

Question 14

Mergesort Algorithm (merging two arrays)

Answer 14

merge(array1[], first, last) mid = (first + last) / 2; i1 = 0; i2 = first; i3 = mid + 1; while *both left and right subarrays of* array1 *contains elements* if array1[i2] \< array[i3] temp[i1++] = array1[i2++]; else temp[i1++] = array[i3++]; *load into* temp *the remaining elements of* array1; *load to* array1 *the content of* temp;

Question 15

Mergesort Algorithm Implementation

Answer 15

template < typename E, typename Comp >
void mergeSort(E A[], E temp[], int left, int right)
{
  if (left == right) return; // list of one element
  int mid = (left + right) / 2;
  mergeSort < E, Comp > (A, temp, left, mid);
  mergeSort < E, Comp > (A, temp, mid+1, right);
  for (int i=left; i <= right; i++) // copy subarray to temp
    temp[i] = A[i];
  // do the merge operation back to A
  int i1 = left; int i2 = mid + 1;
  for (int curr=left; curr <= right; curr++)
  {
    if (i1 == mid+1) // left sublist exhausted
      A[curr] = temp[i2++];
    else if (i2 > right) // right sublist exhausted
      A[curr] = temp[i1++];
    else if ( Comp::prior(temp[i1], temp[i2]) )
      A[curr] = temp[i1++];
    else A[curr] = temp[i2++];
  }
}

Question 16

Quicksort Summary

Answer 16

Stable: No*

Best Case: O( n log n)

Average Case: between best and worst

Worst Case: O( n² )

* Implentations vary, and may affect stability

Question 17

Quicksort Pivot Choices

Answer 17

• Middle value in (sub)array
• Median of first, middle, and last elements
• Median of values at 3 random indices

Question 18

Quicksort Implementation

Answer 18

template < class T >
void quickSort(T data[], int first, int last)
{

}

Question 19

It is inapproriate to use ________ for small arrays. For arrays with fewer than 30 items, ________ ______ is more efficient.

Answer 19

quicksort, insertion sort

Question 20

Sorting algorithms that rely on the comparison of items require at least ______ time – This is a lower bound

Answer 20

n log n

Question 21

Counting Sort Summary

Answer 21

Stable: Yes

Best Case: O( M* + n )

Average Case: O( M* + n )

Worst Case: O( M* + n )

* M is maximum data + 1

Question 22

Radix Sort Summary

Answer 22

Stable: Yes

Best Case: O( p(N + b) )

Average Case: O( p(N + b) )

Worst Case: O( p(N + b) )

* p is # of passes; b is # of “buckets”

Question 23

Shell Sort Summary

Answer 23

Stable: No

Best Case: O( n log n )*

Average Case: O( n^1.5 )

Worst Case: O( n² )

* if list is already sorted

Question 24

External Sorts Efficiency

Answer 24

Measured by the number of I/O transactions to/from disk or tape