Data Structures

Bubble, insertion or selection? Samples of students' work

A: Insertion sort
- Create a new empty list.
- Each time pick the smallest number from the existing list, append to the new list, remove it from the old list.
- Repeatthe 2nd step until the old list becomes empty.
B: Insertion sort
For the deck of cards example, draw one card at a time. Assume you are sorting smallest to largest. If the next crad you draw is higher than the previous card, put it at the end; if it is lower, put it in the beginning. Each time you draw a card, compare it with what you have already sorted and insert it into the correct spot.
C: Selection sort
Find the smallest and put it at the front, then find the second smallest and put it in the second spot. Repeat until the list is sorted.
D: Selection sort
Selection sort works by finding the minimum of a list, then swapping that with the front element. You then find the minimum of the list starting at the second element, and swap that with the second element. This continues until the end of the list is reached.

Students' plots

Easy to implement (but not the most efficient) sorting algorithms

Insertion sort: insertion sort iterates through a list of items, such that each item is inserted in turn at the correct postion within the sorted, left portion of the list composed of processed items.
```
InsertionSort(A):
    for(i=1; i < A.length; i++)
       j=i
       while(j>0 and A[j]<A[j-1])
	    swap(A[j], A[j-1]) 
	    j--
```
Selection sort algorithm. The selection sort algorithm divides the list into two sublists: one sorted (empty in the beginning) and one unsorted (the entire list in the beginning). In every iteration, the algorithm finds the minimum item (considering ascending order) from the unsorted sublist and swaps the minimum with the first item in the unsorted sublist (so the size of unsorted sublist reduces by one in each iteration). The interation stops when the unsorted sublist becomes empty.
```
SelectionSort(A):
    for(i = 0; i < A.length-1; i ++) 
        lowest = i
        for(j=i+1; j < A.length; j ++) 
	    if(A[j] < A[lowest]) 
		lowest = j
        if(lowest != i) 
	    swap(A[i], A[lowest])
```

Bubble sort repeatedly steps through the list of items to be sorted, compare each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed

//bubble up version
//A is the array of records to be sorted
BubbleSort(A):
    for(i=0; i < A.length-1; i++)
        swapped = false
        for(j=A.length-1; j > i; j--)  
	     if(A[j] < A[j-1])  
		swap(A[j], A[j-1])
		swapped = true
        if swapped == false
	     break

//sink down version
BubbleSort(A):
    for(i=0; i < A.length-1; i++)
        swapped = false
        for(j=0; j < A.length-1-i; j++)  
	    if(A[j] > A[j+1]) 
		swap(A[j], A[j+1])
		swapped = true
        if swapped == false
	    break

Bubble, insertion or selection? Samples of students' work

Students' plots

Easy to implement (but not the most efficient) sorting algorithms

All three are $\Theta(n^2)$ sorting algorithms