Sorting Algorithms - Maple Help

All Products Maple MapleSim

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( $n^{2}$ ) Best Case: O( $n^{}$ ) Average Case: O( $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( $n^{2}$ ) Best Case: O( $n^{}$ ) Average Case: O( $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( $n^{2}$ ) Best Case: O( $n^{}$ ) Average Case: O( $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( $n^{2}$ ) Best Case: O( $n^{2}$ ) Average Case: O( $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( $n^{2}$ )

Best Case: O( $n$ )

Average Case: O( $n^{2}$ )

Space Complexity: O( $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( $n^{2}$ )

Best Case: O( $n \log (n)$ )

Average Case: O( $n \log (n)$ )

Space Complexity: O( $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( $n \log (n)$ ) Best Case: O( $n \log (n)$ ) Average Case: O( $n \log (n)$ ) Space Complexity: O( $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( $n^{2}$ )

Best Case: O( $n$ )

Average Case: O( $n^{2}$ )

Space Complexity: O( $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( $n^{2}$ ) Best Case: O( $n \log (n)$ ) Average Case: $(\binom{n^{2}}{2^{p}})$ , 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( $n^{2}$ )

Best Case: O( $n \log (n)$ )

Average Case: O( $n \log (n)$ )

Space Complexity: O( $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( $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( $n \log (n)$ )

Best Case: O( $n \log (n)$ )

Average Case: O( $n \log (n)$ )

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

MathApps/ComputerScience

Download Help Document

Maple

Maple Add-Ons

MapleSim

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim

Maple

Powerful math software that is easy to use

Maple Add-Ons

MapleSim

Advanced System Level Modeling

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim