Draft:Monotonic Sort

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

UserpageCOI.svgThis user has made a public declaration indicating that they have a conflict of interest with regard to the following Wikipedia article(s):
Monotonic Sort
ClassSorting algorithm
Data structureArray
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity

In computer science, montonic sort is an efficient, general-purpose, stable non-comparative sorting algorithm which is based on the radix sort and sorts data by reducing the sorting problem to an integer sorting problem which can be solved in linear time complexity. Developed by Ido Dov Cohen in 2019. When implemented well, it can be about two or three faster than intro-sort/quick-sort.

Monotonic sort uses a non-ascending or non-descending monotonic function to determine the order of the elements. It sorts the monotonic function values assigned to the elements in the array via an LSD or MSD radix sort and applies the same permutations to the elements array, effectively sorting it as well.

Radix sort with negative values.png

When the monotonic values contain negative values, the LSD radix sort places them in the end of the array due to the two’s complement method, which sets the most significant bit of the monotonic function value to 1. After performing the LSD radix sort, the elements assigned with negative monotonic function values, should be shifted from the end of the array to its beginning, maintaining their internal order.

Assigning monotonic function values[edit]

Arrays of elements sorted with comparative sorting algorithm can be sorted with the monotonic sort by using the comparison key as the monotonic function value. When the comparison key is integer, using it as the monotonic function value is trivial.

In cases where the comparison key is a floating-point value, it can be converted to an integer value, still maintaining the monotonic property.

A simple way to make this conversion is:

  1. If the floating-point value is positive, get the binary representation of the floating-point value and use the integer number that corresponds to that binary representation.
  2. If the floating-point value is negative, get the binary representation of the additive inverse of floating-point value and use the additive inverse of the integer that corresponds to that binary representation.

However, these are not the only ways to determine which monotonic function values should be assigned to elements and it depends on the problem.

Direct approch[edit]

Conceptually, a monotonic sort works as follows:

  1. Assign a monotonic function value to each element in the array.
  2. Sort the monotonic function values array with an radix sort.
  3. Apply the permutations made on the array of the monotonic function values to the elements array as well.
  4. Move elements assigned with negative monotonic function values to the beginning of the array.

Direct implementation[edit]

Example pseudo code:

function ModifiedLsdRadixSort(elements,monotonicVals)
  indices = array of n integers;
  for i=0 to w
    [elements, monotonicVals] = SortByChunkIndex(i, elements, monotonicVals);
  end for
  return indices;
end function

function SortByChunkIndex(index, elements, monotonicVals)
  elementBuckets = array of R arrays of objects;
  valBuckets = array of R arrays of integers;
  for i = 0 to n
  c = chunk #index of element[i];
    elementBuckets[c].Add(element[i]);
    valBuckets[c].Add(monotonicVals[i]);
  end for
 
  for i = 0 to R
    elements.AddRange(elementBuckets[i]);
    monotonicVals.AddRange(valBuckets[i]);
  end for
  Return [elements, monotonicVals];
end function

function MonotonicSort(elements)
  monotonicValues = array of n integers;
  negativeCount = 0;
  for i = 0 to n
    monotonicValues[i] = elements[i].GetMonotonicHint();
    if (monotonicValues[i] < 0)
      negativeCount++;
    end if
  end for

  ModifiedLsdRadixSort(elements, monotonicValues);
  copy last negativeCount elements to temporary buffer.
  shift all elements <negativeCount> elements toward the end of the array.
  copy the elements in the temporary buffer to the start of the array.	
end function

An example[edit]

We’ll use the monotonic sort to solve the X + Y sorting problem in quadratic time.

Given an original unsorted list X: 13, 7, 42 and Original unsorted list Y: 12, -7.5.

The Cartesian product of the X and Y lists: (13, 12), (13,-7.5), (7, 12), (7, -7.5), (42, 12), (42, -7.5)

All we need to do is use the monotonic function:

X Y
13 12 25
13 -7.5 5.5
7 12 19
7 -7.5 -0.5
42 12 54
42 -7.5 34.5

Sorting the monotonic values with the radix sort and applying its permutations to the array of pairs (x,y) gives:

X Y
13 -7.5 5.5
7 12 19
13 12 25
42 -7.5 34.5
42 12 54
7 -7.5 -0.5

Shifting the elements assigned with negative monotonic function values to the beginning of the array gives:

X Y
7 -7.5 -0.5
13 -7.5 5.5
7 12 19
13 12 25
42 -7.5 34.5
42 12 54

and the array is sorted.

Parallel sorting[edit]

The original input array can be splitted to several non-overlapping partitions, where each partition contains elements assigned with monotonic function values from a certain range. Those partitions can be monotonically sorted in parallel and then reassembled as one array.

Monotonic sort partitioning.png

External links[edit]

  • [1] Implementation of Monotonic Sort in C#



Category:Articles with example C code Category:Sorting algorithms Category:Stable sorts