Transcript Selection sort

An Introduction to
Sorting
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 1
Objectives
1. To learn how to use the standard sorting
methods in the Java API
2. To learn how to implement the following
sorting algorithms: selection sort, mergesort,
and quicksort – no insertion, shell, radix, or
bubble sort
3. To understand the difference in performance
of these algorithms, and which to use for
small arrays, which to use for medium arrays,
and which to use for large arrays
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 2
Applications of Sorting
•
•
•
•
The most intensively studied processing
Internal sorting - data fit into RAM
External sorting - data are on the disk
Sorting speeds up search:
Dictionary
Files in a directory
Calendar
Phone list
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 3
Sorting Arrays
• Sorting is the task of putting data into a particular
order either ascending or descending
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 4
Selection Sort
• The Selection sort begins at the front of the list
and looks for the first element smaller (or larger)
than the current element. Then the elements are
switched.
– The actual identification of the element to switch is
based upon the type of sort
• Ascending or descending
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 5
Selection Sort
• Example – Selection.java
• Analysis – best, worst, and average cases are:
Q(n2)
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 6
Merge Sort
• The merge sort algorithm requires recursion
– The concept used in this algorithm is called
divide-and-conquer
• The array is first split into two smaller arrays
• Each of the smaller two arrays are recursively
sorted
• The two arrays are merged back into one array
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 7
Merge Sort
– The base case for the merge sort is when the
array to be sorted only has one element left that
does not need to be rearranged
– If there is more than one element to sort, split the
arrays into two sections and call the merge sort
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 8
Merge Sort
• Example – Merge.java
• The best, worst, and average cases require Q(n
log n)
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 9
Quick Sort
• Quick sort is also a divide-and-conquer recursive
sorting method
– The difference is the method in which the array is
divided
• Determine the final position in the sorted array of the
first element of the unsorted array. (all values to the
left of the element are less than the element and all
values to the right of the element are greater than the
element). - Pivot point
– After the array is divided, the sort is performed on
the two unsorted sub-arrays
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 10
Quick Sort
• Example – Qsort.java
• Best and average cases are Q(n log n)
• Worst case is Q(n2)
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 11
Comparison of Sorts
• Quick Sort and Merge Sort will always be faster
than the Selection sort.
• Quick Sort sorts “in place” and the hidden
constant in the average case is smaller than
Merge Sort's
• Merge Sort’s worst case behavior is better than
Quick Sort’s worst case
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 12
Using Java Sorting Methods
• Java API provides a class Arrays with several
overloaded static sort methods for different array
types
• The Collections class provides similar sorting
methods
• Sorting methods for arrays of primitive types are
based on quicksort algorithm
• Method of sorting for arrays of objects and Lists
based on mergesort
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 13
Selection Sort
• Sorting: Arrange things into either ascending or
descending order
• Task: rearrange books on shelf by height
– Shortest book on the left
• Approach:
–
–
–
–
–
Look at books, select shortest book
Swap with first book
Look at remaining books, select shortest
Swap with second book
Repeat …
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 14
Selection Sort
Before and after exchanging shortest book
and the first book.
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 15
Selection Sort
A selection sort of an
array of integers into
ascending order.
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 16
Selection Sort
• Iterative algorithm for selection sort
Algorithm selectionSort(a, n)
// Sorts the first n elements of an array a.
for (index = 0; index < n - 1; index++)
{ indexOfNextSmallest = the index of the smallest value among
a[index], a[index+1], . . . , a[n-1]
Interchange the values of a[index] and a[indexOfNextSmallest]
// Assertion: a[0] a[1] . . . a[index], and these are the smallest
// of the original array elements.
// The remaining array elements begin at a[index+1].
}
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 17
Selection Sort in Java
void selectionSort(int a[], int size)
{
int i, j, min;
for (i = 0; i < size - 1; i++)
{
min = i;
for (j = i+1; j < size; j++)
if (a[j] < a[min])
min = j;
swap(a[i], a[min]);
}
}
Copyright © 2006 Pearson Addison-Wesley. All rights reserved.
Sorting I 18