Сортування масиву зі стоками та чергами

I need to create a method which sorts an array of integers using a Stack and a Queue. For instance if given [-1, 7, 0, 3, -2] -> [-2, -1, 0, 3, 7]. I'm completely lost at how to do this question, because I would just use a sorting method, however for this question I am not allowed to do that. Can anyone explain how to do this with a Stack and a Queue?

5
Добре, якщо враховувати вимогу використовувати стек або чергу, єдиним логічним способом це буде використання певної форми mergesort.
додано Автор scott_fakename, джерело
Добре, якщо враховувати вимогу використовувати стек або чергу, єдиним логічним способом це буде використання певної форми mergesort.
додано Автор scott_fakename, джерело
Це не те, що потрібно сортувати зі стеком або чергою. Можливо, ваш масив повинен бути реалізований як стек або черга.
додано Автор Rohit Jain, джерело
Або, можливо, скористайтеся StackSort ? ... Не забувайте, ви вже це робите.
додано Автор Philipp, джерело
додано Автор Philipp, джерело
Або, можливо, скористайтеся StackSort ? ... Не забувайте, ви вже це робите.
додано Автор Philipp, джерело
Погляньте на stackoverflow.com/a/23695092/3315914
додано Автор rpax, джерело
Погляньте на stackoverflow.com/a/23695092/3315914
додано Автор rpax, джерело
Так. По-перше, вам потрібно передати структуру даних до масиву. Пізніше ви можете використовувати якийсь алгоритм сортування. Наприклад, швидкий сортування.
додано Автор Petr Shypila, джерело
Так. По-перше, вам потрібно передати структуру даних до масиву. Пізніше ви можете використовувати якийсь алгоритм сортування. Наприклад, швидкий сортування.
додано Автор Petr Shypila, джерело
звучить трохи як домашній запит на курси даних
додано Автор Akunosh, джерело
звучить трохи як домашній запит на курси даних
додано Автор Akunosh, джерело

6 Відповіді

Багато алгоритмів швидкого сортування (наприклад, mergesort та quicksort) можуть бути ефективно впроваджені в пов'язаних списках , використовуючи той факт, що ви можете ефективно розглядайте окремий список як стек (шляхом додавання елементів до фронту) або черги (додавши елементи до спини). Отже, одним із можливих способів вирішення цієї проблеми є прийняття одного з цих алгоритмів сортування та підхід до нього, як якщо б ви сортували пов'язаний список, а не нормальну послідовність.

Наприклад, ось один простий спосіб, яким ви могли б реалізувати mergesort, використовуючи черги. Я написав це для сортування Integer s, але це можна легко розширити для обробки інших типів:

public void mergesort(Queue sequence) {
    /* Base case: Any 0- or 1-element sequence is trivially sorted. */
    if (sequence.size() <= 1) return;

    /* Otherwise, split the sequence in half. */
    Queue left  = new LinkedList(),
                   right = new LinkedList();
    while (!sequence.isEmpty()) {
        left.add(sequence.remove());
        if (!sequence.isEmpty()) {
           right.add(sequence.remove());
        }
    }

    /* Recursively sort both halves. */
    mergesort(left);
    mergesort(right);

    /* Merge them back together. */
    merge(left, right, sequence);
}

private void merge(Queue one, Queue two,
                   Queue result) {
    /* Keep choosing the smaller element. */
    while (!one.isEmpty() && !two.isEmpty()) {
        if (one.peek() < two.peek()) {
            result.add(one.remove());
        } else {
            result.add(two.remove());
        }
    }

    /* Add all elements from the second queue to the result. */
    while (!one.isEmpty()) {
        result.add(one.remove());
    }
    while (!two.isEmpty()) {
        result.add(two.remove());
    }
}

Загалом, це буде виконуватися в час O (n log n), що асимптотично оптимально.

Крім того, ви можете використовувати quicksort, як показано тут:

