Method DensePartialSort

DensePartialSort<T>(IEnumerable<T>, int)

Executes a partial sort of the top count elements of a sequence, including ties. If count is less than the total number of elements in source, then this method will improve performance.

Declaration

public static IEnumerable<T> DensePartialSort<T>(this IEnumerable<T> source, int count)

Parameters

Type	Name	Description
IEnumerable<T>	source	The source sequence.
int	count	Number of (maximum) elements to return.

Returns

Type	Description
IEnumerable<T>	A sequence containing at most top count elements from source, in their ascending order.

Type Parameters

Name	Description
T	Type of elements in the sequence.

Remarks

This is an O(n * log(K)) operation where K is count.

This method is implemented by using deferred execution. However, source will be consumed in it's entirety immediately when first element of the returned sequence is consumed.

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key.

Examples

The following code example demonstrates how to get the top N items of a sequence using DensePartialSort.

var sequence = new Item[]
{
    new(key: 5, text: "1"),
    new(key: 5, text: "2"),
    new(key: 4, text: "3"),
    new(key: 4, text: "4"),
    new(key: 3, text: "5"),
    new(key: 3, text: "6"),
    new(key: 2, text: "7"),
    new(key: 2, text: "8"),
    new(key: 1, text: "9"),
    new(key: 1, text: "10"),
};

// Get the top N sets of items
var result = sequence.DensePartialSort(3);

Console.WriteLine(
    "[" +
    string.Join(", ", result) +
    "]");

// This code produces the following output:
// [(1, 9), (1, 10), (2, 7), (2, 8), (3, 5), (3, 6)]

class Item : IComparable<Item>
{
    public Item(int key, string text)
    {
        Key = key;
        Text = text;
    }

    public int Key { get; }
    public string Text { get; }

    public int CompareTo(Item other) =>
        this.Key.CompareTo(other.Key);

    public override string ToString() =>
        $"({this.Key}, {this.Text})"; 
}

Exceptions

Type	Condition
ArgumentNullException	source is null.
ArgumentOutOfRangeException	count is less than 1.

DensePartialSort<T>(IEnumerable<T>, int, OrderByDirection)

Executes a direction partial sort of the top count elements of a sequence, including ties. If count is less than the total number of elements in source, then this method will improve performance.

Declaration

public static IEnumerable<T> DensePartialSort<T>(this IEnumerable<T> source, int count, OrderByDirection direction)

Parameters

Type	Name	Description
IEnumerable<T>	source	The source sequence.
int	count	Number of (maximum) elements to return.
OrderByDirection	direction	The direction in which to sort the elements

Returns

Type	Description
IEnumerable<T>	A sequence containing at most top count elements from source, in the specified order.

Type Parameters

Name	Description
T	Type of elements in the sequence.

Remarks

This is an O(n * log(K)) operation where K is count.

This method is implemented by using deferred execution. However, source will be consumed in it's entirety immediately when first element of the returned sequence is consumed.

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key.

Examples

The following code example demonstrates how to get the top N items of a sequence using DensePartialSort.

var sequence = new Item[]
{
    new(key: 5, text: "1"),
    new(key: 5, text: "2"),
    new(key: 4, text: "3"),
    new(key: 4, text: "4"),
    new(key: 3, text: "5"),
    new(key: 3, text: "6"),
    new(key: 2, text: "7"),
    new(key: 2, text: "8"),
    new(key: 1, text: "9"),
    new(key: 1, text: "10"),
};

// Get the top N sets of items
var result = sequence.DensePartialSort(3, OrderByDirection.Descending);

Console.WriteLine(
    "[" +
    string.Join(", ", result) +
    "]");

// This code produces the following output:
// [(5, 1), (5, 2), (4, 3), (4, 4), (3, 5), (3, 6)]

class Item : IComparable<Item>
{
    public Item(int key, string text)
    {
        Key = key;
        Text = text;
    }

    public int Key { get; }
    public string Text { get; }

    public int CompareTo(Item other) =>
        this.Key.CompareTo(other.Key);

    public override string ToString() =>
        $"({this.Key}, {this.Text})"; 
}

