CIS3355: Business Data Structures
Fall, 2008
 

What are the basic categories and types of Sorts?

I. There are two basic categories of Sorts:

            A.    Internal Sort

• Works with list elements manipulated in RAM.

• They are fast with input and output.

• The problem is that its limited by the amount in RAM.

           B.    External Sort

• Works with list elements that are manipulated by storing the elements to secondary storage (disk space).

• They are used for large lists.

• They are slow with input and output.

• The problem is that its limited by secondary storage (disk space).

A. There are three basic types of Internal Sorts:

1.    Exchange Sort

• They are used for single list.

•  Works by finding and swapping incorrectly ordered pairs.

2.    Selection Sort

• They are generally for two (or more) lists.

• Selection with exchange uses only one list.

• Works by selecting the largest/smallest (depends on how you want to sort) in each pass and placing it into the correct position.

3.    Insertion Sort

• They are used for one or two lists (two are more common).

• Works by selecting each item from the original list and inserting it into the correct position in the new list.

1. There are two commonly types of Exchange Sorts:

                                      a.    Bubble Sort

• They are the most common and simplest of all sorts.

• They are used for small lists.

• Works by continually examining the list of data and letting the largest/smallest (depends on how you want to sort) element bubble to the top/bottom of the list with each pass.

Example:

Given:   

• Point to bottom element -> 2

• Compare with element above -> 5

  

o   If element is greater, swap positions (in this case, swap)

o    If element is smaller, reset the  bottom pointer

• Continue the process until the largest element is at the end

o    It will require n-1 (4 for our example) (where n = the length of the unsorted list)

• At end of pass

o   The largest number is in the last position

How it works:

                  Pass #1                                Comparison

         1        don't swap  2 and 5

        2        swap 5 and 1

         3        swap 5 and 4

         4        swap 5 and 3

The new list (note: 4(n-1) comparisons were required, we know   that the largest element is at the end of the list)

Pass #2                     Comparison

     1 (5)        swap 2 and 1

     2 (6)        don't swap 2 and 4

     3 (7)        swap 4 and 3

     4 (8)         don't swap 4 and 5

     And here is the new list

                                        b.    Quick Sort

• They are used for larger lists.

• They are generally the fastest sort.

• Works by breaking the list up into smaller lists, sorts the smaller list, and then merges the lists together, the process continues until there is only one element left on the list.

Example:

quicksort( void *a, int low, int high )
  {
  int pivot;
  /* Termination condition! */
  if ( high > low )
    {
    pivot = partition( a, low, high );
    quicksort( a, low, pivot-1 );
    quicksort( a, pivot+1, high );
    }
  }

Here are some good references:

1. http://oopweb.com/Algorithms/Documents/Sman/VolumeFrames.html

2. http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/ds_ToC.html

At this point in time, you should be able to Answer the following questions:

1. Describe the differences between internal and external sorting methods?

Internal Sorts:

• How? List elements are manipulated in RAM
• Why? Faster
• Problem? Limited by amount of RAM (List size)

External Sorts:

• How? List elements are manipulated by storing the elements to secondary storage
• Why? The List is too large to be stored in RAM
• Problem? Much Slower

2. When should each be used?

The answer to when each should be used is determined by whether or not the list can be stored in RAM. 

3. Describe how a bubble sort works.  

A bubble sort works by ‘bubbling’ the larger elements to the top of the list or ‘bubbling’ the smaller elements to the bottom of the list (depending on the direction of the sort, and whether or not the list is to be sorted in ascending order or descending order).

4. Explain how a quick sort works.

   A quick sort works by recursively partitioning a list into smaller sublists, each time making sure that the sublists to the left contain smaller elements than the list it was derived from, while the sublists to the right contain elements larger than the sublists to the right. The process continues until there is only one element left on the list.