public void quicksort(Queue sequence) {
    /* Base case: Any 0- or 1-element sequence is trivially sorted. */
    if (sequence.size() <= 1) return;

    /* Choose the first element as the pivot (causes O(n^2) worst-case behavior,
     * but for now should work out fine.  Then, split the list into three groups,
     * one of elements smaller than the pivot, one of elements equal to the
     * pivot, and one of elements greater than the pivot.
     */
    Queue pivot = new LinkedList(),
                   less  = new LinkedList(),
                   more  = new LinkedList();

    /* Place the pivot into its list. */
    pivot.add(sequence.remove());

    /* Distribute elements into the queues. */
    while (!sequence.isEmpty()) {
        Integer elem = sequence.remove();
        if      (elem < pivot.peek()) less.add(elem);
        else if (elem > pivot.peek()) more.add(elem);
        else                          pivot.add(elem);
    }

    /* Sort the less and greater groups. */
    quicksort(less);
    quicksort(more);

    /* Combine everything back together by writing out the smaller
     * elements, then the equal elements, then the greater elements.
     */
    while (!less.isEmpty())  result.add(less.remove());
    while (!pivot.isEmpty()) result.add(pivot.remove());
    while (!more.isEmpty())  result.add(more.remove());
}

Це триває в найкращому випадку час O (n log n) та найгірший час O (n 2 ). Для цікавого вправу спробуйте вибрати вертикальний елемент у довільному порядку, щоб отримати очікуваний час виконання O (n log n). :-)

Зовсім іншим підходом, ви можете розглянути можливість виконувати найменш значущий сортування radix по значенням, оскільки ви знаєте, що це цілі числа:

public void radixSort(Queue sequence) {
    /* Make queues for values with a 0 in the current position and values with a
     * 1 in the current position.  It's an optimization to put these out here;
     * they honestly could be declared inside the loop below.
     */
    Queue zero = new LinkedList(),
                   one  = new LinkedList();

    /* We're going to need 32 rounds of this, since there are 32 bits in each
     * integer.
     */
    for (int i = 0; i < 32; i++) {
        /* Distribute all elements from the input queue into the zero and one
         * queue based on their bits.
         */
        while (!sequence.isEmpty()) {
            Integer curr = sequence.remove();

            /* Determine whether the current bit of the number is 0 or 1 and
             * place the element into the appropriate queue.
             */
            if ((curr >>> i) % 2 == 0) {
                zero.add(curr);
            } else {
                one.add(curr);
            }
        }

        /* Combine the elements from the queues back together.  As a quick
         * note - if this is the 31st bit, we want to put back the 1 elements
         * BEFORE the 0 elements, since the sign bit is reversed.
         */
        if (i == 31) {
            Queue temp = zero;
            zero = one;
            one = temp;
        }
        while (!zero.isEmpty()) result.add(zero.remove());
        while (!one.isEmpty())  result.add(one.remove());
    }
}

Це буде виконуватися в часі O (n log U), де U - це максимально можливе значення, яке можна зберегти в int .

Звичайно, всі ці алгоритми є ефективними та елегантними. Іноді, однак, ви хочете зробити повільний і неелегантний вид, як bogosort . Тепер bogosort дещо важко реалізувати, оскільки зазвичай це вимагає перемішування вхідної послідовності, що простіше робити в масиві. Однак ми можемо імітувати перестановку черги наступним чином:

  • Виберіть випадковий індекс у чергу.
  • Цикл через багато елементів.
  • Видалити цей елемент з черги та додати його до результату.
  • Повторити

This ends up taking time O(n2) rather than O(n), which has the unfortunate side-effect of making bogosort take expected time O(n2 &mdot; n!) rather than O(n &mdot; n!). However, it's the price we have to pay.

public void bogosort(Queue sequence, Random r) {
    while (!isSorted(sequence)) {
        permute(sequence, r);
    }
}

/* Checking if a sequence is sorted is tricky because we have to destructively modify
 * the queue.  Our process will be to cycle the elements of the sequence making sure
 * that each element is greater than or equal to the previous element.
 *
 * Because we are using bogosort, it's totally fine for us to destructively modify
 * the queue as long as all elements that were in the original input queue end up
 * in the resulting queue.  We'll do this by cycling forward through the elements
 * and stopping if we find something mismatched.
 */
private void isSorted(Queue sequence) {
    int last = Integer.MIN_VALUE;

    for (int i = 0; i < sequence.size(); i++) {
        int curr = sequence.remove();
        sequence.add(curr);

        if (curr < last) return false;
    }
    return true;
}

/* Randomly permutes the elements of the given queue. */
private void permute(Queue sequence, Random r) {
    /* Buffer queue to hold the result. */
    Queue result = new LinkedList();

    /* Continuously pick a random element and add it. */
    while (!sequence.isEmpty()) {
        /* Choose a random index and cycle forward that many times. */
        int index = r.nextInt(sequence.size());
        for (int i = 0; i < index; i++) {
            sequence.add(sequence.remove());
        }
        /* Add the front element to the result. */
        result.add(sequence.remove());
    }

    /* Transfer the permutation back into the sequence. */
    while (!result.isEmpty()) sequence.add(result.remove());
}

Сподіваюся, це допомагає!

7
додано
@templatetypedef Гей коротке запитання, скажімо, я хотів би, щоб параметр був ArrayQueue замість Queue , як мені змінити відповідь?
додано Автор hyperfkcb, джерело
Оце Так! Відмінна відповідь!
додано Автор rpax, джерело

Ви можете легко застосувати сортування вибору зі стеком та чергою:

Якщо дані спочатку знаходяться в стекі, поставте все в чергу та виконайте наступне:

int size = list.length;//list is the int[] sent as a method parameter.
while (size > 0) {//until we've placed all elements in their sorted positions
  int min = Integer.MAX_VALUE;//make sure the minimum is bigger than all the data
  for (int i = 0; i < size; i++) {//check all elements in the queue
    int temp = queue.dequeue();//mark the current element
    if (temp < min) min = temp;//if it's a possible minimum record it.
    queue.enqueue(temp);//place it back in the queue so we don't lose data.
  }
  for (int i = 0; i < size; i++) {//go through and remove the minimum element
    int temp = queue.dequeue();//mark the currently removed element
    if (temp == min) break;//if it's the minimum, stop we've removed it.
    queue.enqueue(temp);//otherwise put it back on.
  }
  stack.push(min);//put the minimum value on the stack (in sorted order)
  size--; //we have one less element to consider, so decrement the size.
}

Після сортування над елементами буде відсортовано зі стеків, після видалення їх усі повертають дані у порядку, від найбільшого до найменшого (що легко можна скасувати).

Ні, це не дуже ефективно, я припускаю, що це домашнє завдання. Реалістично, якщо ви хочете відсортувати дані, ви повинні використовувати Arrays.sort або Collections.sort, які реалізують сортування злиття для об'єктів та quicksort для примітивів. Це буде набагато швидше (O (NlogN) проти O (N * N)). Зрозумійте, однак, вам доведеться мати дані в масиві чи списку, щоб зробити це, а не стек або чергу.

5
додано
Вважається, що метод приймає в списку int [], який містить всі числа. А потім використовує Стеки та Чергу для сортування, що є непотрібним і безглуздим ... EDIT: Крім того, я обмежуюсь лише методами enqueue (), dequeue() та isEmpty() для черги та push() pop() і isEmpty() у стекі.
додано Автор user123, джерело
У цьому випадку просто покладіть кожен елемент з int [] у чергу, потім наприкінці поставте всі елементи зі стека у int [] у зворотному порядку. Я буду редагувати код ваших методів.
додано Автор Robert Mitchell, джерело

Ви можете легко застосувати сортування вибору зі стеком та чергою:

Якщо дані спочатку знаходяться в стекі, поставте все в чергу та виконайте наступне:

int size = list.length;//list is the int[] sent as a method parameter.
while (size > 0) {//until we've placed all elements in their sorted positions
  int min = Integer.MAX_VALUE;//make sure the minimum is bigger than all the data
  for (int i = 0; i < size; i++) {//check all elements in the queue
    int temp = queue.dequeue();//mark the current element
    if (temp < min) min = temp;//if it's a possible minimum record it.
    queue.enqueue(temp);//place it back in the queue so we don't lose data.
  }
  for (int i = 0; i < size; i++) {//go through and remove the minimum element
    int temp = queue.dequeue();//mark the currently removed element
    if (temp == min) break;//if it's the minimum, stop we've removed it.
    queue.enqueue(temp);//otherwise put it back on.
  }
  stack.push(min);//put the minimum value on the stack (in sorted order)
  size--; //we have one less element to consider, so decrement the size.
}