Exceptions

Type	Condition
ArgumentNullException	source is null.
ArgumentOutOfRangeException	count is less than 1.

DensePartialSort<T>(IEnumerable<T>, int, IComparer<T>?)

Executes a partial sort of the top count elements of a sequence, including ties, using comparer to compare elements. If count is less than the total number of elements in source, then this method will improve performance.

Declaration

public static IEnumerable<T> DensePartialSort<T>(this IEnumerable<T> source, int count, IComparer<T>? comparer)

Parameters

Type	Name	Description
IEnumerable<T>	source	The source sequence.
int	count	Number of (maximum) elements to return.
IComparer<T>	comparer	An IComparer<T> to compare elements.

Returns

Type	Description
IEnumerable<T>	A sequence containing at most top count elements from source, in their ascending order.

Type Parameters

Name	Description
T	Type of elements in the sequence.

Remarks

This is an O(n * log(K)) operation where K is count.

This method is implemented by using deferred execution. However, source will be consumed in it's entirety immediately when first element of the returned sequence is consumed.

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key.

Examples

The following code example demonstrates how to get the top N items of a sequence using DensePartialSort.

var sequence = new[]
{
    (key: 5, text: "1"),
    (key: 5, text: "2"),
    (key: 4, text: "3"),
    (key: 4, text: "4"),
    (key: 3, text: "5"),
    (key: 3, text: "6"),
    (key: 2, text: "7"),
    (key: 2, text: "8"),
    (key: 1, text: "9"),
    (key: 1, text: "10"),
};

// Get the top N sets of items
var result = sequence
    .DensePartialSort(
        3, 
        Comparer<(int key, string text)>.Create((x, y) => x.key.CompareTo(y.key)));

Console.WriteLine(
    "[" +
    string.Join(", ", result) +
    "]");

// This code produces the following output:
// [(1, 9), (1, 10), (2, 7), (2, 8), (3, 5), (3, 6)]

Exceptions

Type	Condition
ArgumentNullException	source is null.
ArgumentOutOfRangeException	count is less than 1.

DensePartialSort<T>(IEnumerable<T>, int, IComparer<T>?, OrderByDirection)

Executes a direction partial sort of the top count elements of a sequence, including ties, using comparer to compare elements. If count is less than the total number of elements in source, then this method will improve performance.

Declaration

public static IEnumerable<T> DensePartialSort<T>(this IEnumerable<T> source, int count, IComparer<T>? comparer, OrderByDirection direction)

Parameters

Type	Name	Description
IEnumerable<T>	source	The source sequence.
int	count	Number of (maximum) elements to return.
IComparer<T>	comparer	A IComparer<T> to compare elements.
OrderByDirection	direction	The direction in which to sort the elements

Returns

Type	Description
IEnumerable<T>	A sequence containing at most top count elements from source, in the specified order.

Type Parameters

Name	Description
T	Type of elements in the sequence.

Remarks

This is an O(n * log(K)) operation where K is count.

This method is implemented by using deferred execution. However, source will be consumed in it's entirety immediately when first element of the returned sequence is consumed.

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key.

Examples

The following code example demonstrates how to get the top N items of a sequence using DensePartialSort.

var sequence = new[]
{
    (key: 5, text: "1"),
    (key: 5, text: "2"),
    (key: 4, text: "3"),
    (key: 4, text: "4"),
    (key: 3, text: "5"),
    (key: 3, text: "6"),
    (key: 2, text: "7"),
    (key: 2, text: "8"),
    (key: 1, text: "9"),
    (key: 1, text: "10"),
};

// Get the top N sets of items
var result = sequence
    .DensePartialSort(
        3, 
        Comparer<(int key, string text)>.Create((x, y) => x.key.CompareTo(y.key)),
        OrderByDirection.Descending);

Console.WriteLine(
    "[" +
    string.Join(", ", result) +
    "]");

// This code produces the following output:
// [(5, 1), (5, 2), (4, 3), (4, 4), (3, 5), (3, 6)]

Exceptions

Type	Condition
ArgumentNullException	source is null.
ArgumentOutOfRangeException	count is less than 1.