# Presentation: 662437

## C++ Plus Data Structures

**Nell Dale**
**Chapter 10**
**Sorting and Searching Algorithms**
***Slides by Sylvia Sorkin, Community College of Baltimore County - Essex Campus***

## Sorting means . . .

- The values stored in an array have keys of a type for which the relational operators are defined.   (We also assume unique keys.)
- Sorting rearranges the elements into either ascending or descending order within the array. (We’ll use ascending order.)

## Straight Selection Sort

**On each pass, finds the smallest of the unsorted elements, and swaps it into its correct place,**** ****thereby increasing the number of sorted elements by one.**

**Straight Selection Sort**

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**36**
**24**
**10**
**  ****6**
**12**

## Selection Sort: Pass One 

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**36**
**24**
**10**
**  ****6**
**12**

**U**
**N**
**S**
**O**
**R**
**T**
**E**
**D**

## Selection Sort: End Pass One 

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**  ****6**
**24**
**10**
** ****36**
**12**

**U**
**N**
**S**
**O**
**R**
**T**
**E**
**D**

## Selection Sort: Pass Two 

**Selection Sort: Pass Two **

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**  ****6**
**24**
**10**
** ****36**
**12**

**U**
**N**
**S**
**O**
**R**
**T**
**E**
**D**

## Selection Sort: End Pass Two 

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**  ****6**
**10**
**24**
**36**
**12**

**U**
**N**
**S**
**O**
**R**
**T**
**E**
**D**

## Selection Sort: Pass Three 

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**  ****6**
**10**
**24**
**36**
**12**

**U**
**N**
**S**
**O**
**R**
**T**
**E**
**D**

## Selection Sort: End Pass Three 

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**  ****6**
**10**
**12**
**36**
**24**

**S**
**O**
**R**
**T**
**E**
**D**

## Selection Sort: Pass Four 

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**  ****6**
**10**
**12**
**36**
**24**

**S**
**O**
**R**
**T**
**E**
**D**

## Selection Sort: End Pass Four

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**  ****6**
**10**
**12**
**24**
**36**

**S**
**O**
**R**
**T**
**E**
**D**

## Selection Sort: How many comparisons?

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**  ****6**
**10**
**12**
**24**
**36**

**4 compares for values[0]**
**3 compares for values[1]**
**2 compares for values[2]**
**1 compare for values[3]**
**=  4  +  3  +  2  +  1**

## For selection sort in general

**The number of comparisons when the array contains N elements is**
-   Sum = (N-1)  +   (N-2)  + .  .  .  +  2  +  1

## Notice that . . .

**Notice that . . .**

**    ****Sum =  (N-1)  +   (N-2)  +  .  .  .  +    2    +     1**
**+  Sum =      1    +       2    +  .  .  .  + (N-2) +  (N-1)**
**2* Sum =     N    +      N    +  . . .     +   N    +     N**
**2 * Sum = ****	****	****	****    N * (N-1)**
**     ****Sum =                         N * (N-1)**
**                                                ****2**

## For selection sort in general

**The number of comparisons when the array contains N elements is**
**  ****Sum = (N-1)  +   (N-2)  + .  .  .  +  2  +  1**
**  ****Sum = N * (N-1) /2 **
**  ****Sum = .5 N****2**** - .5 N**
**  ****Sum = O(N****2****)**

## 

template <class  ItemType >
int  MinIndex  ( ItemType  values [ ] ,   int  start ,  int end )	

//  Post: Function value = index of the smallest value in
//             values [start]  . . values [end].
{
	int  indexOfMin = start ;

	for  ( int  index = start + 1 ;  index <= end ; index++ )	

	       if  ( values [ index ] < values [ indexOfMin ] )

		      indexOfMin = index ;

	return   indexOfMin;

} 	