Після сортування над елементами буде відсортовано зі стеків, після видалення їх усі повертають дані у порядку, від найбільшого до найменшого (що легко можна скасувати).

Ні, це не дуже ефективно, я припускаю, що це домашнє завдання. Реалістично, якщо ви хочете відсортувати дані, ви повинні використовувати Arrays.sort або Collections.sort, які реалізують сортування злиття для об'єктів та quicksort для примітивів. Це буде набагато швидше (O (NlogN) проти O (N * N)). Зрозумійте, однак, вам доведеться мати дані в масиві чи списку, щоб зробити це, а не стек або чергу.

5
додано
Вважається, що метод приймає в списку int [], який містить всі числа. А потім використовує Стеки та Чергу для сортування, що є непотрібним і безглуздим ... EDIT: Крім того, я обмежуюсь лише методами enqueue (), dequeue() та isEmpty() для черги та push() pop() і isEmpty() у стекі.
додано Автор user123, джерело
У цьому випадку просто покладіть кожен елемент з int [] у чергу, потім наприкінці поставте всі елементи зі стека у int [] у зворотному порядку. Я буду редагувати код ваших методів.
додано Автор Robert Mitchell, джерело

Для простого сортування array ви можете використовувати Arrays.sort() .

Для черги спеціально PriorityQueue це те, що потрібно для сортування Queue . Подивіться файли Java .

Ви можете вставити значення в PriorityQueue за допомогою методу add() , і ви отримаєте сортовану Queue назад. Ви також можете керувати порядком сортування за допомогою Comparator .

4
додано
Я думав, що це питання стосується стеків і черг у абстрактному вигляді, а не типу Java Stack або Queue . Питання виглядає як нерозумний трюк, якщо відповідь "в Java, вони насправді реалізуються як масиви, так що ви можете використовувати стандартні методи сортування".
додано Автор templatetypedef, джерело
Чи не питання про те, як використовувати стеки та черги для сортування списку? Черги та черги з пріоритетами не такі ж, як черги, а Arrays.sort не є варіантом для стеку чи черги.
додано Автор templatetypedef, джерело
+1 для PriorityQueue
додано Автор arshajii, джерело
Саме тому я надав метод Arrays.sort() та параметр PriorityQueue . Нехай опитувач вибере.
додано Автор JHS, джерело
Коли запитання позначається в java і мова йде про Черви . Яке Queue , на вашу думку, задає питання.
додано Автор JHS, джерело

Для простого сортування array ви можете використовувати Arrays.sort() .

Для черги спеціально PriorityQueue це те, що потрібно для сортування Queue . Подивіться файли Java .

Ви можете вставити значення в PriorityQueue за допомогою методу add() , і ви отримаєте сортовану Queue назад. Ви також можете керувати порядком сортування за допомогою Comparator .

4
додано
Я думав, що це питання стосується стеків і черг у абстрактному вигляді, а не типу Java Stack або Queue . Питання виглядає як нерозумний трюк, якщо відповідь "в Java, вони насправді реалізуються як масиви, так що ви можете використовувати стандартні методи сортування".
додано Автор templatetypedef, джерело
Чи не питання про те, як використовувати стеки та черги для сортування списку? Черги та черги з пріоритетами не такі ж, як черги, а Arrays.sort не є варіантом для стеку чи черги.
додано Автор templatetypedef, джерело
+1 для PriorityQueue
додано Автор arshajii, джерело
Саме тому я надав метод Arrays.sort() та параметр PriorityQueue . Нехай опитувач вибере.
додано Автор JHS, джерело
Коли запитання позначається в java і мова йде про Черви . Яке Queue , на вашу думку, задає питання.
додано Автор JHS, джерело

Стеки та черги - це структури даних. Стек - FILO, а черга - FIFO. Якщо ви розумієте, як працюють ці структури даних, ви зможете зрозуміти це. У кінцевому підсумку ви можете використовувати ту саму логіку, яку ви зазвичай використовуєте для цього типу проблеми, за винятком того, що вам потрібно використовувати стек та черги у структурах даних.

Один із способів використання стека в Java - це сортувати числа за допомогою рекурсивного методу, оскільки Java має внутрішній стек пам'яті.

Надія, що допомагає.

1
додано
ІТ КПІ - Java
ІТ КПІ - Java
436 учасників