Сортировка: как отсортировать массив, содержащий 3 вида чисел

Например:int A[] = {3,2,1,2,3,2,1,3,1,2,3};

Как эффективно отсортировать этот массив?

Это для собеседования, мне нужен только псевдокод.

 Andre16 июн. 2012 г., 23:43
Способ обмануть. Уважатьsorting если вы действительно хотите узнать о них.
 dirkgently16 июн. 2012 г., 23:39
Что ты пробовал?
 Matt Wolfe16 июн. 2012 г., 23:46
Почему бы просто не посчитать, сколько их каждого, а затем сгенерировать новый массив из подсчета?
 thechmodmaster16 июн. 2012 г., 23:41
интервью завтра, но тот, у кого уже было такое же интервью, задал этот вопрос
 Angshuman Agarwal16 июн. 2012 г., 23:40
en.wikipedia.org/wiki/Quicksort, Если это для собеседования, то я думаю, что вы не можете ответить на Array.Sort ();)

Ответы на вопрос(15)

//Bubble sort for unsorted array - algorithm
public void  bubleSort(int arr[], int n) { //n is the length of an array
    int temp;
    for(int i = 0; i <= n-2; i++){
        for(int j = 0; j <= (n-2-i); j++){
            if(arr[j] > arr[j +1]){
                temp = arr[j];
                arr[j] = arr[j +1];
                arr[j + 1] = temp;

            }
        }

    }
Решение Вопроса

Это стандартная проблема в информатике:Проблема голландского национального флага Смотрите ссылку.

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

посчитать каждое число, а затем создать новый массив на основе их количества ... сложность времени в O (n)

 int counts[3] = {0,0,0};
 for(int a in A)
  counts[a-1]++;
 for(int i = 0; i < counts[0]; i++)
  A[i] = 1;
 for(int i = counts[0]; i < counts[0] + counts[1]; i++)
  A[i] = 2;
 for(int i = counts[0] + counts[1]; i < counts[0] + counts[1] + counts[2]; i++)
  A[i] = 3;
 17 июн. 2012 г., 01:37
На самом деле это O (n + k), где n = размер ввода и k = количество возможных значений. Так как k & lt; В примере, приведенном в оригинальном плакате, это спорный вопрос, но я думаю, что он должен быть понятен будущим посетителям.
 thechmodmaster16 июн. 2012 г., 23:55
Я не могу определить другой массив. я могу переключать ячейки (нужно переключать меньше, чем это возможно
 16 июн. 2012 г., 23:58
поэтому вместо числа массивов используйте три переменные

Я думаю, что я понимаю вопрос - вы можете использовать только O (1) пробел, и вы можете изменить массив только путем замены ячеек. (Таким образом, вы можете использовать 2 операции над массивом - своп и получить)

Мое решение:

Используйте 2 указателя указателя - один для позиции последних 1 и один для позиции последних 2.

На этапе i вы предполагаете, что массив уже отсортирован от 1 до i-1, чем вы проверяете i-ю ячейку: Если A [i] == 3     ты ничего не делаешь. Если A [i] == 2     Вы меняете его ячейкой после последних двух индексов. Если A [i] == 1     Вы меняете его ячейкой после последних двух индексов, а затем меняете ячейку     после последнего 2 индекса (который содержит 1) с ячейкой после последнего 1 индекса.

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

Просто для забавы, вот как вы бы реализовали «перемещение значений к дальнему краю», как предложил ElYusubub:

sort(array) {
  a = 0
  b = array.length
  # a is the first item which isn't a 1 
  while array[a] == 1
    a++
  # b is the last item which isn't a 3
  while array[b] == 3
    b--

  # go over all the items from the first non-1 to the last non-3
  for (i = a; i <= b; i++)
    # the while loop is because the swap could result in a 3 or a 1
    while array[i] != 2
      if array[i] == 1
        swap(i, a)
        while array[a] == 1
          a++
      else # array[i] == 3
        swap(i, b)
        while array[b] == 3
          b--

Это может быть оптимальным решением. Я не уверен.

Решение Вопроса

Описание проблемы: у вас есть n ведер, в каждом ведре содержится одна монета, стоимость монеты может быть 5, 10 или 20. Сортировать ведра следует по этому ограничению: 1. Вы можете использовать только эти 2 функции: SwitchBaskets (Basket1 , Basket2) & # x2013; переключить 2 корзины GetCoinValue (Basket1) & # x2013; вернуть значение монеты в выбранной корзине 2. вы не можете определить массив размером n 3. используйте функцию switch как можно меньше.

Моё простое решение с псевдокодом, которое может быть реализовано на любом языке со сложностью O (n).

Я заберу монету из корзины 1) если это 5 - нажмите на нее, чтобы быть первым, 2) если это 20 - нажмите его, чтобы быть последним, 3) Если 10 - оставь его там, где он есть. 4) и посмотрите на следующее ведро в очереди.

