 Sorting Algorithms - Maple Help

Home : Support : Online Help : Math Apps : Computer Science : Sorting Algorithms

Comparison Sorting Algorithms

Sorting Algorithms Bubble Sort

The algorithm repeatedly steps through an array, swapping adjacent elements that are out of order. The algorithm keeps on modifying the array until there are no more swaps to be made. Bubble sort is rarely used in practice due to its performance time. Time Complexity Worst Case: O(${\mathrm{n}}^{2}$) Best Case: O(${\mathrm{n}}^{}$) Average Case: O(${\mathrm{n}}^{2}$) Space Complexity: O(1) auxiliary Implementation in Maple bubblesort := proc(arr)      local len, change, temp;      len := numelems(arr):      while(len >= 2) do              change := false:              len := len-1:              for i from 1 to len do                      if (arr[i] > arr[i+1]) then                              swap(arr, i, i+1);                              change := true:                     end if:             end do:             if (not change) then break end if:     end do: end proc: Cocktail Sort

The algorithm is a variation of bubble sort. It also repeatedly iterates through an array and swapping adjacent elements that are out of order, but instead of always starting from the left, once reaching the end of the array, cocktail sort turns around and operates on the array backwards. Similar to bubble sort, the algorithm stops when no more swaps are made during one iteration. Time Complexity Worst Case: O(${\mathrm{n}}^{2}$) Best Case: O(${\mathrm{n}}^{}$) Average Case: O(${\mathrm{n}}^{2}$) Space Complexity: O(1) auxiliary Implementation in Maple cocktailsort := proc(arr)         local left, right,swapped,i,j:         left, right := 1, numelems(arr)-1:         while(true) do                 swapped := false:                 for i from left to right do                         if arr[i] > arr[i+1] then:                                 swap(arr, i, i+1):                                 swapped := true:                                 right := i-1:                         end if:                 end do:                 if (not swapped) then break: end if:                 swapped := false:                 for j from right to left by -1 do                         if arr[j] > arr[j+1] then                                 swap(arr,j,j+1):                                 swapped := true:                                 left := j+1:                         end if:                 end do:                 if (not swapped) then break: end if:     end do: end proc: Gnome Sort

The algorithm is based on the story of a Garden Gnome sorting their flower pots with the following method:

 • The Gnome looks at the flower pot at his position and the one before; if the two pots are in the right order the gnome steps one pot forward, else the gnome swaps them and steps one pot backward.
 • When the gnome is standing at the beginning of the pots (index 1 of the array), the gnome steps forward; When the gnome stands at the end of the pots, the sorting is done. Time Complexity Worst Case: O(${\mathrm{n}}^{2}$) Best Case: O(${\mathrm{n}}^{}$) Average Case: O(${\mathrm{n}}^{2}$) Space Complexity: O(1) auxiliary Implementation in Maple gnomesort := proc(arr)         local len, i:         len := numelems(arr):         i := 2:         while (i <= len) do                 if (i=1 or arr[i] >= arr[i-1]) then                 i:= i+1:         else                 swap(arr,i,i-1):                 i:=i-1:         end if:     end do: end proc: Selection Sort

Selection sort is an inplace comparison sort. This algorithm divides the input array into two subarrays: sorted and unsorted, where the sorted array is built up from left to right starting at the front of the array—note that initially the sorted subarray is empty and the unsorted subarray is the entire input array. Each iteration the algorithm finds the smallest element in the unsorted subarray and swapping it with the leftmost unsorted element, thus increasing the length of the sorted array and decreasing the length of the unsorted subarray by one at the same time. Time Complexity Worst Case: O(${\mathrm{n}}^{2}$) Best Case: O(${\mathrm{n}}^{2}$) Average Case: O(${\mathrm{n}}^{2}$) Space Complexity: O(1) auxiliary Implementation in Maple selectionsort := proc(arr)     len := numelems(arr):     for i to len-1 do         j_min := i:         for j from i+1 to len do                 if arr[j] < arr[j_min] then                         j_min := j:                 end if:         end do:         if (not j_min = i) then                 temp := arr[i]:                 arr[i] := arr[j_min]:                 arr[j_min] := temp:         end if:     end do: end proc; Insertion Sort

This algorithm iterates up the array and builds a sorted subarray behind. At each step, insertion sort removes one element from the input array, locates the position it should be in the sorted subarray (so the subarray remains sorted) and inserts it there by shifting all larger elements right to make a empty spot. Time Complexity Worst Case: O(${\mathrm{n}}^{2}$) Best Case: O($\mathrm{n}$) Average Case: O(${\mathrm{n}}^{2}$) Space Complexity: O($\mathrm{n}$) total, O(1) auxiliary Implementation in Maple insertionsort := proc(arr)     len := numelems(arr):     for i from 2 to len do         val := arr[i]:         j := i-1:         while(j > 0 and arr[j] > val) do                 arr[j+1] := arr[j]:                 j:=j-1:         end do:         arr[j+1] := val:     end do: end proc; Quick Sort

