Sorting Algorithm

bubbleSort

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
     n = n - 1
   until not swapped
end procedure

insertionSort

for i = 1 to length(A) - 1
    x = A[i]
    j = i
    while j > 0 and A[j-1] > x
        A[j] = A[j-1]
        j = j - 1
    end while
    A[j] = x
 end for

mergeSort

TopDownMergeSort(A[], B[], n)
{
    TopDownSplitMerge(A, 0, n, B);
}
 
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set)
TopDownSplitMerge(A[], iBegin, iEnd, B[])
{
    if(iEnd - iBegin < 2)                       // if run size == 1
        return;                                 //   consider it sorted
    // recursively split runs into two halves until run size == 1,
    // then merge them and return back up the call chain
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // split / merge left  half
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // split / merge right half
    TopDownMerge(A, iBegin, iMiddle, iEnd, B);  // merge the two half runs
    CopyArray(B, iBegin, iEnd, A);              // copy the merged runs back to A
}
 
//  left half is A[iBegin :iMiddle-1]
// right half is A[iMiddle:iEnd-1   ]
TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
    i0 = iBegin, i1 = iMiddle;
 
    // While there are elements in the left or right runs
    for (j = iBegin; j < iEnd; j++) {
        // If left run head exists and is <= existing right run head.
        if (i0 < iMiddle && (i1 >= iEnd || A[i0] <= A[i1]))
            B[j] = A[i0];
            i0 = i0 + 1;
        else
            B[j] = A[i1];
            i1 = i1 + 1;    
    } 
}
 
CopyArray(B[], iBegin, iEnd, A[])
{
    for(k = iBegin; k < iEnd; k++)
        A[k] = B[k];
}

quickSort

partition(Array, start, end)
     pivot = Array[end]
     index = start
     current = start
     while (current < end )
         if Array[current] <= pivot
              swap Array[index] and Array[current]
              index = index + 1
        current = current + 1
     swap Array[index] and Array[end]  // Move pivot to its final place
     return index
	 
quicksort(Array, start, end)
    if start < end
        index = partition(Array, start, end)
        quicksort(Array, start, index-1)
        quicksort(Array, index+1, end)
	
	
testlist1 = [1, 5, 6, 4, 9, 8, 2, 7, 3, 0]
def quicksort(listToSort, lowerIndex, highIndex):
    if ((highIndex - lowerIndex) > 0):
        p = partition(listToSort, lowerIndex, highIndex)
        quicksort(listToSort,lowerIndex,p-1)
        quicksort(listToSort,p+1,highIndex)
def partition(listToSort, lowerIndex, highIndex):
    divider = lowerIndex
    pivot = highIndex
    for i in range(lowerIndex, highIndex):
        if (listToSort[i] < listToSort[pivot]):
            listToSort[i], listToSort[divider] = listToSort[divider], listToSort[i]
            divider += 1
    listToSort[pivot], listToSort[divider] = listToSort[divider], listToSort[pivot]
    return divider
print testlist1
quicksort (testlist1,0,9)
print testlist1

selectionSort

/* a[0] to a[n-1] is the array to sort */
int i,j;
int iMin;
 
/* advance the position through the entire array */
/*   (could do j < n-1 because single element is also min element) */
for (j = 0; j < n-1; j++) {
    /* find the min element in the unsorted a[j .. n-1] */
    /* assume the min is the first element */
    iMin = j;
    /* test against elements after j to find the smallest */
    for ( i = j+1; i < n; i++) {
        /* if this element is less, then it is the new minimum */  
        if (a[i] < a[iMin]) {
            /* found new minimum; remember its index */
            iMin = i;
        }
    }
    if(iMin != j) {
        swap(a[j], a[iMin]);
    }
}