Programming Assignment #1

This is an inital lab to familiarize you with the lab techniques to be used in this class AND to refresh your memory of C++ arrays, sorting, and Visual Studio.

1.1 Learning objectives

  • C++ Arrays
  • Implementing a sorting algorithm.
  • Using Visual Studio
  • Turning in Lab work

1.2 Task statement

The Pancake Sort is a sorting technique in which the only operation allowed to rearrange the elements is to reverse the front elements of the array. We call this the flip operation as it mimics the flipping of a stack of pancakes.

The aim of this exercise is to implement a simple version of the algorithm described below. Assuming that the array is A with n elements, the algorithm will take n-1 passes.

  1. For each pass i, where i is from 1 to n-1, search for the largest element in A[0] to A[n-i].
  2. If the largest element is already at the correct position of the array (i.e. A[n-i]), go to the next pass, otherwise continue to next step.
  3. If the largest element is at A[0], skip to step 5.
  4. Assuming the largest element is at A[max_index], flip (reverse) the first max_index+1 array elements A[0], A[1], ... A[max_index] by calling the flip(A,max_index) function.
  5. Flip the first n-i+1 elements by calling flip(A,n-i).
  6. Go to next pass.

You need to keep count on the number of times you flip the elements.

Below shows the 6 passes of this Pancake Sort algorithm on the 7-element array {5, 7, 3, 2, 10, 8, 6}. The total number of flips is 8.

pancake1.gif

pancake_sort2.gif

Write a program pancake_sort.c to implement this Pancake Sort algorithm on an integer array with at most 20 elements. The input of your program consists of the number of array elements followed by that number of array elements. The output of your program is the sorted array, and the number of flips performed.

You may assume that the array does not contain duplicate elements.

1.3 Sample runs

Sample runs using interactive input (user's input shown in blue; output shown in bold purple). Note that the first two lines (in green) below) are commands issued to compile and run your program in Visual Studio 2010.

Number of elements: 7
Enter array values: 5 7 3 2 10 8 6
 

Sample run #2:

Number of elements: 10
Enter array values: -14 39 7 13 52 -28 0 5 -2 10
 

1.4 Important notes

  • The skeleton program is provided here: pancake-sort.cpp.
  • You may assume that the array size is at most 20, and the array does not contain duplicate elements.
  • Note that there is NO trailing space at the end of each line of output.
  • Fully document you program with comments, include you name, the date, and the lab number and lab description.

1.5 Turning in your solution

  • Do 5 different runs, including a run with 1 element, and one with 20 elements.
  • Go to the Moodle site for this course, and turn in two files, one with a capture of the runs, the other with the solution for this problem.

1.6 Estimated development time

The time here is an estimate of how much time we expect you to spend on this exercise. If you need to spend way more time than this, it is an indication that some help might be needed.

  • Algorithm given: 0 minutes
  • Writing pseudo-code: 10 minutes
  • Translating pseudo-code into code: 20 minutes
  • Typing in the code: 20 minutes
  • Testing and debugging: 40 minutes
  • Total: 1 hour 30 minutes

-- JimSkon - 2011-02-04

*

Topic attachments
I Attachment Action Size Date Who Comment
Gifgif pancake1.gif manage 15.3 K 2011-02-04 - 14:57 JimSkon Pancake 1
Gifgif pancake_sort2.gif manage 13.2 K 2011-02-04 - 14:57 JimSkon Pancake 2
Topic revision: r2 - 2011-02-04 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback