CS23
1) If the array is smaller than 2 items then return 2) Choose a partition element, p 3) Split array into 2 partitions: p1 and p2 p1 contains elements < p p2 contains elements >= p (The array should be placed in the order p1 p p2) 4) Recursively sort p1 and p2
Counting the number of comparisons, Steps 1 and 2 are O(1). Step 3 is O( n). Step 4 is 2O( n/2). Solving the resulting recurrence relation:
yields a running time of O( n log n).
void bsort(int d[], inst n) { int counts[100]; int i; int j; int cur; // Empty all the buckets. for (i = 0; i < 100; ++i) counts[i] = 0; // "Place" each item from d in its appropriate bucket. for (i = 0; i < size; ++i) counts[d[i] - 1]++; // "Take" the items from the buckets, putting them back in d. for (cur = 0, i = 0; i < 100; ++i) for (j = 0; j < counts[i]; ++j) d[cur++] = i + 1; }
O( n).
Generally, you can't bound the range of the inputs. If you have m buckets, then bucket sort is O( m + n). If the range of the inputs is the full range of an int, you have over 4,000,000,000 buckets to examine. Personally, I'd pass on that proposition.
Clearly indicate which problem you are solving.
I suppose I have to solve both of them. Life just isn't fair.
()
, {}
, []
)
balanced. Assume that the stack class has been written for you.
The following are balanced: ()
, [()]{}
.
The following are unbalanced: ()}
, [{}
, ([)]
.
// Support function. Match c against top of stack. int match(Stack &S, int c) { char d; if (S.IsEmpty()) return 0; S.Top(d); S.Pop(); switch (c) { case ')': return d == '('; break; case '}': return d == '{'; break; case ']': return d == '['; break; // This should never happen. default: cout << "ARGHHH!\n"; exit(1); break; } // Not reached. } // The function that does the work. Assumes that f has already been // opened. int checkit(ifstream &f) { Stack S; char c; while (!f.eof()) { f.get(c); switch (c) { case '(': case '{': case '[': S.Push(c); break; case ')': case '}': case ']': if (!match(S, c)) return 0; break; default: break; } // Stack should be empty at this point. return S.IsEmpty(); }
// We have no need for data members in Stack; List provides everyting we // need. However, we don't want a Stack user accessing List methods, // so we inherit List privately. class Stack : private List { public: void Push(int val); void Pop(void); int Top(void); int IsEmpty(void); } void Stack::Push(int val) { Insert(1, val); } void Stack::Pop(void) { Delete(1); } int Stack::Top(void) { return Retrieve(1); } int Stack::IsEmpty(void) { return List::IsEmpty(); // Scope resolution necessary to prevent // infinite recursion. }