Arhn - архитектура программирования

Пузырьковая сортировка в схеме

Я пишу рекурсивный код для пузырьковой сортировки (от меньшего к большему путем замены)
У меня есть код, выполняющий пузырьковую сортировку только один раз.

(define (bubble-up L)  
   (if (null? (cdr L))  
     L   
  (if (< (car L) (cadr L))  
(cons (car L) (bubble-up (cdr L)))  
(cons (cadr L) (bubble-up (cons (car L) (cddr L))))  
  )
 )

если я помещу список в этот код, он вернет список с наибольшим числом в конце
EX.. (пузырь-вверх ' (8 9 4 2 6 7)) -> ' (8 4 2 6 7 9 )

Теперь я пытаюсь написать код, чтобы сделать (пузырь L) N раз (количество целых чисел в списке)
У меня есть этот код:

  (define (bubble-sort-aux N L)   
    (cond ((= N 1) (bubble-up L))  
       (else (bubble-sort-aux (- N 1) L)  
  (bubble-up L))))  
(bubble-sort-aux 6 (list 8 9 4 2 6 7))  -> ' (8 4 2 6 7 9)

Но рекурсии, кажется, не происходит, потому что она сортируется только один раз!
Любые предложения приветствуются, я просто в тупике!

list sorting scheme bubble-sort
09.10.2013

  • Я пишу рекурсивный код для пузырьковой сортировки - не делайте этого! 09.10.2013
  • @MitchWheat AveryPoole пишет на схеме, где оптимизация хвостового вызова предписывается спецификацией. Итерация обычно достигается с помощью хвостовой рекурсии в Scheme. Отказ является естественным для реализации этого в Scheme. 09.10.2013
  • Есть ли альтернативный метод? Только начал писать код, хвостовая рекурсия - единственный способ, которым я научился. @MitchWheat 09.10.2013
  • @Joshua Taylor: я имел в виду использование BubbleSort в целом. 09.10.2013
  • Scheme (по крайней мере, R5RS) поддерживает конструкцию do итерации, но будет гораздо чаще видеть хвостовую рекурсию, используемую для выражения итерации в Scheme. Например, ответ Оскара Лопеса внешне рекурсивен, но поскольку вызов bubble-sort-aux находится в хвостовой позиции, он по существу итеративный. Однако ваш bubble-up не хвостовой рекурсии. Вы также можете попытаться сделать его рекурсивным. 09.10.2013

Ответы:


1

Попробуй это:

(define (bubble-sort-aux N L)   
  (cond ((= N 1) (bubble-up L))  
        (else (bubble-sort-aux (- N 1) (bubble-up L)))))

Если вы продолжите «пузырить» список N раз, он будет отсортирован в конце. Проблема с вашим кодом заключается в том, что вы ни для чего не использовали результат bubble-up, но если мы передадим значение, возвращаемое bubble-up, при следующем вызове функции, оно в конечном итоге будет отсортировано. Теперь процедура работает как положено:

(bubble-sort-aux 6 (list 8 9 4 2 6 7))
=> '(2 4 6 7 8 9)
09.10.2013
  • огромное спасибо Оскар! Кажется, я немного выгорел, это была большая ошибка =/ 09.10.2013

    • 2

    Моя реализация:

    (define (bubble-swap ls)
  (if (null? (cdr ls))
      ls
      (if (> (car ls) (cadr ls))
          (cons (cadr ls) (bubble-swap (cons (car ls) (cddr ls))))
          (cons (car ls) (bubble-swap (cdr ls))))))

(define (len ls)
  (if (null? ls)
      0
      (+ 1 (len (cdr ls)))))

(define (bubblesort_ ls n)
  (if (= n 1)
      ls
      (bubblesort_ (bubble-swap ls) (- n 1))))

(define (bubblesort ls) (bubblesort_ ls (len ls)))

    Я реализовал пользовательскую функцию len, но вы можете использовать стандартную функцию length, если она доступна.

    27.02.2017
    Новые материалы
    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..