Например: int A[] = {3,2,1,2,3,2,1,3,1,2,3};
Как эффективно сортировать этот массив?
Это для собеседования, мне нужен только псевдокод.
Сортировка: как отсортировать массив, содержащий 3 вида чисел
Ответ 1
Описание проблемы: у вас есть n ковшей, каждое ведро содержит одну монету, значение монеты может быть 5 или 10 или 20. вам нужно сортировать ведра под этим ограничением: 1. вы можете использовать только эти 2 функции: SwitchBaskets (Basket1, Basket2) - корзины переключателей 2 GetCoinValue (Basket1) - вернуть значение монеты в выбранной корзине 2. вы не можете определить массив размера n 3. используйте функцию переключателя как можно меньше.
Мое простое решение псевдокода, которое может быть реализовано на любом языке с сложностью O (n).
Я возьму монету из корзины 1) если это 5 - нажмите, чтобы он был первым, 2) если это 20-нажмите его, чтобы быть последним, 3) Если 10 - оставить его там, где он есть. 4) и посмотрите на следующий ковш в линию.
Изменить:, если вы не можете нажимать элементы на первую или последнюю позицию, тогда Merge sort будет идеально для пиратской реализации. Вот как это будет работать:
Сортировка Merge использует простоту слияния уже отсортированных списков в новый отсортированный список. Он начинается с сравнения всех двух элементов (например, 1 с 2, затем 3 с 4...) и их замены, если первый должен прийти после второго. Затем он объединяет каждый из результирующих списков из двух в списки из четырех, затем объединяет эти списки из четырех и так далее; пока, наконец, два списка не будут объединены в окончательный отсортированный список. Из описанных здесь алгоритмов это первое, которое хорошо масштабируется для очень больших списков, поскольку его наихудшее время работы - O (n log n). Сортировка Merge показала относительно недавнюю популярность для практических реализаций, которая используется для стандартной процедуры сортировки на языках программирования.
Ответ 2
Перспективным способом сортировки является подсчет сортировки. Стоит взглянуть на эту лекцию Ричарда Бакланда, особенно часть с 15:20.
Аналогично сортировке подсчета, но еще лучше было бы создать массив, представляющий домен, инициализировать все его элементы до 0, а затем перебирать через массив и подсчитывать эти значения. Как только вы узнаете эти значения значений домена, вы можете соответствующим образом переписать значения вашего массива. Сложностью такого алгоритма будет O (n).
Здесь код С++ с поведением, как я его описал. Его сложность на самом деле равна 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;
Обратите внимание, что если существует большая разница между значениями домена, хранение домена в виде массива неэффективно. В этом случае гораздо лучше использовать карту (спасибо abhinav за ее указание). Здесь код С++, который использует 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 в вышеприведенном коде более эффективно, сообщите мне)
Ответ 3
Его стандартная проблема в информатике: проблема голландского национального флага См. Ссылку.
Ответ 4
подсчитывать каждое число, а затем создавать новый массив на основе их подсчетов... сложность времени в 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;
Ответ 5
Я думаю, этот вопрос намеревается использовать сортировку ведра. В случаях, когда имеется небольшое количество значений, сортировка ведра может быть намного быстрее, чем более часто используемые quicksort или mergesort.
Ответ 6
Как упоминал Роберт, basketsort (или bucketsort) является лучшим в этой ситуации.
Я бы также добавил следующий алгоритм (он действительно очень похож на сортировку букета):
[псевдокод - это java-стиль]
Создайте 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);
}
}
Ответ 7
Я думаю, что я не понимаю вопроса - вы можете использовать только O (1) пространство, и вы можете изменить массив только путем замены ячеек. (Таким образом, вы можете использовать 2 операции над массивом - swap и get)
Мое решение:
Используйте 2 указательных указателя - один для позиции последнего 1 и один для позиции последних 2.
На этапе я вы предполагаете, что массив allready отсортирован от 1 до i-1, чем вы проверяете i-я ячейка: Если A [i] == 3 ты ничего не делаешь. Если A [i] == 2 вы меняете его с помощью ячейки после последнего 2 индекса. Если A [i] == 1 вы меняете его с помощью ячейки после последнего 2 индекса, а затем меняете ячейку после последнего 2 индекса (который содержит 1) с ячейкой после последнего индекса.
Это основная идея, вам нужно позаботиться о маленьких деталях. Общая сложность O (n).
Ответ 8
Вы пытались посмотреть на wiki, например? - http://en.wikipedia.org/wiki/Sorting_algorithm
Ответ 9
Этот код предназначен для С#:
Тем не менее, вам нужно рассмотреть алгоритмы для его реализации нестандартным образом. Как предложено Bucket set, возможно, будет эффективным. Если вы предоставите подробную информацию о проблеме, я попытаюсь найти лучшее решение. Удачи...
Вот пример кода в С#.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());
Ответ 10
Просто для удовольствия, вот как бы вы реализовали "толкание значений к дальнему краю", как предположил Эль Юсубуб:
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--
Это может быть оптимальным решением. Я не уверен.
Ответ 11
Вот решение groovy, основанное на @ElYusubov, но вместо того, чтобы нажимать Bucket (5) на начало и Bucket (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} " }
Ответ 12
Позволяет разбить проблему, у нас есть только два числа в массиве. [1,2,1,2,2,2,1,1]
Мы можем сортировать за один проход o (n) с minm swaps, если; Мы начинаем два указателя слева и справа, пока они не встречаются друг с другом. Перемещение левого элемента с правом, если левый элемент больше. (сортировать по возрастанию)
Мы можем сделать еще один проход, для трех чисел (k-1 проходит). В проходе один мы переместили 1 в их конечную позицию, а в проходе 2 мы переместили 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
Ответ 13
Это можно сделать очень легко, используя →
Алгоритм голландского национального флага http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
вместо того, чтобы использовать 1,2,3, считать его 0,1,2
Ответ 14
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
Ответ 15
Я бы использовал рекурсивный подход здесь
fun sortNums(smallestIndex,largestIndex,array,currentIndex){
if(currentIndex >= array.size)
return
if (array[currentIndex] == 1){
You have found the smallest element, now increase the smallestIndex
//You need to put this element to left side of the array at the smallestIndex position.
//You can simply swap(smallestIndex, currentIndex)
// The catch here is you should not swap it if it already on the left side
//recursive call
sortNums(smallestIndex,largestIndex,array,currentIndex or currentIndex+1)// Now the task of incrementing current Index in recursive call depends on the element at currentIndex. if it 3, then you might want to let the fate of currentIndex decided by recursive function else simply increment by 1 and move further
} else if (array[currentInde]==3){
// same logic but you need to add it at end
}
}
Вы можете запустить рекурсивную функцию с помощью sortNums (smalllestIndex = -1, mostIndex = array.size, array, currentIndex = 0)
Вы можете найти образец кода здесь Кодовая ссылка
Ответ 16
//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;
}
}
}