C++ programming.

Question

Algorithms -devising an efficient algorithm

Write a function that is given an array of names and that removes duplicate names and keeps the remaining names in the order in which they first appeared. (These are customers in the order in which they ordered products from us, and we want a list of them in order of seniority. If Hal Bob Hal Al Al Al were the names, then the array should be changed to Hal Bob Al since those are the 3 different customers, and Hal ordered earlier than Bob ever ordered etc.)

Your function must be infinitely better than O(n’) Suggestions: ideas that might be useful -binary search, mergesort, structured data, sort,

I'll be glad to discuss your algorithm ideas during lab.

// orders[0..n-l] contains the names on orders arranged as they occurred

// post: orders[0..k-1] contains each name once, in the order of first appearance, where k is the return

//requircmcnt -better asymptotic performance than O(n*n) int cleanCustomerList( string ordersl], int n )

Don't use any library functions (other than rand which was shown in the tutorial).

Make a main program in a separate file to test a small case. I will test your function with a big case (more than 1 million ). Don't put your main program into the dropbox -just the file with your function.

Answer 1

Your instructor says not to use any other functions, but did say you can use data structures. The question to ask is if you can use the STL? The STL or Standard Template Library is a collection of containers and functions that standardized common operations, such as searches sorting and more.

There is a specific data structure that is ideal for this assignment - it's called a set. Sets are containers that store unique elements, the key word here being unique. Items can be inserted into the set and duplicates just get inserted into the same location. set has operators to check for duplicates, but in this case you don't care. The STL is also highly optimized, so working through the instructors list of 1 million names should still be close to O(n).