** **
**template <class  ItemType >**
**int  MinIndex  ( ItemType  values [ ] ,  **** ****int  start ,  int end )****	**
**	**
**//  Post: Function value = index of the smallest value in**
**//             values [start]  . . values [end].**
**{**
**	****int  indexOfMin = start ;**
**	****for  ( int  index = start + 1 ;  index <= end ; index++ )****	**
**	****       ****if  ( values [ index ] < values [ indexOfMin ] )**
**	****	****      ****indexOfMin = index ;**
**	****return   indexOfMin;**
**           **
**} *****	***

## 

template <class  ItemType >
void  SelectionSort  ( ItemType  values [ ] ,   int  numValues )	

//  Post: Sorts array values[0 . . numValues-1 ] into ascending 
//            order by key
{
	int  endIndex = numValues - 1 ;

	for  ( int  current = 0 ; current < endIndex ; current++ )	

	       Swap ( values [ current ] , 
                        values [ MinIndex ( values, current, endIndex ) ] ) ;

} 	

** **
**template <class  ItemType >**
**void  SelectionSort  ( ItemType  values [ ] ,  **** ****int  numValues )****	**
**	**
**//  Post: Sorts array values[0 . . numValues-1 ] into ascending **
**//            order by key**
**{**
**	****int  endIndex = numValues - 1 ;**
**	****for  ( int  current = 0 ; current < endIndex ; current++ )****	**
**	****       ****Swap ( values [ current ] , **
**                        ****values [ MinIndex ( values, current, endIndex ) ] ) ;**
**           **
**} *****	***

## Bubble Sort

**On each pass, this causes the smallest element to “bubble up” to its correct place in the array.**

**Bubble Sort**

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**36**
**24**
**10**
**  ****6**
**12**

## 

template <class  ItemType >
void BubbleUp  ( ItemType  values [ ] ,   int  start ,  int end )	

//  Post: Neighboring elements that were out of order have been
//            swapped between values [start] and  values [end],
//            beginning at values [end].
{

	for  ( int  index = end ;  index > start ; index-- )	

	       if  (values [ index ] < values [ index - 1 ] )

		      Swap ( values [ index ], values [ index - 1 ] ) ;

} 	

** **
**template <class  ItemType >**
**void BubbleUp  ( ItemType  values [ ] ,  **** ****int  start ,  int end )****	**
**	**
**//  Post: Neighboring elements that were out of order have been**
**//            swapped between values [start] and  values [end],**
**//            beginning at values [end].**
**{**
**	****for  ( int  index = end ;  index > start ; index-- )****	**
**	****       ****if  (values [ index ] < values [ index - 1 ] )**
**	****	****      ****Swap ( values [ index ], values [ index - 1 ] ) ;**
**           **
**} *****	***

## 

template <class  ItemType >
void  BubbleSort  ( ItemType  values [ ] ,   int  numValues )	

//  Post: Sorts array values[0 . . numValues-1 ] into ascending 
//            order by key
{
	int  current = 0  ;

	while  ( current < numValues - 1 )	

	       	BubbleUp ( values , current , numValues - 1 ) ;

		current++ ;

} 	

** **
**template <class  ItemType >**
**void  BubbleSort  ( ItemType  values [ ] ,  **** ****int  numValues )****	**
**	**
**//  Post: Sorts array values[0 . . numValues-1 ] into ascending **
**//            order by key**
**{**
**	****int  current = 0  ;**
**	****while  ( current < numValues - 1 )****	**
**	****       ****	****BubbleUp ( values , current , numValues - 1 ) ;**
**	****	****current++ ;**
**           **
**} *****	***

## Insertion Sort

**On each pass, this causes the number of already sorted elements to increase by one.**

**Insertion Sort**

**  **
**values****	**** [ 0 ]       **
**	**** ****[ 1 ]**
**	**** ****[ 2 ]**
** **
** **
**             ****[ 3 ]**
** ****	**** ****[ 4 ]**

**36**
**24**
**10**
**  ****6**
**12**

