Is this list sorted?

• 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?

/*
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;
}