# 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;
}