## Insertion Sort

**To insert 12, we need to make room for it by moving first 36 and then 24.**

**Insertion Sort**

**12**

**36**

## Insertion Sort

**Works like someone who “inserts” one more card at a time into a hand of cards that are already sorted.**** **
**To insert 12, we need to make room for it by moving first 36 and then 24.**

**Insertion Sort**

**36**

**12**

## Insertion Sort

**To insert 12, we need to make room for it by moving first 36 and then 24.**

**Insertion Sort**

**6**

**10**

**12**

## Insertion Sort

**To insert 12, we need to make room for it by moving first 36 and then 24.**

**Insertion Sort**

**6**

**10**

**12**

## template <class  ItemType >
void InsertItem  ( ItemType  values [ ] ,   int  start ,  int end )	

//  Post: Elements between values [start] and  values [end]
//            have been sorted into ascending order by key.
{
	bool  finished = false ;
	int     current  =  end ;
	bool  moreToSearch = ( current != start ) ;

	while  ( moreToSearch  &&  !finished )
	{	

	       if  (values [ current ] < values [ current - 1 ] )
	       {
		      Swap ( values [ current ], values [ current - 1 ] ) ;
		      current-- ;
		      moreToSearch = ( current != start );
		}
		else
		      finished = true ;
	}      
} 	

**template <class  ItemType >**
**void InsertItem  ( ItemType  values [ ] ,  **** ****int  start ,  int end )****	**
**	**
**//  Post: Elements between values [start] and  values [end]**
**//            have been sorted into ascending order by key.**
**{**
**	****bool  finished = false ;**
**	****int     current  =  end ;**
**	****bool  moreToSearch = ( current != start ) ;**
**	****while  ( moreToSearch  &&  !finished )**
**	****{****	**
**	****       ****if  (values [ current ] < values [ current - 1 ] )**
**	****       ****{**
**	****	****      ****Swap ( values [ current ], values [ current - 1 ] ) ;**
**	****	****      ****current-- ;**
**	****	****      ****moreToSearch = ( current != start );**
**	****	****}**
**	****	****else**
**	****	****      ****finished = true ;**
**	****}****      **
**} *****	***

## 

template <class  ItemType >
void  InsertionSort  ( ItemType  values [ ] ,   int  numValues )	

//  Post: Sorts array values[0 . . numValues-1 ] into ascending 
//            order by key
{
	for  ( int count = 0 ; count < numValues ; count++ )

	       	InsertItem ( values , 0 , count ) ;

} 

** **
**template <class  ItemType >**
**void  InsertionSort  ( ItemType  values [ ] ,  **** ****int  numValues )****	**
**	**
**//  Post: Sorts array values[0 . . numValues-1 ] into ascending **
**//            order by key**
**{**
**	****for  ( int count = 0 ; count < numValues ; count++ )**
**	****       ****	****InsertItem ( values , 0 , count ) ;**
**} **

## Sorting Algorithms and Average Case Number of Comparisons

**Simple Sorts**
**Straight Selection Sort**
**Bubble Sort**
**Insertion Sort**
**More Complex Sorts**
**Quick Sort**
**Merge Sort**
**Heap Sort**

**     ****O(N****2****)**
**  ****O(N*log N)**

## Recall that . . .

- A heap is a binary tree that satisfies these
-  special SHAPE and ORDER properties:
**Its shape must be a complete binary tree. **
**For each node in the heap, the value stored in that node is greater than or equal to the value in each of its children.**

** **

** ****60**

**40**

**30**

**12**

**   ****8**

**root**

**The largest element**** in a heap is always found in the root node**** **

**10**

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**70**
**60**
**12**
**40**
**30**
**  ****8**
**10**

**values**

** ****60**
**  ****1**

**40**
** **
** ****3 ****                **

**12**
**  ****2**

**   ****8**
**   ****5**

**  ****root**

**The heap can be stored ****in an array **

