Transcript CPS120: Introduction to Computer Science

CPS120: Introduction to
Computer Science
Sorting
Abstract Data Types
• Abstract data type: a data type whose
properties (data and operations) are
specified independently of any particular
implementation
• The goal in design is to reduce complexity
through abstraction
Linked Implementation
A linked list
Stacks
• A stack is an abstract data type in which
accesses are made at only one end
– LIFO, which stands for Last In First Out
– The insert is called Push and the delete is
called Pop
Queues
• Queue is an abstract data type in which
items are entered at one end and removed
from the other end
– FIFO, for First In First Out
– Like a waiting line in a bank or supermarket
– No standard queue terminology
• Insert is used for the insertion operation
• Remove is used for the deletion operation.
Trees
• ADTs such as lists, stacks, and queues are
linear in nature
• More complex relationships require more
complex structures
Binary Search Trees
• A binary search tree has the shape property
of a binary tree
Binary Search Tree
The value in any node is greater than the
value in any node in its left subtree and less
than the value in any node in its right subtree
Basics of Sorting
• When you rearrange data and put it into a
certain kind of order, you are sorting the
data.
• You can sort data alphabetically,
numerically, and in other ways.
• Often you need to sort data before you use
searching algorithms to find a particular
piece of data.
Key Fields
• The key field is the field upon which the
data is sorted.
• A key value is a specific value that is stored
within the key field.
• The input size is the number of elements in
a list that will eventually be sorted.
Approaches to Sorting
• There are two basic approaches to sorting data
– The incremental approach
– The divide and conquer approach.
• Using the incremental approach, one sorts the
whole list at once using loops
• The divide and conquer approach splits the list up
into parts and sorts each part separately. Then this
approach manages to join the sorted parts together
into a large sorted list
Sorting Algorithms
• There are a number of different sorting
algorithms that are widely used by
programmers.
• Each algorithm has its own advantages and
disadvantages.
Selection Sort
• Sorting a List of names manually
– Put them in alphabetical order
• Find the name that comes first in the alphabet,
and write it on a second sheet of paper
• Cross out the name on the original list
• Continue this cycle until all the names on the
original list have been crossed out and written
onto the second list, at which point the second list is
sorted
Understanding the Selection Sort
• The selection sort is an incremental one
• Every key value is examined starting at the
beginning of the list.
• A temporary variable to "remember" the position
of the largest key value
• By the time you have examined every key value,
you swap the key value that was the largest with
the last key value in the list
• Next, you repeat the process again from the
beginning of the list, however, you will not need
to compare anything to the new last key value in
the list since you know it is the largest
Selection Sort
Example of a selection sort (sorted elements are shaded)
The Insertion Sort
• The insertion sort is incremental in nature.
• This is similar to the way a person usually
organizes a hand of playing cards.
• The insertion sort is relatively quick for
small lists that are close to being sorted
Insertion Sorting
Mary
Mary
Gerri
Terry
Gerri
Kari
Gerri
Kari
Harry
Kari
Harry
Barry
Harry
Barry
Mary
Barry
Terry
Terry
Bubble Sort
• A sort that uses a different scheme for
finding the minimum value
– Starting with the last list element, we compare
successive pairs of elements, swapping
whenever the bottom element of the pair is
smaller than the one above it
Understanding the Bubble Sort
• The bubble sort is an incremental sort which is usually
faster than the insertion and selection sorts.
• A bubble sort works similarly to the release of CO2 in
carbonated soda
• The use of the Boolean variable causes this sort to only
sweep the list one extra time after it has been fully
sorted. This makes the bubble sort more efficient than a
number of other incremental sorts
Bubble Sort
Example of a
bubble sort
Quicksort
Based on the idea that it is faster and easier to sort
two small lists than one larger one
Understanding the Quick Sort
• The quicksort is a divide and conquer
algorithm and is more efficient than
incremental sorts. It can be difficult to code
though since it uses recursion or stacks.
• The original list is partitioned into two lists.
– One of the lists contains elements that are
greater than the first original element.
– The second list contains elements that are less
than or equal to the first original element.
Quicksort
Pages 292–293