Bubble Sort from Lab [½ pt extra credit] Note that you are only allowed to use t

Question

Bubble Sort from Lab [½ pt extra credit]

Note that you are only allowed to use the following LISP functions: defun, cond, car, cdr, list, cons, append, >, <, >=, <=, = and null. (DO NOT USE set or setq.)

To implement a bubble sort we started developing the code in lab. I designed a recursive solution that used two functions: sort and bubbleUp. I implemented the latter in lab (code below). Note I used color to help differentiate the if parts of the conditional from the then parts.

(defun bubbleUp (n)

(cond

((null n) nil)

((null (cdr n)) n)

((> (car n) (car (cdr n)))

(append (list (car (cdr n))) (bubbleUp (cons (car n) (cdr (cdr n))))))

    (T (append (list (car n)) (bubbleUp (cdr n))))

)

Your job is to write the sort that uses bubbleUp:

(defun sort (n)

    ???

)

A call to sort will output the following:

> (sort ‘(5 4 3 2 1)) > (1 2 3 4 5)

> (sort ‘(6 4 3 9 8))

> (3 4 6 8 9)

A hint about what goes in ???. You cannot simply call bubbleUp n number of times since you don’t know n (yes it works on the command line but that’s because you know how many times to call it). So you likely have to check for an empty list in order to stop. This usually means a cond of the form in bubbleUp that checks for a null list, etc. The meat of the sort will be one of the conditional clauses where you have to call bubbleUp with the list, minus the last item. So in LISP it’s easy to get the first (car) and all-but-the first (cdr) item but not as easy to get the last item (you have to do a bit of thinking for this).

Explanation / Answer

Bubble sort using recursive funtion in c is as below

#include <stdio.h>
#include <stdlib.h>

void BubbleSorting(int *inp_data, int n) {
int x, temporary;

if (n > 0) {
for (x = 1; x< n; x++) {
if (inp_data[x - 1] > inp_data[x]) {
temporary = inp_data[x];
inp_data[x] = inp_data[x - 1];
inp_data[x - 1] = temporary;
}
}

BubbleSorting(inp_data, n - 1);
}

return;
}

int main() {
int i, n, *inp_data;

/* ask for user input */
printf("Number of inputs should enter:");
scanf("%d", &n);

/* dynamically allocate memory */
inp_data = (int *) malloc(sizeof(int) * n);

/* input inp_data from the user */
for (i = 0; i < n; i++) {
printf("inp_data[%d]: ", i);
scanf("%d", &inp_data[i]);
}

/* call the sort function*/
BubbleSorting(inp_data, n);

/* print the sorted numbers */
printf("inp_data After Bubble Sort: ");
for (x = 0; x < n; x++) {
printf("%d ", inp_data[x]);
}
printf(" ");

return 0;
}

Please let us know if this works for you.Thanks!

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.