Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cs-142:is-this-list-sorted [2015/05/14 17:44] (current)
cs142ta created
Line 1: Line 1:
 += Is this list sorted? =
 +==Problem==
  
 +* Sorting is a common task that computers perform. ​
 +* Sorting can be computationally expensive.
 +* Determining if a list is already sorted is far less expensive and can save time.
 +
 +* Write a program to report if a list of user-input words is already sorted lexicographically.
 +* Use “STOP” as a sentinel value to end user input.
 +
 +* Follow the problem solving steps to design a solution
 +* How does your brain do it?
 +
 +==Solution==
 +<code cpp>
 +/*
 +Test case 1:
 +Input: a,b,c (sorted list)
 +Expected Output: sorted
 +Actual:
 +
 +Test case 2:
 +Input: a,c,b (unsorted list)
 +Expected Output: unsorted
 +Actual:
 +
 +Test case 3:
 +Input: a (list with one item)
 +Expected Output: sorted
 +Actual:
 +
 +*/
 +
 +#include <​iostream>​
 +#include <​string>​
 +
 +using namespace std;
 +
 +const string SENTINEL = "​STOP";​
 +
 +int main()
 +{
 + cout << "Gimme your list and I'll tell you if it's sorted (a-z): " << endl;
 +
 + // Look at the first word, remember it
 + string first_word;
 + cin >> first_word;
 +
 + string prev_word = first_word;
 + string curr_word;
 +
 + bool is_sorted = true;
 + while (curr_word != SENTINEL)
 + {
 + // Look at the next word
 + cin >> curr_word;
 +
 + // If the next word is not STOP and is "​smaller"​ (i.e., comes before lexicographically) than the prev word
 + if (curr_word < prev_word && curr_word != SENTINEL)
 + {
 + // MAYDAY! Avast, list is not sorted!
 + is_sorted = false;
 +
 + }
 +
 + // we need to remember the current word when looking at the next word
 + prev_word = curr_word;
 +
 + // Repeat until we see STOP
 + }
 +
 + // Tell if it's sorted
 + if (is_sorted)
 + {
 + cout << "​It'​s sorted!"​ << endl;
 + }
 + else
 + {
 + cout << "Not sorted!"​ << endl;
 + }
 +
 + system("​pause"​);​
 + return 0;
 +}
 +</​code>​
cs-142/is-this-list-sorted.txt · Last modified: 2015/05/14 17:44 by cs142ta
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0