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