## Heap Sort Approach   

**First, make the unsorted array into a heap by satisfying the order property.  Then repeat the steps below until there are no more unsorted elements.**
**Take the root (maximum) element off the heap**** by swapping it into its correct place in the array at the end of the unsorted elements.**
**Reheap the remaining unsorted elements.**** (This puts the next-largest element into the root position).**

** **

**After creating the original heap **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**70**
**60**
**12**
**40**
**30**
**  ****8**
**10**

**values**

** ****60**
**  ****1**

**40**
** **
** ****3 ****                **

**12**
**  ****2**

**   ****8**
**   ****5**

**  ****root**

** **

**Swap root element into last place in unsorted array **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**70**
**60**
**12**
**40**
**30**
**  ****8**
**10**

**values**

** ****60**
**  ****1**

**40**
** **
** ****3 ****                **

**12**
**  ****2**

**   ****8**
**   ****5**

**  ****root**

** **

**After swapping root element ****into its place **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****60**
**  ****1**

**40**
** **
** ****3 ****                **

**12**
**  ****2**

**   ****8**
**   ****5**

**  ****root**

**70**
** ****6**

**10**
**60**
**12**
**40**
**30**
**  ****8**
**70**

**NO NEED TO CONSIDER AGAIN**

** **

**After reheaping remaining unsorted elements **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****40**
**  ****1**

**10**
** **
** ****3 ****                **

**12**
**  ****2**

**   ****8**
**   ****5**

**  ****root**

**70**
** ****6**

**60**
**40**
**12**
**10**
**30**
**  ****8**
**70**

** **

**Swap root element into last place in unsorted array**

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****40**
**  ****1**

**10**
** **
** ****3 ****                **

**12**
**  ****2**

**   ****8**
**   ****5**

**  ****root**

**70**
** ****6**

**60**
**40**
**12**
**10**
**30**
**  ****8**
**70**

** **

**After swapping root element ****into its place **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****40**
**  ****1**

**10**
** **
** ****3 ****                **

**12**
**  ****2**

**  ****root**

**70**
** ****6**

**  ****8**
**40**
**12**
**10**
**30**
**60**
**70**

**  ****60**
**   ****5**

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****30**
**  ****1**

**10**
** **
** ****3 ****                **

**12**
**  ****2**

**  ****root**

**70**
** ****6**

**40**
**30**
**12**
**10**
**  ****6**
**60**
**70**

**  ****60**
**   ****5**

**After reheaping remaining unsorted elements **

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****30**
**  ****1**

**10**
** **
** ****3 ****                **

**12**
**  ****2**

**  ****root**

**70**
** ****6**

**40**
**30**
**12**
**10**
**  ****6**
**60**
**70**

**  ****60**
**   ****5**

**Swap root element into last place in unsorted array**

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****30**
**  ****1**

**10**
** **
** ****3 ****                **

**12**
**  ****2**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**After swapping root element ****into its place **

**40**
** ****4**

**  ****6**
**30**
**12**
**10**
**40**
**60**
**70**

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****10**
**  ****1**

**  ****6**
** **
** ****3 ****                **

**12**
**  ****2**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**40**
** ****4**

**30**
**10**
**12**
**  ****6**
**40**
**60**
**70**

**After reheaping remaining unsorted elements **

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****10**
**  ****1**

**  ****6**
** **
** ****3 ****                **

**12**
**  ****2**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**40**
** ****4**

**30**
**10**
**12**
**  ****6**
**40**
**60**
**70**

**Swap root element into last place in unsorted array**

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****10**
**  ****1**

**12**
**  ****2**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**40**
** ****4**

**After swapping root element ****into its place **

**  ****6**
**10**
**12**
**30**
**40**
**60**
**70**

**30**
** **
** ****3 ****                **

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****10**
**  ****1**

**  ****6**
**  ****2**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**40**
** ****4**

**12**
**10**
**  ****6**
**30**
**40**
**60**
**70**

