Skip to content

[Oops.] Exercise 1.9(b) - Is there ever a sequence that pancake sort must needs n flips? #313

@skydiving94

Description

@skydiving94

Chapter number or note title: Chapter 1

Page number: 50

Error description:
Consider the following algorithm.

FlipSort(A[1..n]):
  for i <- n down to 2:
    k <- position of the largest misplaced pancake i
    if k < i:
      flip(A, k) to move the i-th pancake to the front.
      flip(A, i) to move the i-th pancake to the i-th position through flipping. 

For n = 1, there is no flip needed, i.e. flip needed is 0, because k = i = 1.
Am I missing anything that somehow a flip would be needed?

Or is the algorithm above not the ideal one for 1.9(a)?

Suggested fix (if any): [fix]

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions