Problem Solving related to Lecture 3.pptx

NSU

1. Problem Solving related to Lecture 3 CSE 225/Spring 2018/ AzK

2. Exercise: Write a client function that splits an unsorted list into two unsorted lists using the following specification. SplitLists ( UnsortedType list, ItemType item, UnsortedType & list1, UnsortedType & list 2) Function : Divides list into two lists according to the key of item. Preconditions : list has been initialized and is not empty. Postconditions : list1 contains all the items of list whose keys are less than or equal to item’s key; list2 contains all the items of list whose keys are greater than item’s key; list remains unchanged.

3. SplitLists Solution void SplitLists ( const UnsortedType & list , ItemType item , UnsortedType & list1 , UnsortedType & list2 ) { ItemType listItem ;   list1 .MakeEmpty(); list2 .MakeEmpty(); list .ResetList ();   while (! list .IsLastItem ()) { list .GetNextItem ( listItem ); if ( listItem > item ) list2 .InsertItem( listItem ); else list1 .InsertItem( listItem ); } } What is the time complexity using big-O?

4. Exercise: Write a client function that merges two unsorted lists into another unsorted list using the following specification. MergeL ists ( UnsortedType list1, UnsortedType list2, UnsortedType & list) Function : Merge list1 and list2 into another list . Preconditions : list1 and list2 have been initialized. Postconditions : list contains all the items of list1 and list2; list does not contain duplicates .

5. O(N 1 ) void MergeLists ( UnsortedType list1 , UnsortedType list2 , UnsortedType & list ){ ItemType item; bool found; list .MakeEmpty ();   list1 .ResetList(); while (! list1 .IsLastItem() && (! list .IsFull ())) { list1 .GetNextItem(item); list .InsertItem (item); } list2 .ResetList(); while (! list2 .IsLastItem() && (! list .IsFull ())) { list2 .GetNextItem(item); list .RetrieveItem (item, found); if (!found) list .InsertItem (item) } if ( list .IsFull () && (! list2 .IsLastItem())) cout << “Not enough space to merge the lists” << endl ; }