Можете ли вы назвать этот алгоритм сортировки?

Question

У меня есть базовые знания в C#, я немного читал об алгоритмах сортировки, но я не смог идентифицировать этот. Я написал его в C#, и программа принимает список строк в качестве входных данных и выводит их в отсортированном порядке. Если вы можете назвать этот алгоритм, пожалуйста, сделайте это.

List<string> inputStrings = new List<string>(); 
string currentString = ""; 
Console.WriteLine("Enter strings and when you want to stop type '$$$'."); 
while (currentString != "$$$") 
{ 
    currentString = Console.ReadLine(); 
    if (currentString != "$$$") 
     inputStrings.Add(currentString); 
} 
for (int i = 0; i < inputStrings.Count - 1; i++) 
{ 
    for (int k = i + 1; k < inputStrings.Count; k++) 
    { 
     if (inputStrings[i].CompareTo(inputStrings[k]) > 0) 
     { 
      string tempString = inputStrings[i]; 
      inputStrings[i] = inputStrings[k]; 
      inputStrings[k] = tempString; 
     } 
    } 
} 
Console.WriteLine("These are the strings shown in sorted order:"); 
for (int i = 0; i < inputStrings.Count; i++) 
{ 
    Console.WriteLine(inputStrings[i]); 
} 

Answer 1

Это Selection Sort

Алгоритм делит список ввода на две части: подсписок элементов уже отсортирован, который строится слева направо спереди (слева) из списка, и список предметов, оставшихся для сортировки, которые занимают остальную часть списка. Первоначально отсортированный подсписок пуст, а несортированный подсписок - это весь список ввода. Алгоритм продолжается путем нахождения наименьшего (или самого большого, в зависимости от порядка сортировки) элемента в несортированном подсписке, обменивая (свопинг) его с самым левым несортированным элементом (помещая его в отсортированный порядок) и перемещая границы субблица один элемент вправо ,

Значение i представляет собой границу между уже отсортированной частью массива и частью, подлежащей сортировке.

Эта реализация не ортодоксальна, поскольку она мгновенно меняет значение на месте, а не ждет завершения вложенного цикла. Однако в этой реализации присутствует характерная часть сортировки выбора, которая ищет линейное значение следующего значения в несортированной части.

Это негативно скажется на производительности, поскольку общее количество свопов будет расти от O (n) до O (n).

Чтобы понять, почему это произойдет, рассмотрите наихудший вариант для этого алгоритма, когда массив отсортирован в обратном порядке. Когда это происходит, каждая итерация будет «двигаться» оставшаяся часть массива на один элемент (| знака представляет собой отсортированную/несортированную границу):

| a b c d -- first iteration of the outer loop 
    b a c d -- nested loop starts 
    c a b d 
    d a b c -- nested loop finishes 
d | a b c -- second iteration of the outer loop 
    d b a c 
    d c a b 
d c | a b -- third iteration of the outer loop 
    d c b a 
d c b | a -- final state 

Answer 2

Это называется пузырьковый вид.

Вы можете это оптимизировать, используя Optimized Bubble Sort.

Кроме того, я бы предпочел не использовать $$$ для завершения ввода. Почему бы просто не запросить всю строку, введенную в одну строку, с запятой между каждой строкой. Затем вы можете разбить одну входную строку на Comma, в результате получится список подстроки.

Answer 3

Он выглядит как смесь между Selection sort и Bubble sort. Подобно сортировке сортировки, в конце каждой итерации i i-й элемент будет отсортирован. Однако, в отличие от сортировки сортировки, он не ищет максимальное оставшееся значение, но вместо этого свопит сразу, как только он найдет большее значение, что и делает пузырь.

Я не думаю, что этот точный алгоритм имеет имя.