C# || How To Sort An Array O(nlog(n)) Using C#

May 01, 2023 admin No comments

The following is a module with functions which demonstrates how to sort an array O(nlog(n)) complexity using C#.

1. Sort Array – Problem Statement

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1] Output: [1,2,3,5] Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0] Output: [0,0,1,1,2,5] Explanation: Note that the values of nums are not necessairly unique.

2. Sort Array – Solution

The following is a solution which demonstrates how to sort an array O(nlog(n)) complexity using C#.





		
		
			2. Sort Array - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to sort an array O(nlog(n))
// ============================================================================
public class Solution {
    public int[] SortArray(int[] nums) {
        RadixSort(nums);
        return nums;
    }

    // Radix sort function.
    private void RadixSort(int[] arr) {
        // Find the absolute maximum element to find max number of digits.
        int maxElement = arr[0];
        foreach (int val in arr) {
            maxElement = Math.Max(Math.Abs(val), maxElement);
        }
        int maxDigits = 0;
        while (maxElement > 0) {
            maxDigits += 1;
            maxElement /= 10;
        }

        // Radix sort, least significant digit place to most significant.
        int placeValue = 1;
        for (int digit = 0; digit < maxDigits; ++digit) {
            BucketSort(arr, placeValue);
            placeValue *= 10;
        }

        // Seperate out negatives and reverse them.
        List<int> negatives = new List<int>();
        List<int> positives = new List<int>();
        foreach (int val in arr) {
            if (val < 0) {
                negatives.Add(val);
            } else {
                positives.Add(val);
            }
        }
        negatives.Reverse();

        // Final 'answer' will be 'negative' elements, then 'positive' elements.
        int index = 0;
        foreach (int val in negatives) {
            arr[index++] = val;
        }
        foreach (int val in positives) {
            arr[index++] = val;
        }
    }

    // Bucket sort function for each place value digit.
    private void BucketSort(int[] arr, int placeValue) {
        int bucketSize = 10;
        List<List<int>> buckets = new List<List<int>>();
        for (int digit = 0; digit < bucketSize; ++digit) {
            buckets.Add(new List<int>());
        }

        // Store the respective number based on its digit.
        foreach (int val in arr) {
            int digit = Math.Abs(val) / placeValue;
            digit = digit % bucketSize;
            buckets[digit].Add(val);
        }

        // Overwrite 'arr' in sorted order of current place digits.
        int index = 0;
        for (int digit = 0; digit < bucketSize; ++digit) {
            foreach (int val in buckets[digit]) {
                arr[index++] = val;
            }
        }
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to sort an array O(nlog(n))
// ============================================================================
public class Solution {
    public int[] SortArray(int[] nums) {
        RadixSort(nums);
        return nums;
    }
 
    // Radix sort function.
    private void RadixSort(int[] arr) {
        // Find the absolute maximum element to find max number of digits.
        int maxElement = arr[0];
        foreach (int val in arr) {
            maxElement = Math.Max(Math.Abs(val), maxElement);
        }
        int maxDigits = 0;
        while (maxElement > 0) {
            maxDigits += 1;
            maxElement /= 10;
        }
 
        // Radix sort, least significant digit place to most significant.
        int placeValue = 1;
        for (int digit = 0; digit < maxDigits; ++digit) {
            BucketSort(arr, placeValue);
            placeValue *= 10;
        }
 
        // Seperate out negatives and reverse them.
        List<int> negatives = new List<int>();
        List<int> positives = new List<int>();
        foreach (int val in arr) {
            if (val < 0) {
                negatives.Add(val);
            } else {
                positives.Add(val);
            }
        }
        negatives.Reverse();
 
        // Final 'answer' will be 'negative' elements, then 'positive' elements.
        int index = 0;
        foreach (int val in negatives) {
            arr[index++] = val;
        }
        foreach (int val in positives) {
            arr[index++] = val;
        }
    }
 
    // Bucket sort function for each place value digit.
    private void BucketSort(int[] arr, int placeValue) {
        int bucketSize = 10;
        List<List<int>> buckets = new List<List<int>>();
        for (int digit = 0; digit < bucketSize; ++digit) {
            buckets.Add(new List<int>());
        }
 
        // Store the respective number based on its digit.
        foreach (int val in arr) {
            int digit = Math.Abs(val) / placeValue;
            digit = digit % bucketSize;
            buckets[digit].Add(val);
        }
 
        // Overwrite 'arr' in sorted order of current place digits.
        int index = 0;
        for (int digit = 0; digit < bucketSize; ++digit) {
            foreach (int val in buckets[digit]) {
                arr[index++] = val;
            }
        }
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[1,2,3,5] [0,0,1,1,2,5]

Was this article helpful?

👍 YesNo

Posted in: C#, Console Tags: c-sharp, leetcode

C# || How To Sort An Array O(nlog(n)) Using C#

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories