cs126 sorting

Describe the steps of an insertion sort.

1. Starting with element e at index i

2. Compare it to the element d at index i–1

3. If e < f:

   • Swap the elements and repeat from (2) with i - 2

4. If e ≥ f or index = 0:

   • Repeat from (1) with i + 1

5. The list is sorted when a full pass is completed with no swaps

What is the best-case cost of an insertion sort of n elements?

ϴ(n)

What is the worst-case cost of an insertion sort of n elements?

ϴ(n²)

Describe the steps of a selection sort.

• Find the smallest element and swap it with the first element of the array.

• Repeat this with the subarray formed by taking the tail of the array.

What is the worst-case cost of a selection sort of n elements?

O(n²)

What is the theorem about sorting algorithms that exchanges adjacent elements?

Any sorting algorithm that exchanges adjacent elements requires Ω(n²) average time.

What is the theorem about sorting algorithms based on key comparisons?

No sorting algorithm based on key comparisons can possibly be faster than Ω(nlogn).

What is the divide and conquer strategy?

• Divide: 

  • Divide the input data S into two independent subproblems S₁ and S₂

• Recursive: 

  • Solve the subproblems S₁ and S₂

• Conquer: 

  • Combine the solutions for S₁ and S₂ into a solution for S

• The base case for the recursion are subproblems of size 0 or 1

Describe the steps of a merge sort.

• Divide: 

  • Partition S into two sequences S₁ and S₂ of about n/2 elements each 

• Recursive: 

  • Recursively sort S₁ and S₂

• Conquer: 

  • Merge S₁ and S₂ into a sorted sequence

What is the cost of merging two sorted sequences, each with n/2 elements.

O(n)

What is the height h of a merge sort tree?

O(logn)

What is the worst-case time cost of a merge sort?

O(nlogn)

Describe the steps of a quick sort.

1. Divide the array into two subarrays L and R around a pivot q, where each  element in L is less than or equal to q, and each element in R is greater than q

2. Repeat (1) with the L and R subarrays

Name the (3) strategies for selecting a pivot in a quick sort.

1. Pick the first element in the array (may lead to a worst-case scenario)

2. Randomly select the pivot (generating random number is a costly operation)

3. Median-of-three strategy: median of the first, last and middle value of the array

What is the best-case cost of a quick sort of n elements, and how is this result found?

• partition() divides each array into two subarrays of equal size

• So the best case time is ϴ(nlogn)

What is the worst-case cost of a quick sort of n elements, and how is this result found?

• partition() divides each array into a subarray of size n-1 and a subarray of size 0 

• So the worst case time is ϴ(n²)

Describe the features of a selection sort.

• Slow

• In-place

• For small data sets (<1K)

Describe the features of an insertion sort.

• Slow

• In-place

• For small data sets (<1K)

Describe the features of a quick sort.

• Fast (average-case)

• In-place

• For large data sets (>1M)

Describe the features of a merge sort.

• Fast

• Sequential data access

• For huge data sets (>1M)

Describe the steps of a bucket sort.

• Assume we have

  • A set S of n entries according to their keys k

  • An array B of size m

• For each entry in S

  • Remove it and insert it at the end of bucket B[k]

• For i in range 0 to m - 1

  • For each entry in B[i]

    • Remove it and insert it at the end of S

What is the worst-time cost of a bucket sort?

O(n+m)

• n is the number of entries in the set

• m is the size of the array B

What is stable sorting?

• Sorting that preserves the order of key-value pairs

• So if two entries have the same key, they will be ordered in the sorted list in the same order they were originally in.

What is a radix sort?

• Sorts a sequence of key-value pairs by applying a stable bucket-sort approach.

• Least Significant Digit (LSD) radix sort processes the integer representations starting from the LSD and moving towards the MSD.

What is the worst-time cost of a radix sort?

• Its dependant on the number of digits of the keys d

• O(d x n)