Сортировка без сравнения элементов

Question

заданного размера массива 5, с пятью числами в нем, сортировать их от наименьшего к наибольшему без сравнения. (Подсказка, время доступа O (п)

Я пытался найти много, но техника его подводит знал , как это можно сделать. O (n), означает, что algo/data structure.i я не знаю.

Answer 1

Я полагаю, что вам нужно Counting sort, оно имеет линейное время, но занимает некоторую память и зависит от минимального/максимального значения ваш начальный массив

Answer 2

Counting Sort сделает это за вас, хотя, если бы я был в интервью и на месте, я бы, вероятно, сделал что-то вроде ниже h смутно подобен, поскольку я никогда не могу вспомнить эти «классические» алгоритмы с головы!

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

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

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

(Я лично не являюсь фанатом таких вопросов для интервью, где ответ «о, используйте Counting Sort» или что-то еще - я надеюсь, что интервьюер, задающий этот вопрос, будет искренне заинтересован, чтобы посмотреть, какой подход вы приняли к решению новой проблемы, независимо от того, получили ли вы строго правильный ответ или нет)

Производительность ниже: O (n) означает, что она работает в линейном времени (1 элемент занимает X количество времени, 10 элементов занимает 10X и т. д.), но он может использовать большую память, если элемент max является большим, не может выполнять сортировку по месту, будет работать только с примитивами, и это не то, что я надеюсь увидеть в производственном коде :)

void Main() 
{ 
    //create unsorted list of random numbers 
    var unsorted = new List<int>(); 
    Random rand = new Random(); 
    for(int x=0;x<10;x++) 
    { 
    unsorted.Add(rand.Next(1,10)); 
    } 
    //create array big enough to hold unsorted.Max() elements 
    //note this is indirectly performing a comparison of the elements of the array 
    //but not for the sorting, so I guess that is allowable :) 
    var sorted = new NumberCount[unsorted.Max()+1]; 
    //loop the unsorted array 
    for (int index=0;index<unsorted.Count;index++) 
    { 
    //get the value at the current index and use as an index to the target array 
     var value = unsorted[index]; 
     //if the sorted array contains the value at the current index, just increment the count 
     if (sorted[value]!=null && sorted[value].Value!=0) 
     { 
      sorted[value].Count++; 
     } 
     else 
     { 
     //insert the current value in it's index position 
     sorted[value]=new NumberCount{Value=value,Count=1};   
     } 
    } 
    //ignore all elements in sorted that are null because they were not part of the original list of numbers. 
    foreach (var r in sorted.Where(r=>r!=null)) 
    { 
     Console.WriteLine("{0}, occurs {1} times",r.Value,r.Count); 
    } 
} 

//just a poco to hold the numbers and the number of times they occurred. 
public class NumberCount 
{ 
    public int Value{get;set;} 
    public int Count{get;set;} 
}