**30**
** **
** ****3 ****                **

**After reheaping remaining unsorted elements **

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****10**
**  ****1**

**  ****6**
**  ****2**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**40**
** ****4**

**12**
**10**
**  ****6**
**30**
**40**
**60**
**70**

**30**
** **
** ****3 ****                **

**Swap root element into last place in unsorted array**

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

** ****10**
**  ****1**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**40**
** ****4**

**30**
** **
** ****3 ****                **

**After swapping root element ****into its place **

**12**
**  ****2**

**  ****6**
**10**
**12**
**30**
**40**
**60**
**70**

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

**  ****6**
**  ****1**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**40**
** ****4**

**30**
** **
** ****3 ****                **

**12**
**  ****2**

**10**
**  ****6**
**12**
**30**
**40**
**60**
**70**

**After reheaping remaining unsorted elements **

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

**  ****6**
**  ****1**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**40**
** ****4**

**30**
** **
** ****3 ****                **

**12**
**  ****2**

**10**
**  ****6**
**12**
**30**
**40**
**60**
**70**

**Swap root element into last place in unsorted array**

** **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**[ 5 ]**
**[ 6 ]**

**values**

**  ****root**

**70**
** ****6**

**  ****60**
**   ****5**

**40**
** ****4**

**30**
** **
** ****3 ****                **

**12**
**  ****2**

**After swapping root element ****into its place **

**  ****6**
**10**
**12**
**30**
**40**
**60**
**70**

** ****10**
**  ****1**

**  ****6**
**  ****0**

**ALL ELEMENTS ARE SORTED**

** **

**Heap Sort: ****How many comparisons?**

**24**
** ****0**

** ****60**
**  ****1**

**30**
** **
** ****3 ****                **

**40**
** ****4**

**12**
**  ****2**

**   ****8**
**   ****5**

**  ****root**

**10**
** ****6**

**18**
** **
** ****9 ****                **

**In reheap down, an element**
**is compared with its 2 **
**children (and swapped **
**with the larger).  But **
**only one element at**
**each level makes**
**this comparison,**
**and a complete**
**binary tree with **
**N nodes has **
**only O(log****2****N)**
**levels.**

**70**
**10**

## Heap Sort of N elements: How many comparisons?

**(N/2) * O(log N) compares to create original heap**
**(N-1) * O(log N) compares for the sorting loop**
**=  O ( N * log N) compares total**

## Using quick sort algorithm

**                                       ****A . . Z**
**             ****A . . L                                           M . . Z**
**A . . F                 G . . L                 M . . R              S . . Z**
** **

## 
// Recursive quick sort algorithm

template <class  ItemType >
void  QuickSort  ( ItemType  values[ ] ,  int  first ,  int  last )	

//  Pre:   first <= last
//  Post: Sorts array values[ first .  . last ] into ascending order
{
	if  ( first < last ) 	                     //  general case

	{	int  splitPoint ;

		Split ( values, first, last, splitPoint ) ;		

		// values [ first ] . . values[splitPoint - 1 ] <= splitVal
		// values  [ splitPoint ] = splitVal
		// values [ splitPoint + 1 ] . . values[ last ] > splitVal

		QuickSort( values,  first,  splitPoint - 1 ) ;
		QuickSort( values,  splitPoint + 1,  last );
	}

} ;	

**// Recursive quick sort algorithm**
** **
**template <class  ItemType >**
**void  QuickSort  ( ItemType  values[ ] , **** ****int  first ,**** **** int  last )****	**
**	**
**//  Pre:   first <= last**
**//  Post: Sorts array values[ first .  . last ] into ascending order**
**{**
**	****if  ( first < last ) ****	****                     *****//  general case***
**	****{****	****int  splitPoint ;**
**	****	****Split ( values, first, last, splitPoint ) ;****	****	**
**	****	*****// values [ first ] . . values[splitPoint - 1 ] <= splitVal***
***	******	******// values  [ splitPoint ] = splitVal***
***	******	******// values [ splitPoint + 1 ] . . values[ last ] > splitVal***
**	****	****QuickSort( values,  first,  splitPoint - 1 ) ;**
**	****	****QuickSort( values,  splitPoint + 1,  last );**
**	****}**
**           **
**} ;*****	***

