程序代写代做代考 algorithm chain data structure PowerPoint Presentation

PowerPoint Presentation

Sorting Algorithms
and their Efficiency
Chapter 11
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Contents
Basic Sorting Algorithms
Faster Sorting Algorithms
A Comparison of Sorting Algorithms

Basic Sorting Algorithms
Sorting is:

A process
It organizes a collection of data
Organized into ascending/descending order
Internal: data fits in memory
External: data must reside on secondary storage
Sort key: data item which determines order

The Selection Sort
FIGURE 11-1 A selection sort of an array of five integers
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Selection Sort
View implementation of the selection sort,
Listing 11-1
Analysis

This is an O (n2 ) algorithm
If sorting a very large array, selection sort algorithm probably too inefficient to use

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
.htm code listing files must be in the same folder as the .ppt files for these links to work

The Bubble Sort
FIGURE 11-2 The first two passes of a bubble sort
of an array of five integers
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Bubble Sort
View an implementation of the bubble sort,
Listing 11-2
Analysis

Best case, O(n) algorithm
Worst case, O(n2) algorithm
Again, a poor choice for large amounts of data

The Insertion Sort
Take each item from unsorted region, insert into its correct order in sorted region

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
FIGURE 11-3 An insertion sort partitions
the array into two regions

The Insertion Sort
FIGURE 11-4 An insertion sort of an
array of five integers
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Insertion Sort
View implantation of insertion sort,
Listing 11-3
Analysis

An algorithm of order O(n2)
Best case O(n)
Appropriate for 25 or less data items

The Merge Sort
FIGURE 11-5 A merge sort with an
auxiliary temporary array
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Merge Sort
FIGURE 11-6 A merge sort of an array of six integers
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Merge Sort
View implementation of the merge sort,
Listing 11-4
Analysis

Merge sort is of order O(n  log n)
This is significantly faster than O(n2)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Merge Sort
FIGURE 11-7 A worst-case instance of the
merge step in a merge sort
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Merge Sort
FIGURE 11-8 Levels of recursive calls to mergeSort , given an array of eight items
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Quick Sort
FIGURE 11-9 A partition about a pivot
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Quick Sort
FIGURE 11-10 Partitioning of array during quick sort
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Quick Sort
FIGURE 11-11 Median-of-three pivot selection:
(a) The original array; (b) the array with its
first, middle, and last entries sorted
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Quick Sort
FIGURE 11-12 (a) The array with its first, middle, and last entries sorted; (b) the array after positioning the pivot and just before partitioning
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Quick Sort
Note function that performs a quick sort,
Listing 11-5
Analysis

Worst case O(n2)
Average case O(n  log n)
Does not require extra memory like merge sort
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Quick Sort
FIGURE 11-13 kSmall versus quickSort
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Radix Sort
Uses the idea of forming groups, then combining them to sort a collection of data.
Consider collection of three letter groups

ABC, XYZ, BWZ, AAC, RLT, JBX, RDT, KLT, AEO, TLJ
Group strings by rightmost letter

(ABC, AAC) (TLJ) (AEO) (RLT, RDT, KLT) (JBX) (XYZ, BWZ)
Combine groups

ABC, AAC, TLJ, AEO, RLT, RDT, KLT, JBX, XYZ, BWZ
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Radix Sort
Group strings by middle letter

(AAC) (A B C, J B X) (R D T) (A E O) (T L J, R L T, K L T) (B W Z) (X Y Z)
Combine groups

AAC, ABC, JBX, RDT, AEO, TLJ, RLT, KLT, BWZ, XYZ
Group by first letter, combine again

( A AC, A BC, A EO) ( B WZ) ( J BX) ( K LT) ( R DT, R LT) ( T LJ) ( X YZ)
Sorted strings

AAC, ABC, AEO, BWZ, JBX, KLT, RDT, RLT, TLJ, XYZ
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Radix Sort
FIGURE 11-14 A radix sort of eight integers
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Radix Sort
Analysis

Has order O(n)
Large n requires significant amount of memory, especially if arrays are used
Memory can be saved by using chain of linked nodes
Radix sort more appropriate for chain than for array

Comparison of Sorting Algorithms
FIGURE 11-15 Approximate growth rates of time required for eight sorting algorithms
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Related Posts