Sorting Algorithms

Probably the most frequent operation computers do.

Sorting

• Sorting is the process of arranging a group of n elements into a defined order based on particular criteria
• Many sorting algorithms have been designed
• Sequential sorts require approximately O(n²) comparisons
• Logarithmic sorts typically require O(n*lg n) comparisons
• The elements must be Comparable, that is,�We must be able to compare one element to another

18 - 2

Definition of Sorting

• Given a collection of items that can be compared
• You want to sort that data (increasing or decreasing order).

Example of sorting client

public class SortPhoneList

{

public static void main(String[] args)

{

Contact[] friends = new Contact[7];

​

friends[0] = new Contact("John", "Smith", "610-555-7384");

friends[1] = new Contact("Sarah", "Barnes", "215-555-3827");

friends[2] = new Contact("Mark", "Riley", "733-555-2969");

friends[3] = new Contact("Laura", "Getz", "663-555-3984");

friends[4] = new Contact("Larry", "Smith", "464-555-3489");

friends[5] = new Contact("Frank", "Phelps", "322-555-2284");

friends[6] = new Contact("Marsha", "Grant", "243-555-2837");

​

Sorting.selectionSort(friends);

​

for (int i = 0; i < friends.length; i++)

System.out.println(friends[i]);

}

}

18 - 4

Example of data to sort

/**

* Contact represents a phone contact.

* @author Java Foundations

*/

public class Contact implements Comparable<Contact> {

private String firstName, lastName, phone;

/**

* Sets up this contact with the specified information.

*

* @param first a string representation of a first name

* @param last a string representation of a last name

* @param telephone a string representation of a phone number

*/

public Contact(String first, String last, String telephone)

{

firstName = first;

lastName = last;

phone = telephone;

}

​

18 - 5

Example on value to sort on

​

/**

* Uses both last and first names to determine lexical ordering.

*

* @param other the contact to be compared to this contact

* @return the integer result of the comparison

*/

public int compareTo(Contact other)

{

int result;

​

if (lastName.equals(other.lastName))

result = firstName.compareTo(other.firstName);

else

result = lastName.compareTo(other.lastName);

​

return result;

}

}

​

18 - 6

Selection Sort

Select the next element to place in its proper position

Sorting using selectionSort

SelectionSort orders values by repeatedly �putting a particular value into its final sorted position

The algorithm:

• find the smallest value in the dataset
• switch it with the value in the first position
• find the next smallest value in the dataset
• switch it with the value in the second position
• repeat until all values are in their sorted positions

​

​

Visualization https://visualgo.net/sorting

Practice!

• Sort the following numbers using selection sort (make sure to show all intermediary steps):
• Together: 8, 10, -2, 6, -7, 0
• In groups: 9, 15, 3, 12, 7, 10

​

• Implement selection sort in Java (on the white boards)

​

• What’s its time-complexity?

selectionSort( )

public static void selectionSort(Comparable[] data) {

int min;

for(int index = 0; index < data.length – 1; index++){

min = index;

for(int scan = index+1; scan < data.length; scan++)

if (data[scan].compareTo(data[min]) < 0)

min = scan;

swap(data, min, index);

}

} // What is its running time?

Insertion Sort

Given a partially sorted set of elements,�Insert the next element in its proper position

Sorting using insertionSort

InsertionSort orders a list of values by repeatedly �inserting a particular value into a sorted subset of the list

The algorithm:

• consider the first item to be a sorted sublist of length 1
• insert the second item in the sorted sublist, �shifting the first item if needed
• insert the third item into the sorted sublist, �shifting the other items as needed
• repeat until all values inserted into their proper positions

Sorting using insertionSort

InsertionSort orders a list of values by repeatedly �inserting a particular value into a sorted subset of the list

The algorithm:

• consider the first item to be a sorted sublist of length 1
• insert the second item in the sorted sublist, �shifting the first item if needed
• insert the third item into the sorted sublist, �shifting the other items as needed
• repeat until all values inserted into their proper positions

(3) is sorted sublist. Consider 9.

Shift nothing, insert 9. (3, 9) are sorted. Consider 6.

Shift 9, insert 6. (3, 6, 9) are sorted. Consider 1.

Shift 3, 6, 9, insert 1. (1, 3, 6, 9) sorted. Consider 2.

Shift 3, 6, 9, insert 2. (1, 2, 3, 6, 9) sorted.

Practice!

• Sort the following numbers using insertion sort (make sure to show all intermediary steps):
• Together: 8, 10, -2, 6, -7, 0
• In groups: 9, 15, 3, 12, 7, 10

​

• Implement insertion sort in Java (on the white boards)

​

• What’s its time-complexity?

insertionSort( )

public static void insertionSort(Comparable[] data) {

for(int index = 1; index < data.length; index++) {

Comparable key = data[index];

int position = index;

while (position > 0 && data[position-1].compareTo(key) > 0){

// shift larger values to the right

data[position] = data[position-1];

position--;

}

data[position] = key;

}

} //What is its running time?

Merge Sort

Given two partially sorted sets of elements,�Merge them into a new sorted set