Edit: if you can't push elements to the first or last position затемСортировка слиянием было бы идеально для пиратской реализации. Вот как это будет работать:

Сортировка слиянием использует преимущества простоты объединения уже отсортированных списков в новый отсортированный список. Он начинается со сравнения каждых двух элементов (то есть 1 с 2, затем 3 с 4 ...) и замены их, если первое должно следовать после второго. Затем он объединяет каждый из результирующих списков из двух в списки из четырех, затем объединяет эти списки из четырех и т. Д .; пока, наконец, два списка не будут объединены в окончательный отсортированный список. Из описанных здесь алгоритмов это первый, который хорошо масштабируется до очень больших списков, потому что его наихудшее время выполнения O (n log n). Сортировка слиянием получила сравнительно недавний всплеск популярности для практических реализаций, использовавшихся для стандартной процедуры сортировки в языках программирования.

 17 июн. 2012 г., 00:55
Попробуйте использовать сортировку Merge тогда
 17 июн. 2012 г., 01:08
Нет проблем, мне приятно найти хорошее решение.
 thechmodmaster17 июн. 2012 г., 01:04
ElYusubov большое спасибо за вашу помощь, я действительно ценю это!
 thechmodmaster17 июн. 2012 г., 00:42
Вы не можете нажать до конца или до первого - вы можете переключаться только между двумя ведрами.

Этот код для c #:

Тем не менее, вы должны рассмотреть алгоритмы для его реализации не языковым / структурным образом. Как предложеноНабор ковшей может быть эффективным, чтобы пойти с. Если вы предоставите подробную информацию о проблеме, я постараюсь найти лучшее решение. Удачи...

Вот пример кода в C # .NET

int[] intArray = new int[9] {3,2,1,2,3,2,1,3,1 };
Array.Sort(intArray);
// write array
foreach (int i in intArray) Console.Write("{0}, ", i.ToString());  
 17 июн. 2012 г., 00:29
Вот как бы я это сделал. Я выберу монету 1), если она 5 - нажмите ее, чтобы быть первой, 2), если она 20 - нажмите, чтобы быть последней, 3) Если 10 - оставьте ее там, где она есть. 4) и посмотрите на следующее ведро в очереди.
 thechmodmaster17 июн. 2012 г., 00:20
Я буду более конкретным: у вас есть n ведер, в каждом ведре содержится одна монета, стоимость монеты может быть 5 0r 10 или 20. Вы должны отсортировать ведра по этому ограничению: 1. Вы можете использовать только эти 2 функции: SwitchBaskets (Basket1, Basket2) & # x2013; переключить 2 корзины GetCoinValue (Basket1) & # x2013; вернуть значение монеты в выбранной корзине 2. вы не можете определить массив размером n 3. используйте функцию switch как можно меньше.

Как уже упоминал Роберт, корзинка (или корзина) является лучшей в этой ситуации.

Я бы также добавил следующий алгоритм (на самом деле он очень похож на сортировку busket):

