Multi-interval quicksort algorithm for complex objects
First Claim
1. A computer implemented method for sorting an array of elements, the method comprising the steps of:
- receiving a sort request from a requesting entity that includes sorting criteria for the array of elements, wherein the elements are stored in memory that is accessible by a processor, and wherein the elements consist of references to complex objects stored in memory;
operating the processor to run a sorting module to sort the elements from a first order to a second order differing from the first order to form a sorted array;
wherein the elements are sorted dependent on the sorting criteria, the sorting criteria including a characteristic of the complex objects, and the sorting of the elements being performed by accessing the complex objects in the memory and by comparing the characteristics of corresponding ones of the complex objects stored in the memory; and
storing the sorted array of elements in a memory,wherein the forming of the sorted array by the sorting module includes the steps of;
selecting at least two of the elements as pivot elements; and
sorting the elements in the array using the at least two pivot elements as initially sorted elements of the second order defining the sorted array, andwherein the sorting step comprises;
comparing the pivot elements with each other to determine a sort order for the pivot elements relative to each other;
creating a plurality of empty sub-arrays that each correspond to a sorting interval relative to the pivot elements, such that the number of sub-arrays created is one more than the number of pivots;
determining the relative sorting position of each of the non-pivot elements in the array with respect to the pivot elements; and
dependent upon the determining, inserting each non-pivot element of the array into a corresponding one of the plurality of sub-arrays.
1 Assignment
0 Petitions
Accused Products
Abstract
Systems and methods (“utility”) for sorting a plurality of complex objects are provided herein. The utility may include a sorting algorithm that sorts references to the complex objects, rather than the complex objects themselves, such that the need to copy and swap complex objects in their locations in memory is reduced. Further, the sorting algorithm may utilize a recursive divide and conquer process, using multiple pivot elements at each sorting level. For example, the sorting algorithm is based on a modified Quicksort algorithm that uses multiple pivot elements at each level to sort an array of references that point to complex objects.
14 Citations
22 Claims
-
1. A computer implemented method for sorting an array of elements, the method comprising the steps of:
-
receiving a sort request from a requesting entity that includes sorting criteria for the array of elements, wherein the elements are stored in memory that is accessible by a processor, and wherein the elements consist of references to complex objects stored in memory; operating the processor to run a sorting module to sort the elements from a first order to a second order differing from the first order to form a sorted array; wherein the elements are sorted dependent on the sorting criteria, the sorting criteria including a characteristic of the complex objects, and the sorting of the elements being performed by accessing the complex objects in the memory and by comparing the characteristics of corresponding ones of the complex objects stored in the memory; and storing the sorted array of elements in a memory, wherein the forming of the sorted array by the sorting module includes the steps of; selecting at least two of the elements as pivot elements; and sorting the elements in the array using the at least two pivot elements as initially sorted elements of the second order defining the sorted array, and wherein the sorting step comprises; comparing the pivot elements with each other to determine a sort order for the pivot elements relative to each other; creating a plurality of empty sub-arrays that each correspond to a sorting interval relative to the pivot elements, such that the number of sub-arrays created is one more than the number of pivots; determining the relative sorting position of each of the non-pivot elements in the array with respect to the pivot elements; and dependent upon the determining, inserting each non-pivot element of the array into a corresponding one of the plurality of sub-arrays. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A non-transitory computer-readable storage medium having stored therein a computer program comprising code which when executed on a computer will:
-
access a source array of elements, wherein each of the elements includes a reference to one of a plurality of complex objects stored in memory and wherein each of the references comprises only an address or location for one of the complex objects in the memory; select at least two of the elements as pivot elements; compare a characteristic of each of the complex objects that correspond to each of the pivot elements with each other to determine a sort order for the pivot elements relative to each other; create a plurality of empty sub-arrays that each correspond to a sorting interval relative to the pivot elements, such that the number of sub-arrays created is one more than the number of pivot elements; determine the relative sorting position of each of the non-pivot elements in the array with respect to the pivot elements by comparing the characteristic of the corresponding complex object for each of the non-pivot elements; dependent upon the determination, insert each non-pivot element of the array into a corresponding one of the plurality of sub-arrays; and recursively perform the select, compare, create, determine, and insert steps for each of the plurality of sub-arrays until all of the elements of the source array are sorted from a first order to a second order differing from the first order to form a sorted array in in a sorted order defined by a sorting criteria for the source array of elements, wherein the relative sorting positions of the non-pivot elements is determined by using the pivot elements as initially sorted elements of the second order defining the sorted array. - View Dependent Claims (14, 15, 16, 17)
-
-
18. A computer system for sorting a source array that includes a plurality elements, the computer system comprising:
-
a sorting algorithm module that is stored in memory of the computer system, the sorting algorithm module being operable to convert an unsorted array of elements into a sorted array of elements; a plurality of complex objects stored in memory of the computer system; an array of elements stored in memory of the computer system, wherein the each of the elements includes a reference to one of the plurality of complex objects; a processor that is operative to execute the sorting algorithm module; and memory that is operable to store the sorted array of elements; wherein the sorting algorithm module is operable to sort the array of elements according to sorting criteria, the sorting algorithm comprising the steps of; selecting at least two of the elements as pivot elements; and sorting the elements in the array using the at least two pivot elements to form a sorted array, wherein the elements are sorted dependent on the sorting criteria, the sorting criteria including a characteristic of the complex objects, wherein the sorting is performed by iteratively accessing the complex objects in the memory to perform a comparison of values of the characteristics, and wherein the sorting algorithm further comprises the steps of; comparing the pivot elements with each other to determine a sort order for the pivot elements relative to each other; creating a plurality of empty sub-arrays that each correspond to a sorting interval relative to the pivot elements, such that the number of sub-arrays created is one more than the number of pivot elements; determining the relative sorting position of each of the non-pivot elements in the array with respect to the pivot elements; and dependent upon the determining, inserting each non-pivot element of the array into a corresponding one of the plurality of sub-arrays. - View Dependent Claims (19, 20, 21, 22)
-
Specification