Transcript Sorts - Tonga Institute of Higher Education

Sorts
Tonga Institute of Higher
Education
Introduction - 1


Sorting – The act of ordering data
Often, we need to order data.
 Example:
 Order a list of names


Different sorting techniques work best in
different situations
Sorting is very important to making efficient
programs so a lot of research is done in this
area.
Introduction - 2

Sorting Algorithms

Bubble Sort
 Selection Sort
 Insertion Sort

All these sorting routines do 2 steps
repeatedly
Compare 2 items
2. Swap 2 items or copy 1 item
1.
Bubble Sort



Very Slow
Simplest way to sort
Rules
1.
2.
3.
4.
5.
6.
Start from left side
Compare 2 items
If the item on the left is bigger, switch them
Move cursor one position right
Repeat from step 2 until cursor is at the end of the
list. At this point, you have put the largest item at
the end of the list. This item will no longer be
included in this algorithm.
Repeat from step 1 until items are sorted
Demonstration
Bubble Sort Applet
Demonstration
Bubble Sort Code
Project: BubbleSort
Bubble Sort Efficiency

Number of Comparisons

First Pass





Number of items - 1
=N-1
Number of items - 2
=N–2


If the data is random,
swaps occur ½ the time
when a comparison is
made.
((N2 – N) / 2) / 2
= (N2 – N) / 4
So total is:




Number of Swaps
Second Pass



(N -1) + (N – 2) + … + 1
= N*(N-1) / 2
= (N2 – N) / 2
Both comparisons and swaps have an N2
 We
ignore the constant numbers
 Therefore, the bubble sort compares and swaps in
O(N2) time.
Selection Sort


Has less number of swaps than bubble
sorts
Rules
Check every item to find smallest value
2. Swap the item with the smallest value with
the leftmost item. The leftmost item will no
longer be included in this algorithm.
3. Repeat from step 1 until items are sorted
1.
Demonstration
Selection Sort Applet
Demonstration
Selection Sort Code
Project: SelectionSort
Selection Sort Efficiency - 1

Number of Comparisons
 First Pass
 Number of items - 1
 = N - 1
 Second Pass
 Number of items - 2
 = N – 2
 So



total is:
(N -1) + (N – 2) + (N – 3) + … + 1
= N*(N-1)/2
Number of Swaps
 Less
than N swaps
Selection Sort Efficiency - 2

Number of Comparisons

Total is:


= N*(N-1)/2

Number of Swaps

Total is:

Less than N
Comparisons have an N2

We ignore the constant numbers
 Therefore, the selection sort compares in O(N2) time

Swaps have an N



Therefore, the selection sort swaps in O(N) time
For small N values: Selection sorts run faster than bubble sorts
because there are less swaps.
For large N values: Selection sorts run faster than bubble sorts
because there are less swaps. However, the performance will be
close to O(N2) than O(N) because the comparison times will dominate
the swap times.
Insertion Sort - 1


Partial Sorting – Keeping a sorted list of items in
a unsorted list
Marked Item – The leftmost item that has not
been sorted
Insertion Sort - 2

Rules
1.
2.
3.
4.
5.
Take out marked item
Compare marked item
with item on left
If the item on left is
bigger, then move bigger
item 1 place to the right
Repeat from step 2 until
the item on the left is
smaller. Then, put the
marked item in the blank
space
Set marked item 1 place
to the right. Repeat from
step 1
Demonstration
Insertion Sort Applet
Demonstration
Insertion Sort Code
Project: InsertionSort
Insertion Sort Efficiency - 1

Number of Comparisons

First Pass


Second Pass


2
Last Pass


1
N-1
So total is:


1+2+…+N-1
= N*(N-1)/2

However, on average, only half of the items are compared before the
insertion point is found.
 So the total:


= N*(N-1)/4
Number of Copies

Almost the same as the number of comparisons
Insertion Sort Efficiency - 2

Number of Comparisons

Total:


= N*(N-1)/4

Number of Copies

Total:

= N*(N-1)/4
Comparisons have an N2
Therefore, the insertion sort compares in O(N2) time
 However, does half as many comparisons as bubble sorts and selection
sorts


Copies have an N2






Therefore, the insertion sort copies in O(N2) time
A copy is much faster than a swap
This is twice as fast as a bubble sort for random data
This is slightly faster than a selection sort for random data
This is much faster when data is almost sorted
This is the same as a bubble sort for inverse sorted order because every
possible comparison must be carried out
Comparing the 3 Sorts

Bubble Sorts



Selection Sorts




Easiest
Slowest
Same number of comparisons as bubble sorts
Much less number of swaps than bubble sorts
Works well when data is small and swapping takes much longer
than comparisons
Insertion Sorts




Best sort we’ve learned about
½ the number of comparisons as bubble sorts and selection
sorts
Copies instead of swaps, which is much faster
Works well when data is small and data is almost sorted