Quick sort is a Divide and Conquer algorithm. At each step, it picks an element as the pivot and partitions the given array so that elements before the pivot are all smaller and elements behind are bigger than the pivot—notice that the two subarrays are not necessarily sorted. There are many different ways to pick the pivot, including

 • Picking the median
 • Picking a random element
 • Picking the first/last element

In the implementation and the demonstration animation, we always pick the last element as the pivot. Time Complexity Worst Case: O(${\mathrm{n}}^{2}$) Best Case: O() Average Case: O() Space Complexity:  O($\mathrm{n}$) auxiliary Implementation in Maple quicksort := proc(arr, low, high)         local pi:         if (low < high) then                 pi := qpart(arr,low,high):                 quicksort(arr, low, pi-1):                 quicksort(arr, pi+1, high):         end if: end proc: qpart := proc(arr, low, high)         local i,j,pivot;         pivot := arr[high]:         i := low-1:         for j from low to high-1 by 1 do                 if (arr[j] <= pivot) then                         i:=i+1:                         swap(arr, i, j):                 end if;         end do;         swap(arr, i+1, high):         return (i+1): end proc: quicksort(arr,1, numelems(arr)); Merge Sort

Merge Sort is a Divide and Conquer algorithm like Quick Sort. It divides the input array into two halves (division at the midpoint), merge sort (recursively calls itself on) the halves, and then uses a merge function to merge the two already sorted subarrays back together into one array. Time Complexity Worst Case: O() Best Case: O() Average Case: O() Space Complexity:  O($\mathrm{n}$) auxiliary Implementation in Maple merge := proc(arr, left, mid, right)         local i, j, k, n1, n2, L, R;         n1 := mid-left+1:         n2 := right-mid:         L := Array(1..n1):         R := Array(1..n2):         for i from 0 to n1-1 do                 L(i+1) :=arr(left+i):         end do:         for j from 0 to n2-1 do                 R(j+1) := arr(mid+j+1):         end do:         i := 1:         j := 1:         k := left:         while(i <= n1 and j <= n2) do                 if (L[i] <= R[j]) then                         arr[k] := L[i]:                         i:=i+1:                 else                         arr[k] := R[j]:                         j:=j+1:                 end if:                 k:=k+1:         end do:         while(i <= n1) do                 arr[k] := L[i]:                 i:=i+1:                 k:=k+1:         end do:         while(j <= n2) do                 arr[k] := R[j]:                 j:=j+1:                 k:=j+1:         end do: end proc: mergeSort := proc(arr, left, right)         local mid:         if (left < right) then                 mid := trunc((left + right)/2):                 mergeSort(arr, left, mid):                 mergeSort(arr, mid+1, right):                 merge(arr, left, mid, right):         end if: end proc: mergeSort(arr,1,numelems(arr)): Binary Insertion Sort

Binary insertion sort is a variation of insertion sort, where the algorithm uses binary search to locate the position to insert a selected element at each iteration. While in normal insertion at ith iteration, the same process would take i comparisons, (that is, the number is less than all elements in the subarray, and we find the position after doing comparisons with all of i elements), using binary search we can reduce the number to log(i). Note that this only reduces the number of comparisons, but does not bring down the overall time complexity since moving the number to a certain position still takes O(i). Time Complexity Worst Case: O(${\mathrm{n}}^{2}$) Best Case: O($\mathrm{n}$) Average Case: O(${\mathrm{n}}^{2}$) Space Complexity: O($\mathrm{n}$) total, O(1) auxiliary Implementation in Maple binarySearch := proc(arr, item, low, high)         local mid;         if (high <= low) then                 if (item > arr[low]) then return low+1;                 else return low;                 end if;         else                 mid := trunc((low+high)/2);                 if (item = arr[mid]) then return mid+1;                 elif (item > arr[mid]) then return binarySearch(arr, item, mid+1, high);                 else return binarySearch(arr, item, low, mid-1);                 end if;         end if; end proc; bsInsertionSort := proc(arr)         local n,i,j,k,loc,val;         n := numelems(arr):         for i from 2 to n do                 j := i-1:                 val := arr[i]:                 loc := binarySearch(arr,val,1,j);                 while(j >= loc) do                         arr[j+1] := arr[j]:                         j:=j-1:                 end do:                 arr[j+1] := val;         end do: end proc: bsInsertionSort(arr); Comb Sort