## Before call to function Split

**    ****values[first] ****	****	****	****	****	****                               [last]**

- 				**splitVal = 9**
**       ****GOAL:  place  splitVal in its proper position with **
**	****	****       ****all values less than or equal to splitVal on its left **
**	****	****       ****and all larger values on its right**
***     ******9       20         6        18       14       3       60      11  ***

## After call to function Split

**    ****values[first] ****	****	****	****	****	****                               [last]**

- 				**splitVal = 9**
**   ****smaller values****	****                        larger values**
**   ****in left part****	****	****	****           in right part**
*** ***
***     ******6        3         9        18       14       20       60      11  ***

**splitVal in correct position**

## Quick Sort of N elements: How many comparisons?

**N****	****  ****	****For first call, when each of N elements **
**	****	****is compared to the split value**
**2 * N/2 ****	****For the next pair of calls, when N/2 **
**	****	****elements in each “half” of the original**
**	****	****array are compared to their own split values.**
**4 * N/4****	****For the four calls when N/4 elements in each**
**	****	****“****quarter” of original array are compared to **
**	****	****their own split values.**
**	****.**
**	****.****	**** **
**	****.****	****	****HOW MANY SPLITS CAN OCCUR?****	**

## Quick Sort of N elements:How many splits can occur?

**It depends on the order of the original array elements!**
**If each split divides the subarray approximately in half, **
**there will be only log****2****N splits, and QuickSort is O(N*log****2****N).**
**But, if the original array was sorted to begin with, the **
**recursive calls will split up the array into parts of **
**unequal length, with one part empty, and the**
**other part containing all the rest of the array except for split value itself.  In this case, there can be as many as N-1 splits, and QuickSort is O(N****2****).**** **

## Before call to function Split

**    ****values[first] ****	****	****	****	****	****                               [last]**

- 				**splitVal = 9**
**       ****GOAL:  place  splitVal in its proper position with **
**	****	****       ****all values less than or equal to splitVal on its left **
**	****	****       ****and all larger values on its right**
***     ******9       20        26       18       14      53       60      11  ***

## After call to function Split

**    ****values[first] ****	****	****	****	****	****                               [last]**

**splitVal in correct position**

- 				**splitVal = 9**
**   ****no smaller values****	****            larger values**
***   *****empty left part****	****            in right part with N-1 elements**
***     ******9        20       26       18       14       53       60      11  ***

## Merge Sort Algorithm

**Cut the array in half.**
**Sort the left half.**
**Sort the right half.**
**Merge the two sorted halves into one sorted array. **

**              ****[first]                              [middle]   [middle + 1]**

**                                           ****[last]**

**   ****74    36     . . .        95**

**75      29      . . .       52**

**   ****36    74     . . .          95**

**29     52    . . .          75 **

## 
// Recursive merge sort algorithm

template <class  ItemType >
void  MergeSort  ( ItemType  values[ ] ,  int  first ,  int  last )	

//  Pre:   first <= last
//  Post: Array values[ first . . last ] sorted into ascending order.
{
	if  ( first < last ) 	                     //  general case

	{	int  middle = ( first  +  last ) / 2  ;

		MergeSort ( values, first, middle ) ;		

		MergeSort( values,  middle + 1, last ) ;

		// now  merge two subarrays
		// values  [ first . . . middle ] with 
		// values [ middle + 1,  . . . last ].

		Merge( values,  first, middle, middle + 1, last ) ;
	}           
} 	