[pseudocode is java-style]

СоздатьHashMap<Integer, Interger> map и цикл через ваш массив:

for (Integer i: array)
{
    Integer value = map.get(i);
    if (value == null)
    {
        map.put(i, 1);
    }
    else
    {
        map.put(i, value+1);
    }
}
 thechmodmaster17 июн. 2012 г., 00:21
это оригинальный вопрос: у вас есть n ведер, в каждом ведре содержится одна монета, стоимость монеты может быть 5 0r 10 или 20. Вы должны отсортировать ведра в соответствии с этим ограничением: 1. вы можете использовать только эти 2 функции: SwitchBaskets (Basket1, Basket2) & # x2013; переключить 2 корзины GetCoinValue (Basket1) & # x2013; вернуть значение монеты в выбранную корзину 2. вы не можете определить массив размером n 3. используйте функцию переключения как можно меньше

Многообещающим способом сортировки кажетсясортировка, Стоит взглянуть наэта лекция Ричард Бакленд, особенно часть из 15:20.

Аналогично счетной сортировке, но еще лучше было бы создать массив, представляющий домен, инициализировать все его элементы равными 0, а затем выполнить итерацию по вашему массиву и посчитать эти значения. Как только вы узнаете эти значения значений доменов, вы можете переписать значения вашего массива соответствующим образом. Сложность такого алгоритма будет O (n).

Вот код C ++ с поведением, как я его описал. Его сложность на самом деле O (2n), хотя:

int A[] = {3,2,1,2,3,2,1,3,1,2,3};
int domain[4] = {0};

// count occurrences of domain values - O(n):  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
    domain[A[i]]++;

// rewrite values of the array A accordingly - O(n):    
for (int k = 0, i = 1; i < 4; ++i)
    for (int j = 0; j < domain[i]; ++j)
        A[k++] = i;

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

int A[] = {2000,10000,7,10000,10000,2000,10000,7,7,10000};
std::map<int, int> domain;

// count occurrences of domain values:  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
{
    std::map<int, int>::iterator keyItr = domain.lower_bound(A[i]);
    if (keyItr != domain.end() && !domain.key_comp()(A[i], keyItr->first))
        keyItr->second++; // next occurrence 
    else
        domain.insert(keyItr, std::pair<int,int>(A[i],1)); // first occurrence
}

// rewrite values of the array A accordingly:    
int k = 0;
for (auto i = domain.begin(); i != domain.end(); ++i)
    for (int j = 0; j < i->second; ++j)
        A[k++] = i->first;

(если есть способ, как использоватьstd::map в приведенном выше коде более эффективным, дайте мне знать)

 20 июн. 2012 г., 11:00
@abhinav: я отредактировал свой ответ :)
 17 июн. 2012 г., 00:20
Я думаю, что это ответ, который я имел в виду, но не мог объяснить хорошо :) Сложность должна быть определенно O (n). Другими словами, должна быть только одна итерация для всех элементов исходного массива.
 20 июн. 2012 г., 10:20
Кто-нибудь может прокомментировать, как сделать форматирование в комментариях? Я могу сделать это в сообщении или новом ответе, но не смог сделать это в комментарии, как видно выше.
 20 июн. 2012 г., 10:05
@abhinav: Да, если этот домен содержит значения такого типа, гораздо лучше использовать map. Но даже если вы замените массив для карты, подход останется почти таким же (аналогичным).
 20 июн. 2012 г., 09:55
сортировка по счету является наилучшей, но ваш подход плохо масштабируется, если у нас большой динамический диапазон. Я имею в виду, если у меня есть массив A [] = {1, 10, 1000, 1, 200}. В этом случае вам потребуется домен размером не менее max (A), что означало бы наличие 1000 * elemSize выделений для массива всего из 5 элементов (с учетом только положительных элементов). Лучшим подходом к тому же алгоритму была бы карта (я не говорюhash карта; только древовидная карта), и вы можете сделать это просто путем count ++ = 0; asize = sizeof (A) / sizeof (A [0]); while (count ++ & lt; asize) countmap.insert (/ * key * / A [count], / * value * / countmap [A [count]]);

