Chapter 8 SORTING
1,Introduction and Notation
2,Insertion Sort
3,Selection Sort
4,Shell Sort
5,Lower Bounds
6,Divide-and-Conquer Sorting
Chapter 8 SORTING (continue)
8,Quicksort for Contiguous
Lists9,Heaps and Heapsort
10,Comparison of Methods
11,Pointers and Pitfalls
7,Mergesort for Linked Lists
8.1 Introduction and notation
◆ In an external sort,there are so many records
to be sorted that they must be kept in external
les on disks,tapes,or the like,In an internal sort
the records can all be kept internally in high-
speed memory,We consider only internal sorting.
◆ We use the notation and classes set up in
Chapters 6 and 7,Thus we shall sort lists of
records into the order determined by keys
associated with the records,The declarations for
a list and the names assigned to various types
and operations will be the same as in previous
chapters.
◆ To analyze sorting algorithms,we consider
both the number of comparisons of keys and
the number of times entries must be moved
inside a list,particularly in a contiguous list.
◆ Both the worst-case and the average
performance of a sorting algorithm are of
interest,To find the average,we shall consider
what would happen if the algorithm were run on
all possible orderings of the list (with n entries,
there are n! such orderings altogether) and take
the average of the results.
Sortable Lists
◆ To write efficient sorting programs,we must
access the private data members of the lists
being sorted,Therefore,we shall add sorting
functions as methods of our basic List data
structures,The augmented list structure forms
a new ADT that we shall call a Sortable_List,
with the following form.template <class Record> class Sortable_list:public
List<Record>
{ public,// Add prototypes for sorting methods here.
private,// Add prototypes for auxiliary functions here.
};
◆ Hence a Sortable_list is a List with extra
sorting methods.
◆ The base list class can be any of the List
implementations of Chapter 6.
◆ We use a template parameter class called
Record to stand for entries of the Sortable_list.
◆ Record objects can be compared to each
other or to a Key by first converting the
Record objects to their
◆ Any of the Record implementations
discussed in Chapter 7 can be supplied,by a
client,as the template parameter of a
Sortable_list.
◆ An ordered list is an abstract data type,
defined as a list in which each entry has a key,
and such that the keys are in order; that is,if
entry i comes before entry j in the list,then the
key of entry i is less than or equal to the key of
Every Record has an associated key of type Key,A
Record can be implicitly converted to the
corresponding Key,The keys (hence also the records)
can be compared under the operations ' <,' ' >,' ' >=,' '
<=,' ' ==,' and ' !=,'
?One operation retrieves an entry with a
specified key from the ordered list,Retrieval by
key from an ordered list is exactly the same as
searching.
?The second operation,ordered insertion,
inserts a new entry into an ordered list by using
the key in the new entry to determine where in
the list to insert it.
◆ For ordered lists,we shall often use two new
operations that have no counterparts for other
lists,since they use keys rather than positions
to locate the entry,
◆ Note that ordered insertion is not uniquely
specified if the list already contains an entry
with the same key as the new entry,since the
new entry could go into more than one
position.
8.2 Insertion Sort
Contiguous Insertion Sort
template <class Record>
void Sortable_list<Record>::insertion_sort( )
{ int first_unsorted,position;
Record current;
for(first_unsorted = 1; first_unsorted < count;
first_unsorted++)
if(entry[first_unsorted] < entry[first_unsorted-1])
{ position = first_unsorted;
current = entry[first_unsorted];
do{ entry[position] = entry[position-1];
position--;
} while(position>0 && entry[position-1]>current);
entry[position] = current;
}
}
position of
first unsorted entry
searches sorted
part of list
Pull unsorted entry
out of the list.
Shift all entries
until the proper position
is found
position is not em tycurrent entry
store
proper position
Find’t current entries
proper position
Linked Insertion Sort
◆ With no movement of data,there is no need to
search from the end of the sorted sublist,as for the
contiguous case.
◆ Traverse the original list,taking one entry at a time
and inserting it in the proper position in the sorted
list.
◆ Pointer last sorted references the end of the sorted
part of the list.
◆ Pointer first_unsorted==last_sorted->next
references the first entry that has not yet been
inserted into the sorted sublist.
◆ Pointer current searches the sorted part of the list
to find where to insert *first_unsorted.
◆ If * first_unsorted belongs before the head of the
◆ Otherwise,move current down the list until
first_unsorted->entry <= current->entry
and then insert * first_unsorted before *current,
To enable insertion before *current,keep a second
pointer trailing in lock step one position closer to
the head than current.
◆ A sentinel is an extra entry added to one end of a
list to
ensure that a loop will terminate without having to
include a separate check,Since last_sorted->next
== first_unsorted,the node * first_unsorted is
already in position to serve as a sentinel for the
search,and the loop moving current is simplified.
◆ A list with 0 or 1 entry is already sorted,so by
checking these cases separately we avoid
template <class Record>
void Sortable_list<Record>::insertion_sort( )
{ Node<Record> *first_unsorted,*last_sorted,*current,
*trailing;
if(head == NULL) return;
last_sorted = head;
while(last_sorted->next != NULL)
{ first_unsorted = last_sorted->next;
if(first_unsorted->entry < head->entry)
{ last_sorted->next = first_unsorted->next;
first_unsorted->next = head; head = first_unsorted;
}
else
{ trailing = head; current = trailing->next;
while(first_unsorted->entry > current->entry)
{ trailing = current; current = trailing->next; }
the first unsorted node
to be inserted
tail of the
sorted sublist
used to traverse
the sorted sublistone position
behind current
the empty list
is already sortedThe first node alone makes a sorted sublist
Insert *first_unsorted
at the head of
the sorted list
Search the sorted
sublist to
insert*first_unsorted
*first_unsorted
now belongs between
*trailing and *current
if(first_unsorted == current)
last_sorted = first_unsorted;
else
{ last_sorted->next = first_unsorted->next;
first_unsorted->next = current;
trailing->next = first_unsorted;
}
} // end_above else( if-else block)
} // end_while
} // end_function
Analysis of Insertion Sort
◆ The average number of comparisons for
insertion sort applied to a list of n items in random
order is
◆ The average number of assignments of items
for insertion sort applied to a list of n items in
random order is also
◆ The best case for contiguous insertion sort
occurs when the list is already in order,when
insertion sort does nothing except n - 1
comparisons of keys.
◆ The worst case for contiguous insertion sort
occurs when the list is in reverse order.
THEOREM 8.1 Verifying that a list of n entries is in
the correct order requires at least n-1 comparisons
of keys.
◆ Insertion sort verifies that a list is correctly
sorted as quickly as any method can.
8.3 Selection Sort
Contiguous Selection Sort
template <class Record>
void Sortable_list<Record>::selection_sort( )
{ for(int position=count-1; position>0; position--)
{ int max=max_key(0,position);
swap(max,position);
}
}
template <class Record> int Sortable_list<Record>::
max_key(int low,int high)
{ int largest=low,current;
for(current=low-1; current<=high; current--)
if (entry[largest]<entry[current])largest=current;
return largest;
}
Auxiliary
member functions
template <class Record>
void Sortable_list<Record>:,swap(int low,int high)
{ Record temp=entry[low];
entry[low]=entry[high];
entry[high]=temp;
}
Analysis and comparison:
Selection Insertion
(average)Assignments of
entriesComparisons of
keys
8.4 Shell Sort
Shell Sort main function
template <class Record> void Sortable_list<Record>::
shell_sort( )
{ int increment=count,start;
do { increment = increment/3+1;
for(start = 0; start < increment; start++)
sort_interval(start,increment);
} while (increment > 1);
}
spacing of entries
in subliststarting point of sublistmodified insertion sort
Contiguous Shell Sort
Complement
template <class Record>
void Sortable_list<Record>::shell_sort( )
{ int hold; Record curr;
for(int inc=count/3; inc>0; inc/=2)
for(int start=inc; start<count; start++)
{ hold=entry[start]; curr=start-inc;
while(curr>=0 && hold<entry[curr])
{ entry[curr+inc]=entry[curr]; curr-=inc; }
entry[curr+inc]=hold;
}
}
初始增量为 count/3
将 Sortable_list
分为 3组
当增量为 1时
做最后一次
插入操作
修改增量为 inc/2
可以确保 增量
改变成 1
insertion sort
(interval = inc)
8.5 Lower Bounds for
SortingHow fast is it possible to
sort?
THEOREM 8.2 Any algorithm that sorts a list of n
entries by use of key comparisons must,in its
worst case,perform at least ?lg n! ? comparisons
of keys,and,in the average case,it must perform
at least lg n! comparisons of keys.
Outline:
8.6 Divide-and-Conquer Sorting
void Sortable_list::sort( )
{ if the list has length greater than 1
{ partition the list into lowlist,highlist;
lowlist.sort( );
highlist.sort( );
combine(lowlist,highlist);
}
}
Mergesort:
We chop the list into two sublists of sizes as
nearly equal as possible and then sort them
separately,Afterward,we carefully merge the two
sorted sublists into a single sorted list.
Quicksort:
We first choose some key from the list for which,
we hope,about half the keys will come before and
half after,Call this key the pivot,Then we partition
the items so that all those with keys less than the
pivot come in one sublist,and all those with
greater keys come in another,Then we sort the
two reduced lists separately,put the sublists
together,and the whole list will be in order.
枢轴,支点
Mergesort Example:
Quicksort of 7 Numbers Example:
Sort (26,33,35,29,12,22)
8.7 Mergesort for Linked Lists
template <class Record>
void Sortable_list<Record>::merge_sort( )
{ recursive_merge_sort(head); }
Interface method
template <class Record> void Sortable_list<Record>::
recursive_merge_sort(Node<Record> * &sub_list)
{ if(sub_list != NULL && sub_list->next != NULL)
{ Node<Record> *second_half = divide_from(sub_list);
recursive_merge_sort(sub_list);
recursive_merge_sort(second_half);
sub_list = merge(sub_list,second_half);
}
}
recursive functionCall function
partition the list
into sub-lists
and second_half
Call function
combine the two sublists
template <class Record>
Node<Record>
*Sortable_list<Record>::divide_from(Node<Record>
*sub_list)
{ Node<Record> *position,*midpoint,*second_half;
if((midpoint=sub_list) == NULL) return NULL;
position=midpoint->next;
while(position != NULL)
{ position = position->next;
if(position != NULL)
{ midpoint=midpoint->next; position = position-
>next; }
}
second_half = midpoint->next;
midpoint->next = NULL;
return second_half;
}
traverses the entire listmoves at half speed
of position to midpointList is empty
Move position twice
for midpoint's
one move
second_half point to
the last halfFirst half rear nodenext set NULL
template <class Record> Node<Record>
Sortable_list<Record>::
merge(Node<Record> *first,Node<Record> *second)
{ Node<Record> combined;
Node<Record> * last_sorted = &combined;
while(first != NULL && second != NULL)
if(first->entry <= second->entry)
{ last_sorted->next=first; last_sorted=first;
first=first->next; }
else { last_sorted->next = second;
last_sorted = second; second = second->next;
}
if (first==NULL) last_sorted->next = second;
else last_sorted->next=first;
return combined.next;
}
dummy first node,
points to merged
list dummy
points to the last node
of sorted listAttach node with smaller key
Advance to the next
unmerged node
After one list ends,
attach the remainder
of the other
Analysis of Mergesort Sublist length
Lower bound:
Mergesort:
Insertion sort:
8.8 Quicksort for Contiguous Lists
template <class Record>
void Sortable_list<Record>::quick_sort( )
{ recursive_quick_sort(0,count-1); }
Interface method
template <class Record> void Sortable_list<Record>::
recursive_quick_sort(int low,int high)
{ int pivot_position;
if (low<high)
{ pivot_position=partition(low,high);
recursive_quick_sort(low,pivot_position-1);
recursive_quick_sort(pivot_position+1,high);
}
}
Otherwise,n
sorting is needed
Call function
partition the list
into low and high
two parts
template <class Record>
int Sortable_list<Record>::partition(int low,int high)
{ Record pivot;
int i,last_small = low;
swap(low,(low +high)/2);
pivot=entry[low];
for(i=low+1; i<=high; i++)
if(entry[i]<pivot)
{ last_small=last_small +1; swap(last_small,i); }
swap(low,last_small);
return last_small;
}
used to scan
through the listposition of the last key less than pivotPut pivot into
its proper position
Analysis of Quicksort
Worst-case analysis:
If the pivot is chosen poorly,one of the partitioned
sublists may be empty and the other reduced by
only one entry,In this case,quicksort is slower
than either insertion sort or selection sort.
Choice of pivot:
◆ First or last entry,Worst case appears for a list
already
sorted or in reverse order.
◆ Central entry,Poor cases appear only for
unusual orders.
◆ Random entry,Poor cases are very unlikely to
occur.
Average-case
analysis:
In its average case,quicksort performs
comparisons of keys in sorting a list of n entries
in random order.
See Pg.356-359
8.9 Heaps and Heapsort
Trees,Lists,and Heaps
If the root of the tree is in position 0 of the list,
then the left and right children of the node in
position k are in positions 2k+1 and 2k+2 of the
list,respectively,If these positions are beyond
the end of the list,then these children do not
exist.
DEFINITION A heap is a list in which each entry
contains a key,and,for all positions k in the list,
the key at position k is at least as large as the
keys in positions 2k +1 and 2k+2,provided these
positions exist in the list.
REMARK Many C++ manuals and textbooks
refer to the area used for dynamic memory as
the ìheap?; this use of the word ìheap? has
nothing to do with the present definition.
Heapsort is suitable only for contiguous lists.
Example,MaxHeapMinHeapThe not is Heap
See Pg.364 - 367 Fig.8.16 - Fig.8.18
template <class Record>void
Sortable_list<Record>::heap_sort( )
{ Record current;
int last_unsorted;
build_heap( );
for(last_unsorted=count-1; last_unsorted >
0;last_unsorted--)
{ current=entry[last_unsorted];
entry[last_unsorted]=entry[0];
inser_heap(current,0,last_unsorted-1);
}
}
temporary storage
for moving entries
Entries beyond
last_unsorted
have been sorted
Return the list
into a heap
(Auxiliary functions)
Extract last_entry
from list
Move top of
heap to the endRestore the heap
template <class Record>void
Sortable_list<Record>::build_heap( )
{ int low;
for(low=count/2-1; low>=0; low--)
{ Record current=entry[low];
inser_heap(current,low,count-1);
}
}
All entries beyond
the positionlow
form a heapAuxiliary functions
template <class Record> void Sortable_list<Record>::
inser_heap(const Record ¤t,int low,int high)
{ int large=2*low+1;
while(large<=high)
{ if(large<high && entry[large]<entry[large+1])large++;
if(current>=entry[large]) break;
else { entry[low]=entry[large]; low = large;
large=2*low+1; }
}
entry[low]=current;
}
position of child of
entry[low] with
the larger key
large is now
the left child of low
large is now the child
of low with the largest key
current belongs
in position low
Promote entry[large]
and move d wn the tree
Analysis of Heapsort
In its worst case for sorting a list of length n,
heapsort performs
comparisons of keys,and it performs
assignments of entries.
Priority Queues See Pg,369
DEFINITION A priority queue consists of entries,
such that each entry contains a key called the
priority of the entry,A priority queue has only two
operations other than the usual creation,clearing,
size,full,and empty operations:
?Insert an entry.
?Remove the entry having the largest (or smallest)
key.
If entries have equal keys,then any entry with the
largest key may be removed first.
Summary and Review
Comparison of Sorting Methods
template <class Record>
class Sortable_list, public List<Record>
{ public,
Inherit List
(Contiguous or
Linked)
Interface method
void insertion_sort( ); //pg.322 pg.324
void selection_sort( ); //pg.330
void shell_sort( ); // pg.335
void merge_sort( ); //pg.345
void quick_sort( ); //pg.353
void heap_sort( ); //pg.365
private,
int max_key(int low,int high); //pg.331
void swap(int low,int high); //pg.331
void sort_interval(int start,int increment);
void recursive_merge_sort(Node<Record>*&sub_list);
//pg.345
Node<Record> *divide_from(Node<Record>*sub_list);
//pg.346
Node<Record> *merge(Node<Record> *first,
Node<Record> *second); //pg.347
using
Contiguous List
using
Linked List
Auxiliary functions
int partition(int low,int high); //pg.355
void recursive_quick_sort(int low,int high); //pg.353
void insert_heap(const Record ¤t,int low,int
high);
//pg.366
void build_heap(); //pg.368
};Comparison of Sorting Methods
◆ Use of space
◆ Use of computer time
◆ Programming effort
◆ Statistical analysis
◆ Empirical testing
Pointers and Pitfalls
◆ Many computer systems have a general-purpose
sorting utility,If you can access this utility and it
proves adequate for your application,then use it
rather than writing a sorting program from scratch.
◆ In choosing a sorting method,take into account
the ways in which the keys will usually be arranged
before sorting,the size of the application,the
amount of time available for programming,the
need to save computer time and space,the way in
which the data structures are implemented,the
cost of moving data,and the cost of comparing
keys.
◆ Divide-and-conquer is one of the most widely
applicable and most powerful methods for
designing algorithms,When faced with a
programming problem,see if its solution can be
obtained by first solving the problem for two (or
more) problems of the same general form but of a
smaller size,If so,you may
be able to formulate an algorithm that uses the
divide-and-conquer method and program it using
recursion.
◆ Mergesort,quicksort,and heapsort are
powerful sorting methods,more difcult to
program than the simpler methods,but much
more efcient when applied to large lists,Consider
the application carefully to determine whether the
extra effort needed to implement one of these
◆ Priority queues are important for many
applications,Heaps provide an excellent
implementation of priority queues.
◆ Heapsort is like an insurance policy,It is
usually slower than quicksort,but it guarantees
that sorting will be completed in O(n log n)
comparisons of keys,as quicksort cannot always
do.
1,Introduction and Notation
2,Insertion Sort
3,Selection Sort
4,Shell Sort
5,Lower Bounds
6,Divide-and-Conquer Sorting
Chapter 8 SORTING (continue)
8,Quicksort for Contiguous
Lists9,Heaps and Heapsort
10,Comparison of Methods
11,Pointers and Pitfalls
7,Mergesort for Linked Lists
8.1 Introduction and notation
◆ In an external sort,there are so many records
to be sorted that they must be kept in external
les on disks,tapes,or the like,In an internal sort
the records can all be kept internally in high-
speed memory,We consider only internal sorting.
◆ We use the notation and classes set up in
Chapters 6 and 7,Thus we shall sort lists of
records into the order determined by keys
associated with the records,The declarations for
a list and the names assigned to various types
and operations will be the same as in previous
chapters.
◆ To analyze sorting algorithms,we consider
both the number of comparisons of keys and
the number of times entries must be moved
inside a list,particularly in a contiguous list.
◆ Both the worst-case and the average
performance of a sorting algorithm are of
interest,To find the average,we shall consider
what would happen if the algorithm were run on
all possible orderings of the list (with n entries,
there are n! such orderings altogether) and take
the average of the results.
Sortable Lists
◆ To write efficient sorting programs,we must
access the private data members of the lists
being sorted,Therefore,we shall add sorting
functions as methods of our basic List data
structures,The augmented list structure forms
a new ADT that we shall call a Sortable_List,
with the following form.template <class Record> class Sortable_list:public
List<Record>
{ public,// Add prototypes for sorting methods here.
private,// Add prototypes for auxiliary functions here.
};
◆ Hence a Sortable_list is a List with extra
sorting methods.
◆ The base list class can be any of the List
implementations of Chapter 6.
◆ We use a template parameter class called
Record to stand for entries of the Sortable_list.
◆ Record objects can be compared to each
other or to a Key by first converting the
Record objects to their
◆ Any of the Record implementations
discussed in Chapter 7 can be supplied,by a
client,as the template parameter of a
Sortable_list.
◆ An ordered list is an abstract data type,
defined as a list in which each entry has a key,
and such that the keys are in order; that is,if
entry i comes before entry j in the list,then the
key of entry i is less than or equal to the key of
Every Record has an associated key of type Key,A
Record can be implicitly converted to the
corresponding Key,The keys (hence also the records)
can be compared under the operations ' <,' ' >,' ' >=,' '
<=,' ' ==,' and ' !=,'
?One operation retrieves an entry with a
specified key from the ordered list,Retrieval by
key from an ordered list is exactly the same as
searching.
?The second operation,ordered insertion,
inserts a new entry into an ordered list by using
the key in the new entry to determine where in
the list to insert it.
◆ For ordered lists,we shall often use two new
operations that have no counterparts for other
lists,since they use keys rather than positions
to locate the entry,
◆ Note that ordered insertion is not uniquely
specified if the list already contains an entry
with the same key as the new entry,since the
new entry could go into more than one
position.
8.2 Insertion Sort
Contiguous Insertion Sort
template <class Record>
void Sortable_list<Record>::insertion_sort( )
{ int first_unsorted,position;
Record current;
for(first_unsorted = 1; first_unsorted < count;
first_unsorted++)
if(entry[first_unsorted] < entry[first_unsorted-1])
{ position = first_unsorted;
current = entry[first_unsorted];
do{ entry[position] = entry[position-1];
position--;
} while(position>0 && entry[position-1]>current);
entry[position] = current;
}
}
position of
first unsorted entry
searches sorted
part of list
Pull unsorted entry
out of the list.
Shift all entries
until the proper position
is found
position is not em tycurrent entry
store
proper position
Find’t current entries
proper position
Linked Insertion Sort
◆ With no movement of data,there is no need to
search from the end of the sorted sublist,as for the
contiguous case.
◆ Traverse the original list,taking one entry at a time
and inserting it in the proper position in the sorted
list.
◆ Pointer last sorted references the end of the sorted
part of the list.
◆ Pointer first_unsorted==last_sorted->next
references the first entry that has not yet been
inserted into the sorted sublist.
◆ Pointer current searches the sorted part of the list
to find where to insert *first_unsorted.
◆ If * first_unsorted belongs before the head of the
◆ Otherwise,move current down the list until
first_unsorted->entry <= current->entry
and then insert * first_unsorted before *current,
To enable insertion before *current,keep a second
pointer trailing in lock step one position closer to
the head than current.
◆ A sentinel is an extra entry added to one end of a
list to
ensure that a loop will terminate without having to
include a separate check,Since last_sorted->next
== first_unsorted,the node * first_unsorted is
already in position to serve as a sentinel for the
search,and the loop moving current is simplified.
◆ A list with 0 or 1 entry is already sorted,so by
checking these cases separately we avoid
template <class Record>
void Sortable_list<Record>::insertion_sort( )
{ Node<Record> *first_unsorted,*last_sorted,*current,
*trailing;
if(head == NULL) return;
last_sorted = head;
while(last_sorted->next != NULL)
{ first_unsorted = last_sorted->next;
if(first_unsorted->entry < head->entry)
{ last_sorted->next = first_unsorted->next;
first_unsorted->next = head; head = first_unsorted;
}
else
{ trailing = head; current = trailing->next;
while(first_unsorted->entry > current->entry)
{ trailing = current; current = trailing->next; }
the first unsorted node
to be inserted
tail of the
sorted sublist
used to traverse
the sorted sublistone position
behind current
the empty list
is already sortedThe first node alone makes a sorted sublist
Insert *first_unsorted
at the head of
the sorted list
Search the sorted
sublist to
insert*first_unsorted
*first_unsorted
now belongs between
*trailing and *current
if(first_unsorted == current)
last_sorted = first_unsorted;
else
{ last_sorted->next = first_unsorted->next;
first_unsorted->next = current;
trailing->next = first_unsorted;
}
} // end_above else( if-else block)
} // end_while
} // end_function
Analysis of Insertion Sort
◆ The average number of comparisons for
insertion sort applied to a list of n items in random
order is
◆ The average number of assignments of items
for insertion sort applied to a list of n items in
random order is also
◆ The best case for contiguous insertion sort
occurs when the list is already in order,when
insertion sort does nothing except n - 1
comparisons of keys.
◆ The worst case for contiguous insertion sort
occurs when the list is in reverse order.
THEOREM 8.1 Verifying that a list of n entries is in
the correct order requires at least n-1 comparisons
of keys.
◆ Insertion sort verifies that a list is correctly
sorted as quickly as any method can.
8.3 Selection Sort
Contiguous Selection Sort
template <class Record>
void Sortable_list<Record>::selection_sort( )
{ for(int position=count-1; position>0; position--)
{ int max=max_key(0,position);
swap(max,position);
}
}
template <class Record> int Sortable_list<Record>::
max_key(int low,int high)
{ int largest=low,current;
for(current=low-1; current<=high; current--)
if (entry[largest]<entry[current])largest=current;
return largest;
}
Auxiliary
member functions
template <class Record>
void Sortable_list<Record>:,swap(int low,int high)
{ Record temp=entry[low];
entry[low]=entry[high];
entry[high]=temp;
}
Analysis and comparison:
Selection Insertion
(average)Assignments of
entriesComparisons of
keys
8.4 Shell Sort
Shell Sort main function
template <class Record> void Sortable_list<Record>::
shell_sort( )
{ int increment=count,start;
do { increment = increment/3+1;
for(start = 0; start < increment; start++)
sort_interval(start,increment);
} while (increment > 1);
}
spacing of entries
in subliststarting point of sublistmodified insertion sort
Contiguous Shell Sort
Complement
template <class Record>
void Sortable_list<Record>::shell_sort( )
{ int hold; Record curr;
for(int inc=count/3; inc>0; inc/=2)
for(int start=inc; start<count; start++)
{ hold=entry[start]; curr=start-inc;
while(curr>=0 && hold<entry[curr])
{ entry[curr+inc]=entry[curr]; curr-=inc; }
entry[curr+inc]=hold;
}
}
初始增量为 count/3
将 Sortable_list
分为 3组
当增量为 1时
做最后一次
插入操作
修改增量为 inc/2
可以确保 增量
改变成 1
insertion sort
(interval = inc)
8.5 Lower Bounds for
SortingHow fast is it possible to
sort?
THEOREM 8.2 Any algorithm that sorts a list of n
entries by use of key comparisons must,in its
worst case,perform at least ?lg n! ? comparisons
of keys,and,in the average case,it must perform
at least lg n! comparisons of keys.
Outline:
8.6 Divide-and-Conquer Sorting
void Sortable_list::sort( )
{ if the list has length greater than 1
{ partition the list into lowlist,highlist;
lowlist.sort( );
highlist.sort( );
combine(lowlist,highlist);
}
}
Mergesort:
We chop the list into two sublists of sizes as
nearly equal as possible and then sort them
separately,Afterward,we carefully merge the two
sorted sublists into a single sorted list.
Quicksort:
We first choose some key from the list for which,
we hope,about half the keys will come before and
half after,Call this key the pivot,Then we partition
the items so that all those with keys less than the
pivot come in one sublist,and all those with
greater keys come in another,Then we sort the
two reduced lists separately,put the sublists
together,and the whole list will be in order.
枢轴,支点
Mergesort Example:
Quicksort of 7 Numbers Example:
Sort (26,33,35,29,12,22)
8.7 Mergesort for Linked Lists
template <class Record>
void Sortable_list<Record>::merge_sort( )
{ recursive_merge_sort(head); }
Interface method
template <class Record> void Sortable_list<Record>::
recursive_merge_sort(Node<Record> * &sub_list)
{ if(sub_list != NULL && sub_list->next != NULL)
{ Node<Record> *second_half = divide_from(sub_list);
recursive_merge_sort(sub_list);
recursive_merge_sort(second_half);
sub_list = merge(sub_list,second_half);
}
}
recursive functionCall function
partition the list
into sub-lists
and second_half
Call function
combine the two sublists
template <class Record>
Node<Record>
*Sortable_list<Record>::divide_from(Node<Record>
*sub_list)
{ Node<Record> *position,*midpoint,*second_half;
if((midpoint=sub_list) == NULL) return NULL;
position=midpoint->next;
while(position != NULL)
{ position = position->next;
if(position != NULL)
{ midpoint=midpoint->next; position = position-
>next; }
}
second_half = midpoint->next;
midpoint->next = NULL;
return second_half;
}
traverses the entire listmoves at half speed
of position to midpointList is empty
Move position twice
for midpoint's
one move
second_half point to
the last halfFirst half rear nodenext set NULL
template <class Record> Node<Record>
Sortable_list<Record>::
merge(Node<Record> *first,Node<Record> *second)
{ Node<Record> combined;
Node<Record> * last_sorted = &combined;
while(first != NULL && second != NULL)
if(first->entry <= second->entry)
{ last_sorted->next=first; last_sorted=first;
first=first->next; }
else { last_sorted->next = second;
last_sorted = second; second = second->next;
}
if (first==NULL) last_sorted->next = second;
else last_sorted->next=first;
return combined.next;
}
dummy first node,
points to merged
list dummy
points to the last node
of sorted listAttach node with smaller key
Advance to the next
unmerged node
After one list ends,
attach the remainder
of the other
Analysis of Mergesort Sublist length
Lower bound:
Mergesort:
Insertion sort:
8.8 Quicksort for Contiguous Lists
template <class Record>
void Sortable_list<Record>::quick_sort( )
{ recursive_quick_sort(0,count-1); }
Interface method
template <class Record> void Sortable_list<Record>::
recursive_quick_sort(int low,int high)
{ int pivot_position;
if (low<high)
{ pivot_position=partition(low,high);
recursive_quick_sort(low,pivot_position-1);
recursive_quick_sort(pivot_position+1,high);
}
}
Otherwise,n
sorting is needed
Call function
partition the list
into low and high
two parts
template <class Record>
int Sortable_list<Record>::partition(int low,int high)
{ Record pivot;
int i,last_small = low;
swap(low,(low +high)/2);
pivot=entry[low];
for(i=low+1; i<=high; i++)
if(entry[i]<pivot)
{ last_small=last_small +1; swap(last_small,i); }
swap(low,last_small);
return last_small;
}
used to scan
through the listposition of the last key less than pivotPut pivot into
its proper position
Analysis of Quicksort
Worst-case analysis:
If the pivot is chosen poorly,one of the partitioned
sublists may be empty and the other reduced by
only one entry,In this case,quicksort is slower
than either insertion sort or selection sort.
Choice of pivot:
◆ First or last entry,Worst case appears for a list
already
sorted or in reverse order.
◆ Central entry,Poor cases appear only for
unusual orders.
◆ Random entry,Poor cases are very unlikely to
occur.
Average-case
analysis:
In its average case,quicksort performs
comparisons of keys in sorting a list of n entries
in random order.
See Pg.356-359
8.9 Heaps and Heapsort
Trees,Lists,and Heaps
If the root of the tree is in position 0 of the list,
then the left and right children of the node in
position k are in positions 2k+1 and 2k+2 of the
list,respectively,If these positions are beyond
the end of the list,then these children do not
exist.
DEFINITION A heap is a list in which each entry
contains a key,and,for all positions k in the list,
the key at position k is at least as large as the
keys in positions 2k +1 and 2k+2,provided these
positions exist in the list.
REMARK Many C++ manuals and textbooks
refer to the area used for dynamic memory as
the ìheap?; this use of the word ìheap? has
nothing to do with the present definition.
Heapsort is suitable only for contiguous lists.
Example,MaxHeapMinHeapThe not is Heap
See Pg.364 - 367 Fig.8.16 - Fig.8.18
template <class Record>void
Sortable_list<Record>::heap_sort( )
{ Record current;
int last_unsorted;
build_heap( );
for(last_unsorted=count-1; last_unsorted >
0;last_unsorted--)
{ current=entry[last_unsorted];
entry[last_unsorted]=entry[0];
inser_heap(current,0,last_unsorted-1);
}
}
temporary storage
for moving entries
Entries beyond
last_unsorted
have been sorted
Return the list
into a heap
(Auxiliary functions)
Extract last_entry
from list
Move top of
heap to the endRestore the heap
template <class Record>void
Sortable_list<Record>::build_heap( )
{ int low;
for(low=count/2-1; low>=0; low--)
{ Record current=entry[low];
inser_heap(current,low,count-1);
}
}
All entries beyond
the positionlow
form a heapAuxiliary functions
template <class Record> void Sortable_list<Record>::
inser_heap(const Record ¤t,int low,int high)
{ int large=2*low+1;
while(large<=high)
{ if(large<high && entry[large]<entry[large+1])large++;
if(current>=entry[large]) break;
else { entry[low]=entry[large]; low = large;
large=2*low+1; }
}
entry[low]=current;
}
position of child of
entry[low] with
the larger key
large is now
the left child of low
large is now the child
of low with the largest key
current belongs
in position low
Promote entry[large]
and move d wn the tree
Analysis of Heapsort
In its worst case for sorting a list of length n,
heapsort performs
comparisons of keys,and it performs
assignments of entries.
Priority Queues See Pg,369
DEFINITION A priority queue consists of entries,
such that each entry contains a key called the
priority of the entry,A priority queue has only two
operations other than the usual creation,clearing,
size,full,and empty operations:
?Insert an entry.
?Remove the entry having the largest (or smallest)
key.
If entries have equal keys,then any entry with the
largest key may be removed first.
Summary and Review
Comparison of Sorting Methods
template <class Record>
class Sortable_list, public List<Record>
{ public,
Inherit List
(Contiguous or
Linked)
Interface method
void insertion_sort( ); //pg.322 pg.324
void selection_sort( ); //pg.330
void shell_sort( ); // pg.335
void merge_sort( ); //pg.345
void quick_sort( ); //pg.353
void heap_sort( ); //pg.365
private,
int max_key(int low,int high); //pg.331
void swap(int low,int high); //pg.331
void sort_interval(int start,int increment);
void recursive_merge_sort(Node<Record>*&sub_list);
//pg.345
Node<Record> *divide_from(Node<Record>*sub_list);
//pg.346
Node<Record> *merge(Node<Record> *first,
Node<Record> *second); //pg.347
using
Contiguous List
using
Linked List
Auxiliary functions
int partition(int low,int high); //pg.355
void recursive_quick_sort(int low,int high); //pg.353
void insert_heap(const Record ¤t,int low,int
high);
//pg.366
void build_heap(); //pg.368
};Comparison of Sorting Methods
◆ Use of space
◆ Use of computer time
◆ Programming effort
◆ Statistical analysis
◆ Empirical testing
Pointers and Pitfalls
◆ Many computer systems have a general-purpose
sorting utility,If you can access this utility and it
proves adequate for your application,then use it
rather than writing a sorting program from scratch.
◆ In choosing a sorting method,take into account
the ways in which the keys will usually be arranged
before sorting,the size of the application,the
amount of time available for programming,the
need to save computer time and space,the way in
which the data structures are implemented,the
cost of moving data,and the cost of comparing
keys.
◆ Divide-and-conquer is one of the most widely
applicable and most powerful methods for
designing algorithms,When faced with a
programming problem,see if its solution can be
obtained by first solving the problem for two (or
more) problems of the same general form but of a
smaller size,If so,you may
be able to formulate an algorithm that uses the
divide-and-conquer method and program it using
recursion.
◆ Mergesort,quicksort,and heapsort are
powerful sorting methods,more difcult to
program than the simpler methods,but much
more efcient when applied to large lists,Consider
the application carefully to determine whether the
extra effort needed to implement one of these
◆ Priority queues are important for many
applications,Heaps provide an excellent
implementation of priority queues.
◆ Heapsort is like an insurance policy,It is
usually slower than quicksort,but it guarantees
that sorting will be completed in O(n log n)
comparisons of keys,as quicksort cannot always
do.
