Category of sorting algorithm and complexity [closed]

Question

Just for fun, I wrote a sorting algorithm. I did not compare this with existing sorting algorithms.Can someone tell me what class of sorting algorithm this is and it's complexity? The algorithm primarily loops thru all elements finding the lowest in the array and removing them from the array from further processing. [taking duplicates into account]

static void Main(string[] args) { int[] s = { 90,90, 71, 82, 93, 75, 81, 54, 36, 102, 99, 34, -56,-56, 103, 78,796,52,5,215 }; Console.WriteLine($"Before sort: {string.Join(",", s)}"); int[] sorted = new int[s.Length]; int lowestNumber = 0; int[] removedOccurenceArray = s; bool isNonDuplicateMinFound = false; //checks if the same number has been processed before. int occurenceCount = 0; for (int i = 0; i <= s.Length - 1; i++) { if (i == 0) //First number in array check { sorted[i] = FindLowestNumber(s[i], s); } else { //remove the last foudn lowest number from array and also get the occurence count removedOccurenceArray = RemoveOccurenceFromArray(lowestNumber, removedOccurenceArray, out occurenceCount); if (occurenceCount > 1) //if more than 1 occurence found { for (int j = 0; j < occurenceCount - 1; j++) //-1 here as the lowest number was already added once in the previous iteration. J starts from 0 as i was already incremented and pointing to the next element in array { sorted[i + j] = lowestNumber; } i = i + (occurenceCount-1); //occurenceCount-1 as the number was already inserted once before } occurenceCount = 0; int ctr = 0; while (!isNonDuplicateMinFound) { var l = FindLowestNumber(removedOccurenceArray[ctr], removedOccurenceArray); if (!sorted.Contains(l)) { sorted[i] = l; isNonDuplicateMinFound = true; } ctr++; } isNonDuplicateMinFound = false; } lowestNumber = sorted[i]; } Console.WriteLine($"After sort : {string.Join(",", sorted)}"); Console.ReadLine(); } /// <summary> /// Takes a number and removes it from array giving out a new array and also outputing the number of occurences of that number /// </summary> /// <param name="numberToRemove"></param> /// <param name="s"></param> /// <param name="occurenceCount"></param> /// <returns></returns> private static int[] RemoveOccurenceFromArray(int numberToRemove, int[] s, out int occurenceCount) { int[] tmpmoddedArray = new int[s.Length]; int ctr = 0; int zeroCtr = 0; for (int i = 0; i <= s.Length - 1; i++) { if (s[i] != numberToRemove) { tmpmoddedArray[ctr] = s[i]; } else zeroCtr++; ctr++; } //if we can do a dynamic re-size of the array, we can get rid of this second loop int[] moddedArray = new int[tmpmoddedArray.Length - zeroCtr]; ctr = 0; int skipCtr = 0; for (int i = 0; i <= tmpmoddedArray.Length - 1; i++) { if (tmpmoddedArray[i] != 0) { moddedArray[ctr] = tmpmoddedArray[ctr + skipCtr]; ctr++; } else skipCtr++; } occurenceCount = zeroCtr; return moddedArray; } private static int FindLowestNumber(int numberToCompare, int[] set) { int lowestNumber = numberToCompare; if (set.Length == 1) return set[0];// this is the last number, just return it for (int i = 0; i <= set.Length - 1; i++) { if (set[i] == 0) continue; else if (set[i] <= lowestNumber) lowestNumber = set[i]; } return lowestNumber; } 

Answer 1

It is at O(n^3) as remove alone is O(n)

Consider this

int lowestNumber = numberToCompare; if (set.Length == 1) return set[0];// this is the last number, just return it for (int i = 0; i <= set.Length - 1; i++) { if (set[i] == 0) continue; else if (set[i] <= lowestNumber) lowestNumber = set[i]; } return lowestNumber; 

if (set.Length == 1) serves no purpose. The loop would just run once.

Why are you ignoring if (set[i] == 0)

Why are you not tracking duplicate positions of minimum in that loop? It would be almost free.

for (int i = 0; i <= s.Length - 1; i++) { if (i == 0) //First number in array check { sorted[i] = FindLowestNumber(s[i], s); } 

to

sorted[0] = FindLowestNumber(s[0], s); for (int i = 1; i <= s.Length - 1; i++) { 

If lowestNumber is increasing then why does it need to be removed from the array?

I doubt I could write a less efficient sort if I tried.

If you are going to do O(n^2) at least do it in one pass each

public static IEnumerable<int> Sorted(int[] set) { int count; int maxMin = int.MinValue; while ( (maxMin = Min(set, maxMin, out count)) != int.MaxValue ) { for(int i = 0; i < count; i++) yield return maxMin; }; } public static int Min(int[] set, int maxMin, out int count) { int min = int.MaxValue; count = 1; foreach (int i in set) { if (i == min) { count++; } else if(i > maxMin && i < min) { min = i; count = 1; } } return min; }