Comb Sort is an improved version of Bubble Sort; where bubble sort only compares adjacent elements, removing inversions one by one, Comb Sort can compare and invert elements separated by an extra value called gap, thus performing better when there are small values near the end of array The gap shrinks by a factor of 1.3 (gap * 10/13) each iteration until it reaches 1 (Comb Sort with a gap of 1 is equivalent to Bubble Sort). Note that the efficiency of comb sort is heavily impacted by the shrink factor and 1.3 is suggested as an ideal number by the authors of the original article. Time Complexity Worst Case: O(${\mathrm{n}}^{2}$) Best Case: O() Average Case: $\left(\genfrac{}{}{0}{}{{n}^{2}}{{2}^{p}}\right)$, where p is the number of increments Space Complexity: O(1) Implementation in Maple newGap := proc(gap)         local new;         new := trunc(gap*10/13);         if (new < 1) then return 1; end if;         return new; end proc; combsort := proc(arr, len)         local gap, swapped,i, temp;         swapped := true:         gap := len:         while ((not gap = 1) or swapped) do                 gap := newGap(gap):                 swapped := false:                 for i from 1 to len-gap by 1 do                         if (arr[i] > arr[i+gap]) then                                 temp := arr[i]:                                 arr[i] := arr[i+gap]:                                 arr[i+gap] := temp:                                 swapped:= true:                         end if:                 end do:         end do: end proc: combsort(arr, numelems(arr)); Shell Sort

Shell Sort can be seen as a variation/generalization of insertion sort. Similar to comb sort, it uses a gap variable to compare and sort pair of elements far apart from each other, making it easier to move some out-of-order elements into the correct position compared to a normal insertion sort. The gap also decreases with time but by a larger shrink factor (2.2 is suggested, in the implementation below it shrinks by 2);. Time Complexity Worst Case: O(${\mathrm{n}}^{2}$) Best Case: O() Average Case: O() Space Complexity: O($\mathrm{n}$) total, O(1) auxiliary Implementation in Maple shellsort := proc(arr)         local n, gap, i, val, j;         n := numelems(arr):         gap := trunc(n/2):         while (gap > 0) do                 for i from gap to n by 1 do                         val := arr[i];                         j := i;                         while (j > gap and arr[j-gap] > val) do                                 arr[j] := arr[j-gap];                                 j := j-gap;                         end do;                         arr[j] := val;                 end do;                 gap := trunc(gap/2);         end do; end proc; Pancake Sort

Pancake Sort is a sorting algorithm based on one operation: flip the elements between the start of the array and a certain position. The idea is similar to selection sort in the sense that at each step, the algorithm puts the maximum element in the unsorted subarray into correct position. At each iteration, a subarray is first flipped such that the maximum goes to the start of the array, the unsorted subarray is flipped so that the maximum goes to the end of the unsorted array, hence becoming the start of the sorted subarray. Time Complexity Best Case: O(${\mathrm{n}}^{2}$) Space Complexity: O(1) Implementation in Maple flip := proc(arr, i)         local start, temp, icopy;         temp, start, icopy := 0,1,i:         while (start < icopy) do                 temp := arr[start]:                 arr[start] := arr[icopy]:                 arr[icopy] := temp:                 start:=start+1:                 icopy:=icopy-1:         end do: end proc: findMax := proc(arr, i)         local Max, j:         Max := 1:         for j from 1 to i do                 if arr[j] > arr[Max] then Max := j: end if:         end do:         return Max: end proc: pancakesort := proc(arr)         local len,i,Max;         len := numelems(arr):         for i from len to 2 by -1 do                 Max := findMax(arr, i):                 if (not Max = i) then                         flip(arr, Max):                         flip(arr, i):                 end if:         end do: end proc: pancakesort(arr): Heap Sort

Heap sort is a sorting algorithm based on the binary heap structure. At each step it builds a max/min heap with the given unsorted array and puts the min/max element (which is at the root of the tree) in the correct position. It is similar to selection sort in the sense that both divide the array into a sorted subarray and an unsorted subarray and find the min/max in the unsorted one at each step. Time Complexity Worst Case: O() Best Case:  O() Average Case: O() Space Complexity: O(1) auxiliary Implementation in Maple heapify := proc(toSort, n, i)         local largest, l, r, holder:         largest := i:         l := 2*i:         r := 2*i+1:         if (l <= n and toSort[l] > toSort[largest]) then                 largest := l:         end if:         if (r <= n and toSort[r] > toSort[largest]) then                 largest := r:         end if:         if (not largest = i) then                 swap(toSort, i, largest);                 heapify(toSort, n, largest):         end if: end proc: heapsort := proc(arr)         local n,i:         n := numelems(arr):         for i from trunc(n/2) to 1 by -1 do                 heapify(arr, n, i):         end do:         for i from n to 2 by -1 do                 swap(arr, 1, i):                 heapify(arr, i-1, 1):         end do: end proc: heapsort(arr); Reference Source and Credit The time complexity data are from the Wikipedia pages and GeeksForGeeks pages of each of the sorting algorithms. Miscellaneous: Swap The implementation of the swap function to swap two elements in an array: swap := proc(arr, a, b)         local temp:         temp := arr[a]:         arr[a] := arr[b]:         arr[b] := temp: end proc:     More MathApps