3-2-6 Sorting

Why is efficient sorting so important?

• So we can carry out binary searches on large databases
• Interactive systems rely on data being retrieved from these systems quickly.

Bubble Sort:

• Start at the beginning of the list.
• Compare each pair of items.
• If they are not in order, swap them.
• Work through the list n-1 times.

Insertion Sort:

In an Insertion Sort, we divide the list into a sorted part and an unsorted part (to begin with, only the first item in the list is sorted). The next element is the new Current element, and it is compared with the first one and sorted. This goes on with each elemebt until the list is sorted completely.

The next element to be inserted into the correct place is shown in red.  The sorted part of the list is green.

Advantage:

• Faster than a Bubble sort.

Disadvantage:

• Harder to code.

Quicksort: 

• A sorting method developed by Tony Hoare in the 1960's.
• The idea is to divide and conquer: split the list into 2 parts, one containing values less than a pivot value, the others containing values greater than it.
• The pivot value can be arbitrarily chosen.

A Quicksort is a lot quicker than and Insetion sort and a bubble sort.