2C03 Sort Pseudocode

Pseudocode.md

#Pseudocode for Sorting Algorithms In the style of Wikipedia, but for every sorting algorithm we've learned.

Insertion Sort
Shell Sort
Selection Sort
Merge Sort
Quicksort
Heapsort

##Insertion Sort

A = Array to sort
for i = 1; i < length(A) - 1; i++	//Iterate across elements
    j = i
    while j > 0 and A[j-1] > A[j]	//Move element left until it is sorted
        swap A[j] and A[j-1]
        j = j - 1
    endwhile
endfor

##Shell Sort

A = Array to sort
h = 1;
while h < length(A)/3 
	h = 3*h + 1; 
endwhile

while h >= 1 
    //Insertion sort the shell
    for i = h; i < length(A); i++	
        for j = i; j >= h and A[j] < A[j-h]; j -= h
            swap A[j] and A[j-h]
        endfor
    endfor
    //End insertion sort

    h = h/3;	//Divide shell size by 3 each time
endwhile

##Selection Sort

A = Array to sort
for i = 0; i < length(A); i++
    min = i;
    for int j = i+1; j < N; j++
        if A[j] < A[min]
        	min = j;
        endif
    endfor

    swap A[i] and A[min]
endfor

##Merge Sort

//Merge
A = Array to merge
B = Copy of A
lo = Low index of left subarray
mid = High index of left subarray and low index of right subarray
hi = High index of right subarray

i = lo
j = mid+1
for int k = lo; k <= hi; k++ 
    if i > mid  	 //If we have exhausted the left array
        A[k] = B[j]
        j=j+1
    else if j > hi    	//If we have exhausted the right array
        A[k] = B[i]
        i=i+1
    else if B[j] < B[i]  
        A[k] = B[j]	//Add first of right
        j=j+1
    else
        A[k] = B[i	//Add first of left
        i=i+1
    endif
endfor

//Sort
A = Array to sort
B = Auxiliary Array
lo = Low index of subarray
hi = High index of subarray

if hi <= lo
    return
endif

mid = lo + (hi - lo) / 2;
sort(A, B, lo, mid);        //Recursive call to sort left
sort(A, B, mid + 1, hi);    //Recursive call to sort right
merge(A, B, lo, mid, hi);   //Merge both subarrays

##Quicksort

//Sort
A = Array to be sorted
lo = Lower index of subarray
hi = Higher index of subarray
if hi <= lo
    return
endif

j = partition(A, lo, hi); //Partition
sort(A, lo, j-1);	  //Recursive call to sort left subarray
sort(A, j+1, hi);	  //Recursive call to sort right subarray

//Partition
A = Array to be partioned
lo = Lower bound for partition index
hi = Upper bound for partition index

i = lo;
j = hi + 1;
v = A[lo];	//Current element
while true
    //Start at lo, move left until element to swap is found
    while A[++i] < v
        if i == hi  //Stop at high index
            break
        endif

    //Start at hi, move right until element to swap is found
    while v < A[--j]
        if j == lo 
            break;      // Redundant since A[lo] acts as sentinel
        endif
    endwhile

    
    if i >= j   //Check if pointers cross
        break
    endif

    swap A[i] and A[j] 
endwhile

// Put partitioning item v at A[j]
swap A[lo] and A[j]

return j;

##Heapsort

//Sort
A = Array to be sorted
N = length(A)
for k = N/2; k >= 1; k--  //Sink everything but the root (heapify)
    sink A[k] //Sink the element to restore heap invariant
endfor

while N > 1
    swap A[1] and A[N] //Swap last element with root
    N = N-1
    sink A[1] //Sink the root
endwhile

//Sink
A = Array to be sorted
k = Index of node to sink
while 2*k <= N
    j = 2*k   			//Move to left child
    if j < N and A[j] < A[j+1]  //If left child is not last node and is less than right child...
    	j=j+1 			//Move to right child
    endif
    if not A[k] < A[j		//Break if parent is greater or equal than largest child
    	break
    endif
    swap A[k] and A[j] 		//Swap the parent with the chosen child
    k = j
endwhile