Sorting
By Fanon Ananda
Big Oh Notation
• A convenient way of describing the growth
rate of a function and hence the time
complexity of an algorithm.
• Let n be the size of the input
– O(1) refers to constant time.
– O(n) indicates linear time;
– O(nk) (k fixed) refers to polynomial time;
– O(log n) is called logarithmic time;
– O(2n) refers to exponential time, etc.
2
Sorting
• Consider list
x 1, x 2, x 3, … x n
• We seek to arrange the elements of the list in
order
– Ascending or descending
• Some O(n2) schemes
– easy to understand and implement
– inefficient for large data sets
Categories of Sorting Algorithms
• Selection sort
– Find the minimum value in the list
– Swap it with the value in the first position
– Repeat the steps above for remainder of the list (starting at the
second position)
Categories of Sorting Algorithms
• Exchange sort
– Systematically interchange pairs of elements
which are out of order
– Bubble sort does this
Out of order, exchange In order, do not exchange
Difference Between Exchange
Sort and Bubble Sort
• (Some people refer to the "exchange sort" as
a "bubble sort".)
• The difference between the two algorithms is
the manner in which they compare the
elements.
• The exchange sort compares the first
element with each following element of
the array, making any necessary swaps.
Exchange Sort
Example(descending order)
• Array at beginning: 84 69 76 86 94 91
• After Pass #1: 94 69 76 84 86 91
• After Pass #2: 94 91 69 76 84 86
• After Pass #3: 94 91 86 69 76 84
• After Pass #4: 94 91 86 84 69 76
• After Pass #5 (done): 94 91 86 84 76 69
Bubble Sort Algorithm
• It works by repeatedly stepping through the list to be sorted,
comparing two items at a time and swapping them if they
are in the wrong order.
• The pass through the list is repeated until no swaps are
needed, which means the list is sorted.
for (i=0; i<n-1; i++) {
for (j=0; j<n-1-i; j++)
if (a[j+1] < a[j]) { /* compare the two neighbors */
tmp = a[j]; /* swap a[j] and a[j+1] */
a[j] = a[j+1]; a[j+1] = tmp;
}
}
Categories of Sorting Algorithms
• Insertion sort
– Repeatedly insert a new element into an already
sorted list
– Note this works well with a linked list
implementation
All these have
computing time O(n2)
Example of Insertion Sort
• Given list to be sorted
67, 33, 21, 84, 49, 50, 75
– Note sequence of steps carried out
Indirect Sorts
• Possible that the items being sorted are large
structures
– Data transfer/swapping time unacceptable
• Alternative is indirect sort
– Uses index table to store positions of the objects
– Manipulate the index table for ordering
Quicksort
• A more efficient exchange sorting scheme than
bubble sort
– A typical exchange involves elements that are far
apart
– Fewer interchanges are required to correctly position
an element.
• Quicksort uses a divide-and-conquer strategy
– A recursive approach
– The original problem partitioned into simpler sub-
problems,
– Each sub problem considered independently.
• Subdivision continues until sub problems
obtained are simple enough to be solved directly
Quicksort
• Choose some element called a pivot
• Perform a sequence of exchanges so that
– All elements that are less than this pivot are to its left and
– All elements that are greater than the pivot are to its right.
• Divides the (sub)list into two smaller sub lists,
• Each of which may then be sorted independently in
the same way.
Quicksort
If the list has 0 or 1 elements,
return. // the list is sorted
Else do:
Pick an element in the list to use as the pivot.
Split the remaining elements into two disjoint groups:
SmallerThanPivot = {all elements < pivot}
LargerThanPivot = {all elements > pivot}
Return the list rearranged as:
Quicksort(SmallerThanPivot),
pivot,
Quicksort(LargerThanPivot).
Quicksort Example
• Given to sort:
75, 70, 65, 84 , 98, 78, 100, 93, 55, 61, 81, 68
• Select, arbitrarily, the first element, 75, as pivot.
• Search from right for elements <= 75, stop at
first element <75
• Search from left for elements > 75, stop at first
element >=75
• Swap these two elements, and then repeat this
process
Assignment
• Show an example of quick sort operation as
part of your assignment 2
Mergesort
• Sorting schemes are either …
– internal -- designed for data items stored in
main memory
– external -- designed for data items stored in
secondary memory.
• Previous sorting schemes were all internal
sorting algorithms:
– required direct access to list elements
• not possible for sequential files
– made many passes through the list
• not practical for files
Mergesort
• Mergesort can be used both as an internal
and an external sort.
• Basic operation in mergesort is merging,
– combining two lists that have previously been
sorted
– resulting list is also sorted.
Merge Algorithm
1. Open File1 and File2 for input, File3 for output
2. Read first element x from File1 and
first element y from File2
3. While neither eof File1 or eof File2
If x < y then
a. Write x to File3
b. Read a new x value from File1
Otherwise
a. Write y to File3
b. Read a new y from File2
End while
4. If eof File1 encountered copy rest of of File2 into File3.
If eof File2 encountered, copy rest of File1 into File3
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson 19
Education, Inc. All rights reserved. 0-13-140909-3
Priority Queue
• A collection of data elements
– Items stored in order by priority
– Higher priority items removed ahead of lower
• Operations
– Constructor
– Insert
– Find, remove smallest/largest (priority) element
– Replace
– Change priority
– Delete an item
– Join two priority queues into a larger one
Priority Queue
• Implementation possibilities
– As a list (array, vector, linked list)
– As an ordered list
– Best is to use a heap
– Basic operations have O(log2n) time
– Read and show an example of operations on a
priority queue in your assignment.
Assignment 2
• Explain and show an example of any other 2
sorting algorithms not discussed in class