**// Recursive merge sort algorithm**
** **
**template <class  ItemType >**
**void  MergeSort  ( ItemType  values[ ] , **** ****int  first ,**** **** int  last )****	**
**	**
**//  Pre:   first <= last**
**//  Post: Array values[ first . . last ] sorted into ascending order.**
**{**
**	****if  ( first < last ) ****	****                     *****//  general case***
**	****{****	****int  middle = ( first  +  last ) / 2  ;**
**	****	****MergeSort ( values, first, middle ) ;****	****	**
**	****	****MergeSort( values,  middle + 1, last ) ;**
**	****	*****// now  merge two subarrays***
***	******	******// values  [ first . . . middle ] with ***
***	******	******// values [ middle + 1,  . . . last ].***
**	****	****Merge( values,  first, middle, middle + 1, last ) ;**
**	****}****           **
**} *****	***

## Using Merge Sort Algorithm with N = 16

**Using Merge Sort Algorithm ****with N = 16**

**                                              ****16**
**                       ****8                                                 8**
**          ****4                        4                        4                        4**
**     ****2       2             2        2                2       2                2      2**
**  ****1   1    1   1      1   1    1    1        1    1    1    1        1   1   1    1**
** **

## Merge Sort of N elements: How many comparisons?

**The entire array can be subdivided into halves **
**only log****2****N times. **
**Each time it is subdivided, function Merge is called**
**to re-combine the halves. Function Merge uses a **
**temporary array to store the merged elements.  **
**Merging is O(N) because it compares each element **
**in the subarrays. **
**Copying elements back from the temporary array **
**to the values array is also O(N).**
**MERGE SORT IS O(N*log****2****N).**

## Function  BinarySearch( )      

**BinarySearch**** takes ****sorted**** array ****info****,**** and two subscripts, ****fromLoc**** and ****toLoc****, and ****item ****as arguments.  It returns false if ****item**** is not found in the elements ****info[fromLoc...toLoc]****.   Otherwise, it returns true. **
**BinarySearch**** is O(log****2****N). **

## found = BinarySearch(info, 25, 0, 14 );       

**found = BinarySearch(info, 25, 0, 14 );****       **

**	****	****	****	****           ****item     fromLoc     toLoc**
**indexes**
**            ****0     1     2     3     4     5      6      7      8      9     10    11    12    13    14  **
**info **
**            ****0     2     4     6     8    10    12    14    16    18    20    22    24    26    28**
**	****	****	****	****	**** **
**                                                                      ****16    18    20    22    24    26    28**
** **
**	****	****	****	****	****                                     ****24    26    28**
**	****	****	****	****	****	****                        ****24   **
**NOTE:           denotes element examined**

## 
template<class  ItemType>
bool  BinarySearch   (  ItemType  info[ ] ,  ItemType  item , 
                                       int   fromLoc ,    int  toLoc ) 	
	//    Pre:   info [ fromLoc . . toLoc ] sorted in ascending order 
	//    Post:   Function value =  ( item  in info [ fromLoc . . toLoc] ) 

{		int  mid ;
		if  ( fromLoc > toLoc ) 	                 //  base case -- not found
			return  false ;                              
		else  {
                      mid = ( fromLoc + toLoc ) / 2 ;

		         if ( info [ mid ] == item )      // base case-- found at mid

			   return  true  ;

		        else  if ( item < info [ mid ] )     	 //  search lower half 
                             return BinarySearch ( info, item, fromLoc, mid-1 ) ;
                     else 	                          	// search upper half
			   return  BinarySearch( info, item, mid + 1, toLoc ) ;
             }

} 