Вот отличное решение, основанное на @ElYusubov, но вместо того, чтобы нажимать Bucket (5) на начало & amp; Ведро (15) до конца. Используйте просеивание так, чтобы 5 перемещались к началу и 15 к концу.

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

array = [15,5,10,5,10,10,15,5,15,10,5]

    def swapBucket(int a, int b) {

        if (a == b) return; 
        array[a] = array[a] + array[b]
        array[b] = array[a] - array[b]
        array[a] = array[a] - array[b]

    }

def getBucketValue(int a) {
    return array[a];
}

def start = 0, end = array.size() -1, counter = 0;
// we can probably do away with this start,end but it helps when already sorted.

// start - first bucket from left which is not 5
while (start < end) {

    if (getBucketValue(start) != 5) break;
    start++;

}     

// end - first bucket from right whichis not 15
while (end > start) {

    if (getBucketValue(end) != 15) break;
    end--;

}

// already sorted when end = 1 { 1...size-1 are Buck(15) } or start = end-1      

for (counter = start; counter < end;) {

    def value = getBucketValue(counter)

    if (value == 5) { swapBucket(start, counter); start++; counter++;}
    else if (value == 15) { swapBucket(end, counter); end--; } // do not inc counter
    else { counter++; }

}

for (key in array) { print " ${key} " }
def DNF(input,length):
    high = length - 1
    p = 0
    i = 0
    while i <= high:
            if input[i] == 0:
                    input[i],input[p]=input[p],input[i]
                    p = p+1
                    i = i+1
            elif input[i] == 2:
                    input[i],input[high]=input[high],input[i]
                    high = high-1
            else:
                    i = i+1
input = [0,1,2,2,1,0]
print "input: ", input
DNF(input,len(input))
print "output: ", input

Вы пытались посмотреть на вики, например? -http://en.wikipedia.org/wiki/Sorting_algorithm

 thechmodmaster16 июн. 2012 г., 23:52
Я изучил все алгоритмы сортировки, но поскольку этот массив содержит только 3 параметра (1,2 и 3), я подумал, что здесь есть хитрость
 17 июн. 2012 г., 00:02
Нет, каждый алгоритм сортировки будет иметь дело с этим. Но если вы знаете, что только с 3 вариантами (1,2,3) вы можете линейно пройти массив и считать номер 1. Если вы нашли номер 1, вы поместите его в начало массива, если вы нашли номер 3 Вы помещаете это в конец массива, число 2 должно быть помещено в возможность - число чисел 1 (вы помните это) + 1.

Давайте разберем проблему, у нас есть только два числа в массиве. [1,2,1,2,2,2,1,1]

Мы можем отсортировать за один проход o (n) с минимальными перестановками if;   Мы начинаем два указателя слева и справа, пока они не встретятся.   Замена левого элемента на правый, если левый элемент больше. (Сортировать по возрастанию)

Мы можем сделать еще один проход для трех чисел (k-1 проходов). На первом проходе мы переместили 1 в их окончательное положение, а на втором проходе мы переместили 2.

def start = 0, end = array.size() - 1;

// Pass 1, move lowest order element (1) to their final position 
while (start < end) {
    // first element from left which is not 1
    for ( ; Array[start] ==  1 && start < end ; start++);
    // first element from right which IS 1
    for ( ; Array[end] != 1 && start < end ; end--);

    if (start < end) swap(start, end);
}     

// In second pass we can do 10,15

// We can extend this using recurion, for sorting domain = k, we need k-1 recurions 

Это можно сделать очень легко, используя - & gt;

Dutch national Flag algorithm http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

вместо 1,2,3 возьмите его как 0,1,2

Ваш ответ на вопрос