Transcript CS 112 Introduction to Programming

CS 112 Introduction to
Programming
Sorting of an Array
Debayan Gupta
Computer Science Department
Yale University
308A Watson, Phone: 432-6400
Email: [email protected]
Sorting
2
Roadmap: Arrays
 Motivation, declaration, initialization, access
 Reference semantics: arrays as objects
 Example usage of arrays
 Tallying: array elements as counters
 Keeping state
 Manipulating arrays
 Sorting an array
3
Sorting an Array
 The process of arranging an array of
elements into some order, say increasing
order, is called sorting
 Many problems require sorting
 Google: display from highest ranked to lower
ranked
 Morse code
4
Sorting in CS
 Sorting is a classical topic in algorithm design
5
Sorting an Array
 How do we sort an array of numbers?
int[] numbers = {
3,
9,
6,
};
1,
2
6
Many Sorting Algorithms
 Insertion sort
 Selection sort
 Bubble sort
 Merge sort
 Quick sort
…
http://www.youtube.com/watch?v=INHF_5RIxTE
7
Insertion Sort
Basic idea: divide and conquer
(reduction)
 reduce
sorting n numbers to
• sort the first n-1 numbers
• insert the n-th number to the sorted first n-1
8
0
1
insertPos
=1
2
insertPos
=2
3
insertPos
=3
4
insertPos
=4
9
Insertion PseudoCode
// assume 0 to n – 1 already sorted
// now insert numbers[n]
// insertPos = n;
// repeat (number at insertPos-1 > to_be_inserted) {
//
shift larger values to the right
//
numbers[insertPos] <- numbers[insertPos-1];
//
insertPos--;
// numbers[insertPos] <- to_be_inserted;
10
0
1
2
3
// insertPos = n;
// repeat (number at insertPos-1 > to_be_inserted) {
//
shift larger values to the right
//
numbers[insertPos] <- numbers[insertPos-1];
//
insertPos--;
// numbers[insertPos] <- to_be_inserted;
11
Refinement: Insertion PseudoCode
// assume 0 to n – 1 already sorted
// now insert numbers[n]
// insertPos = n;
// repeat (insertPos > 0 &&
number at insertPos-1 > to_be_inserted) {
//
shift larger values to the right
//
numbers[insertPos] <- numbers[insertPos-1];
//
insertPos--;
// numbers[insertPos] <- to_be_inserted;
12
Insertion Sort Implementation
public static void sort (int[] numbers) {
for (int n = 1; n < numbers.length; index++) {
int key = numbers[n];
int insertPos = n;
// invariant: the elements from 0 to index -1
// are already sorted. Insert the element at
// index to this sorted sublist
while (insertPos > 0 && numbers[insertPos-1] > key) {
// shift larger values to the right
numbers[insertPos] = numbers[insertPos-1];
insertPos--;
}
numbers[insertPos] = key;
} // end of for
} // end of sort
13
14
15
16
17
18
19
Analysis of Insertion Sort
 What is algorithm complexity in the worst
case?
int[] numbers = {
3,
9,
6,
};
1,
2
20
Sorting Arrays: Bubble Sort
 Scan the array multiple times
 during each scan, if elements at i and i+1 are
out of order, we swap them
 This sorting approach is called bubble
 http://en.wikipedia.org/wiki/Bubble_sort
sort
 Remaining question: when do we stop (the
termination condition)?
21
Sorting: Bubble Sort
public static void sort (int[] numbers)
{
boolean outOfOrder = false;
do {
outOfOrder = false;
// one scan
for (int i = 0; i < numbers.length-1; i++) {
if (numbers[i] > numbers[i+1]) { // out of order
// swap
int x = numbers[i];
numbers[i] = numbers[i+1];
numbers[i+1] = x;
outOfOrder = true;
} // end of if
} // end of for
} while (outOfOrder);
} // end of sort
22
Selection Sort
 For the i-th iteration, we select the i-th
smallest element and put it in its final place
in the sort list
23
Selection Sort
 The approach of Selection Sort:
 select one value and put it in its final place in
the sort list
 repeat for all other values
 In more detail:
 find the smallest value in the list
 switch it with the value in the first position
 find the next smallest value in the list
 switch it with the value in the second position
 repeat until all values are placed
24
Selection Sort
 An example:
original:
smallest is
smallest is
smallest is
smallest is
1:
2:
3:
6:
3
1
1
1
1
9
9
2
2
2
6
6
6
3
3
1
3
3
6
6
2
2
9
9
9
25
Sorting: Selection Sort
public static void sort (int[] numbers)
{
int min, temp;
for (int i = 0; i < numbers.length-1; i++)
{
// identify the i-th smallest element
min = i;
for (int scan = i+1; scan < numbers.length; scan++)
if (numbers[scan] < numbers[min])
min = scan;
// swap the i-th smallest element with that at i
temp = numbers[min];
numbers[min] = numbers[i];
numbers[i] = temp;
} // end of for
} // end of sort
26
Analysis of Selection Sort
 What is algorithm complexity in the worst
case?
int[] numbers = {
3,
9,
6,
};
1,
2
27
Roadmap
 Both insertion and selection have
complexity of O(N2)
 Q: What is the best that one can do and
can we achieve it?
28
Sorting: Merge Sort
 Split list into two parts
 Sort them separately
 Combine the two sorted lists (Merge!)
 Divide and Conquer!
29
Sorting
public void sort(int[] values) {
numbers = values; // numbers has been previously declared
mergesort(0, number - 1);
}
private void mergesort(int low, int high) {
// check if low is smaller then high, if not then the array is sorted
if (low < high) {
// Get the index of the element which is in the middle
int middle = low + (high - low) / 2;
mergesort(low, middle); // Sort the left side of the array
mergesort(middle + 1, high); // Sort the right side of the array
merge(low, middle, high); // Combine them both
}
}
30
Merging
private void merge(int low, int middle, int high) {
// Copy both parts into the helper array
for (int i = low; i <= high; i++) {
helper[i] = numbers[i];
}
int i = low, j = middle + 1, k = low;
// Copy the smallest values from either side
while (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
numbers[k] = helper[i]; i++;
} else {
numbers[k] = helper[j]; j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= middle) {
numbers[k] = helper[i];
k++; i++;
}
}
31
Merging
3
4
6
7
1
5
8
2
32
Sorting: Quick Sort
 Select a random element
 Compare it to every other element in your
list to find out its rank or position
 You have now split the list into two smaller
lists (if a > x and x > b, then we know that
a > b – we don’t need to compare!)
33
Quicksort
private void quicksort(int low, int high) {
int i = low, j = high;
// Get the pivot element from the middle of the list
int pivot = numbers[low + (high-low)/2];
// Divide into two lists
while (i <= j) {
// If the current value from
// element then get the next
while (numbers[i] < pivot) {
i++;
}
// If the current value from
// element then get the next
while (numbers[j] > pivot) {
j--;
}
the left list is smaller then the pivot
element from the left list
the right list is larger then the pivot
element from the right list
34
Quicksort .. Contd.
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// Recursion
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}
private void
int temp =
numbers[i]
numbers[j]
}
exchange(int i, int j) {
numbers[i];
= numbers[j];
= temp;
35
What’s the best we can do?
 N2?
 N log N
 Why?
36
N log N
 N! possible outcomes
 If we compare two numbers, there are only
2 possible combinations that we can get
 So, if we have x steps, then we can produce
a total of 2x combinations
 To get 2x > N!, we need x > N log N
37
Questions?
38