Sorting using mergeSort

Merge sort orders a list of values by recursively �dividing the list in half until each sublist has one element, then recombining (merging) the sublists

The algorithm:

Split: Divide the list into two equal parts—left and right. If the list has odd length, one half will have an extra element.

Sort: Recursively use merge-sort to sort the two lists. Note that by definition, a list of one element is sorted (base case).�

Merge: Merge the two sorted parts into one sorted list

Merge sort – Split

Merge sort – Sort & Merge

mergeSort( )

public static void mergeSort(Comparable[] data,

int min, int max){

if (min < max) {

int mid = (min + max) / 2;

mergeSort(data, min, mid);

mergeSort(data, mid+1, max);

merge(data, min, mid, max);

}

}

Note: This is NOT the exact code executing in the visualization of the previous slide

merge (1/2)

public static void merge(Comparable[] data,

int first, int mid, int last) {

Comparable[] temp = new Comparable[data.length];

int first1 = first, last1 = mid; //ends of 1st subarray

int first2 = mid+1, last2 = last; //ends of 2nd subarray

int index = first1; // destination in temp array

// copy smaller item from each subarray into temp � // until one of the subarrays is exhausted

while(first1 <= last1 && first2 <= last2){

if(data[first1].compareTo(data[first2]) < 0) {

temp[index] = data[first1];

first1++;

} else {

temp[index] = data[first2];

first2++;

}

index++;

}

merge (2/2)

//copy remaining elements from first subarray, if any

while (first1 <= last1){

temp[index] = data[first1];

first1++;

index++;

}

​

//copy remaining elements from second subarray, if any

while (first2 <= last2){

temp[index] = data[first2];

first2++;

index++;

}

//copy merged data into original array

for(index = first; index <= last; index++){

data[index] = temp[index];

}

}

​

Practice!

• Sort the following numbers using merge sort (make sure to show all intermediary steps):
• In groups: 8, 10, -2, 6, -7, 0
• In groups: 9, 15, 3, 12, 7, 10

​

Note: for this exercise, do this by carefully stepping through the merge sort code.

Sort Efficiencies

1. Which algorithm would you rather use?
1. Look at both space and memory!
2. HW7: merge sorting a link list with O(1) additional space!
2. So for merge sort, where did the log n come from?

Sort Efficiencies

Bonus: Quick Sort

Select an element at random and �place it in its proper location, with �smaller elements to its left and �larger elements to its right

Sorting using quickSort

• Quick sort orders a list of values by partitioning the list around some element (the pivot), then sorting each partition
• The algorithm
1. choose one element in the list to be the pivot value
2. organize the elements so that �all elements less than the pivot value are to the left and�all elements greater than the pivot value are to the right
3. apply quickSort (recursively) to each partition
• Nice if the pivot value divides the list roughly in half
• Better if the pivot value divides the list as close to "in half" as possible
• Worse if the two halves are unbalanced.
• Quick sort has two methods
• quickSort – performs recursive algorithm
• partition – rearranges elements into two partitions

Example of Quicksort

Input array

First element becomes the pivot

Pivot is placed to its final position during partition

Two sub-arrays are sorted recursively

First elements become pivots

Pivots are placed in final position

Four sub-arrays are sorted recursively…

quicksort( )

public static void quickSort� (Comparable[] data, int min, int max) {

int pivot;

if(min < max){

pivot = partition(data, min, max); //make partitions

quickSort(data, min, pivot-1); //sort left part

quickSort(data, pivot+1, max); //sort right part

}

}

Example of partition

1. Input array�
2. First element becomes the pivot�
3. Elements are exchanged to�separate smaller from larger
4. Pivot is exchanged to its final position

Partition finished. After that, the two sub-arrays are sorted recursively

partition

private static int partition(Compareable[] data, int min, int max) {

Comparable pivotValue = data[min];

int left = min; int right = max;

​

while(left < right){

//search for an element that is > pivotValue

while(data[left].compareTo(pivotValue) <= 0 && left < right)

left++;

//search for an element that is < pivotValue

while(data[right].compareTo(pivotValue) > 0)

right--;

if(left < right)

swap(data, left, right); // put them in the other part

}

//move the pivotElement to its final position

swap(data, min, right);

return right; // caller needs to know location of split

}

Practice!

• Sort the following numbers using quick sort (make sure to show all intermediary steps):
• 9, 15, 3, 12, 7, 10

Differences; Pros and Cons

• QuickSort does the work on the way “down,” before the recursion
• doesn’t require extra storage
• has lower overhead; no extra copying stuff around
• QuickSort is probably O(n lg n)
• Used a lot with in-memory sorting.
• Both might switch to InsertionSort for “small” problems, to avoid lots of recursion on small arrays, say less than 10.

​

• MergeSort does the work on the way “up,” returning from recursion
• needs extra array
• works really well on linked lists: no copying needed.
• MergeSort is guaranteed O(n lg n);
• The merge() operation is O(n); if sets are represented as sorted sequences, merge() can be used to implement union() and intersection()
• Used a lot with databases and file-based sorting

​