**template<class  ItemType>**
**bool  BinarySearch   (  ItemType  info[ ] ,  ItemType  item , **
**                                      **** ****int   fromLoc ,  **** **** int  toLoc )**** ****	**
***	******//    Pre:   info [ fromLoc . . toLoc ] sorted in ascending order****** ***
***	******//    Post:   Function value =  ( item  in info [ fromLoc . . toLoc] )***** **
**{****	****	****int  mid ;**
**	****	****if  ( fromLoc > toLoc ) ****	****                 *****//  base case -- not found***
**	****	****	****return  false ;                              **
**	****	****else  {**
**                      ****mid = ( fromLoc + toLoc ) / 2 ;**
** **
**	****	****         ****if ( info [ mid ] == item )      *****// base case-- found at mid***
**	****	****	****   ****return  true  ;**
**           **
**	****	****        ****else  if ( item < info [ mid ] )     *****	****** //  search lower half ***
**                             ****return BinarySearch ( info, item, fromLoc, mid-1 ) ;**
**                     ****else ****	****                          ****	*****// search upper half***
**	****	****	****   ****return  BinarySearch( info, item, mid + 1, toLoc ) ;**
**             ****}**
**           **
**} **

## Hashing

**is a means used to order and access elements in a list quickly -- the goal is O(1) time -- by using a function of the key value to identify its location in the list.**
**The function of the key value is called a hash function.**
- 					       **FOR EXAMPLE . . .**

** **

**Using a hash function  **

**HandyParts company **
**makes no more than 100 **
**different parts.  But the**
**parts all have four digit numbers.**
**This hash function can be used to**
**store and retrieve parts in an array.**
**Hash(key) = partNum % 100**

** **

**Placing elements in the array **

**Use the hash function**
**Hash(key) = partNum % 100**
**to place the element with **
**part number 5502 in the**
**array.**

** **

**Placing elements in the array **

**Next place part number**
**6702 in the array.**
**Hash(key) = partNum % 100**
**        ****6702 % 100 = 2 **
**But values[2] is already **
**occupied.   **
**    ****COLLISION OCCURS **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**  ****.**
**  ****.**
**  ****.**

**    ****values**

** **
** **
**[ 97]**
**[ 98]**
**[ 99]**

**7803**
**Empty**
**.**
**.**
**.**
**Empty**
** **
**2298**
**3699**

**Empty**
**4501**
**5502**

** **

**How to resolve the collision? **

**One way is by linear probing.**
**This uses the rehash function**
**    ****(HashValue + 1) % 100 **
**repeatedly until an empty location**
**is found for part number 6702. **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**  ****.**
**  ****.**
**  ****.**

**    ****values**

** **
** **
**[ 97]**
**[ 98]**
**[ 99]**

**7803**
**Empty**
**.**
**.**
**.**
**Empty**
**2298**
**3699**

**Empty**
**4501**
**5502**

** **

**Resolving the collision **

**Still looking for a place for 6702**
**using the function**
**    ****(HashValue + 1) % 100 **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**  ****.**
**  ****.**
**  ****.**

**    ****values**

** **
** **
**[ 97]**
**[ 98]**
**[ 99]**

**7803**
**Empty**
**.**
**.**
**.**
**Empty **
**2298**
**3699**

**Empty**
**4501**
**5502**

** **

**Collision resolved **

**Part 6702 can be placed at**
**the location with index 4. **

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**  ****.**
**  ****.**
**  ****.**

**    ****values**

** **
** **
**[ 97]**
**[ 98]**
**[ 99]**

**7803**
**Empty**
**.**
**.**
**.**
**Empty **
**2298**
**3699**

**Empty**
**4501**
**5502**

** **

**Collision resolved **

**Part 6702 is placed at**
**the location with index 4. **
**Where would the part with**
**number 4598 be placed using**
**linear probing?**

**[ 0 ]**
**[ 1 ]**
**[ 2 ]**
**[ 3 ]**
**[ 4 ]**
**  ****.**
**  ****.**
**  ****.**

**    ****values**

** **
** **
**[ 97]**
**[ 98]**
**[ 99]**

**7803**
**6702**
**.**
**.**
**.**
**Empty**
**2298**
**3699**

**Empty**
**4501**
**5502**