##### Differences

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

 — cs-142:is-this-list-sorted [2015/05/14 17:44] (current)cs142ta created 2015/05/14 17:44 cs142ta created 2015/05/14 17:44 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== + + /* + 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; + } + 