Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

Selection Sort

No description
by

Samantha Lopez

on 27 March 2014

Report abuse

Transcript of Selection Sort

Selection Sort
Selection Sort in 3 sentences or less...
Known for its simplicity, the selection sort algorithm starts by finding the minimum value in the array and moving it to the first position. This step is then repeated for the second lowest value, then the third, and so on until the entire array is sorted.
Selection Short Image

There are two parts in the array:

-Unsorted zone (blue)

-Sorted zone (red)

In a loop, the highest element from the unsorted zone is selected (hence the name Selection Sort) and placed at the end of the unsorted zone. After that, the sorted zone expands to cover the recently moved element, and the unsorted zone shrinks to lose that element. Eventually, the sorted zone becomes the entire array, and the unsorted zone disappears. The array is then considered to be sorted.

This picture is showing how the program will sort the array in an ascending order, using selection sort. Since 7 is the first element on the list, it will be seen as the current minimum. The program will then simply compare 7 to the second number, which is 4, and then replace the current minimum with 4 considering it is less than 7. It will then compare it to the third number, fourth number, and so on, and then sort. After figuring out that 1 is ultimately the lowest number, it is swapped with the FIRST current minimum, 7, and then "turns red" to be seen as a part of the sorted zone. The sorting continues.
A few websites I found useful throughout this project...
http://courses.cs.vt.edu/~csonline/Algorithms/Lessons/SelectionSort/index.html
http://www.chegg.com/homework-help/definitions/selection-sort-3
http://mathbits.com/MathBits/Java/arrays/SelectionSort.htm
By Samantha Lopez
This YouTube video is a good source to describe selection sort because he visualizes the process using cups, making it a lot easier to understand. After he goes through the entire process of sorting, he then goes further to decode and explain the selection sort code as well.
This YouTube video is another good source to describe selection sort because he incorporates a visual representation of the code by using cards, and also draws out the arrays while explaining it verbally. At the end he decodes the selection sort code line by line.
Though this YouTube video has no explanation, it is a great visual representation of the code because it is a fun an interesting way to understand what is happening. In the video, each person is a number in a location. a[o] is compared with a[1] by dancing with them, and this "dancing" is basically the code checking to see which number is less than the other. Each number dances with the other until everyone is in ascending order.
He has a bit of an annoying voice...
Each website was useful because they included in depth descriptions while also using diagrams to help visualize what they were explaining.
Sources used throughout this presentation include:
http://www.chegg.com/homework-help/definitions/selection-sort-3

http://mathbits.com/MathBits/Java/arrays/SelectionSort.htm

and https://www.youtube.com/ for its various videos throughout the Prezi

http://courses.cs.vt.edu/~csonline/Algorithms/Lessons/SelectionSort/index.html
Worst and Best Case Scenario...
Decoding Selection Sort Line by Line...
Selection Sort:
public void selectionSort (double [] arr, int n)
{
while (n > 1)
{
int maxPos = 0;
for(int k=1;k<n;k++)
if(arr[k]>arr[maxPos])
maxPos=k;
double temp=arr[maxPos];
arr[maxPos]=arr[n-1];
arr[n-1]=temp;
n--;
}
}
for(int k=1;k<n;k++)
if(arr[k]>arr[maxPos])
maxPos=k;
//k is assigned 1, and goes through loop
//until k is greater than n. If k is
//greater than the maxPos, then the max
//Pos is assigned to k.

double temp=arr[maxPos];
arr[maxPos]=arr[n-1];
arr[n-1]=temp;
n--;
}//this code simply swaps the newly
}//found maxPos with the old, using a
//temp
public void selectionSort (double [] arr, int n)
{
while (n > 1)
{
int maxPos = 0;
//sub 0 is set as the max position

Selection sort has an O(n^2) complexity, making it inefficient on large lists and ideal for smaller lists, and generally performs worse than the similar insertion sort. Among simple average-case O(n^2) algorithms, selection sort almost always outperforms bubble sort, but is generally outperformed by insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

Worst and best case scenario is O(n^2). Looking at the math, the time complexity is

T(n) = (n-1) + (n-2) + ... + 2 + 1

And this is stated to be equal to O(n^2) because there are two for-loops, the inner one being n and the outer being n, in sum making it n^2.
MORE SAMPLE CODE-
public static void selectionSort(int[] numbers) {

// Iterate over each number starting from the last one and working backwards
for (int i = numbers.length - 1; i >=1; i--)
{
// Always set the max pos to 0 at the start of each iteration
int maxPos = 0;

// Start at pos 1 and iterate up to the second last number
for (int j = 1; j < i; j++)
{
// If the number in the current max is larger than the one in maxPos,
// set a new maxPos
if (numbers[j] > numbers[maxPos])
{
maxPos = j;
}
}

// We now have the position of the maximum number. If the maximum number is greater than the number in the current max swap them
if (numbers[maxPos] > numbers[i])
{
int temp = numbers[i];
numbers[i] = numbers[maxPos];
numbers[maxPos] = temp;
}
}
}
However, there is a "stop early" strategy that not many people know of:
For each sweep:
set "sorted_so_far" to "true".
As you sweep:
If the item you're looking at is more than max_so_far:
update max_so_far and the index pointing to it.
If the item you're looking at is less than max_so_far:
set "sorted_so_far" to false.
At the end of any sweep, if "sorted_so_far" is still true, then the array is sorted and you can stop early.
----