Skip to content

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

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]

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

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