Sorting

Introduction

One of the most common and necessary actions in computing is to sort data. It allows us to make sense of or find information easier. It is for this reason that there are over 30 different types of sorting.

Defining "Sorting"

We can define sorting as the ordering of data according to some criteria. The most common ways of that we use are lexicographical and numerical, but that does not mean there aren't other, more complex ways of sorting. As humans we are capable of sorting a group of items very quickly because our brains are capable of viewing the entire list of items and doing multiple comparisons at the same time.

Computers are not so lucky: They can only make one comparison at a time and as such need some sort of strategy with which to sort. Such strategies typically involve a comparison of two elements in a list and a swap.

Activity:

Create your own sorting strategy. In groups, brainstorm and come up with your own sorting strategy. Once you have a strategy, try it out with a random group of manipulatives (cards) to see if it will result in a sorted array. While executing your sort note the following:

The original state of the group of manipulatives
The number of comparisons being made
The number of swaps being performed

Present your strategy, being sure to tell the class

your criteria for comparison
the original state of the group of manipulatives
does the strategy work? (i.e. is the final state of the objects sorted or unsorted)
if it does work:
- the number of comparisons being made to bring the array to its sorted state
- the number of swaps performed to bring the array to its sorted state
if it does not work:
- how did you know it won't work
- do you know how to fix it? If so, how?

Walk-Through: Bubble Sort

Sorting

Activities

Implement the Pseudocode from the following two algorithms. Once finished, answer the following questions.
1. In your own words, describe the strategies used by Insertion Sort and Selection sort.
2. Assume that you have an array of 5 integers that are in random order. How many comparisons are performed before Insertion Sort finishes? Selection Sort?
3. Assume that you have an array of 5 integers that are already sorted. How many comparisons are performed before Insertion Sort finishes? Selection Sort?
4. When we talk about sorting, we often discuss the "worst-case" scenarios for the algorithms. The worst case occurs when the data is arranged in such a way that we have the highest number of comparisons before it completes. What arrangement of data causes the "worst-case" for Insertion sort? Selection Sort?
5. When is selection sort faster than insertion sort? When is insertion sort faster than selection sort?

Insertion Sort

A is an array

v is the item to swap

for j = 0 to size(A) - 1

  v = j

  for i = j + 1 to size(A)

    if A[i] < A[v]

      v = i

    end if

  end for

  if v not = j

    swap (A[j], A[v])

  end if

end for

Selection Sort

A is an array

v is the item to insert

for i = 1 to size(A)

  v = A[i]

  j = i

  while j > 0 and v < A[j - 1]

    A[j] = A[j - 1]

    j-= 1

  end while

  A[j] = v

end for

Report abuse