Pseudo-code for a basic Bubble Sort routine: procedure BubbleSort( A : list of s

Question

Pseudo-code for a basic Bubble Sort routine:

procedure BubbleSort( A : list of sortable items )

repeat

swapped = false
for each item in A inclusive do:

if A[i-1] > A[i] then

swap A[i-1] and A[i] swapped = true

end if

end for

until not swapped

end procedure

modify the program below so that menu option “4 to quit” becomes menu option “5 to quit”. And then add a new menu option “4 to sort”. So that way, the program will still function as it did, but when someone chooses option 4 your BubbleSort function will sort the items in ascending ordering. Your function will not display anything, it will just perform the sort and then someone can use menu option 3 to view the items in the linked list. Just to be clear, you don't have to mess around with rearranging the linked list, simply swap the values of dataitem.

Explanation / Answer

Here is the code

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

#define FALSE 0
#define EMPTY 0

struct listelement_struct
{
int    dataitem;
struct listelement_struct *next;
};

typedef struct listelement_struct listelement;

void Menu(int *);
listelement *AddItem(listelement *, int);
listelement *RemoveItem(listelement *);
void PrintQueue(listelement *);
void ClearQueue(listelement *);
void bubbleSort(listelement *);
void swap(listelement *a, listelement *b);

int main()
{
listelement *listpointer;
int data, choice;

listpointer = EMPTY;
do
{
    Menu(&choice);
    switch (choice)
    {
      case 1:
        printf(" Enter data item value to add: ");
        scanf("%d", &data);
        listpointer = AddItem(listpointer, data);
        break;
      case 2:
        if (listpointer == EMPTY)
        { printf(" Queue empty! "); }
        else
        { listpointer = RemoveItem(listpointer); }
        break;
      case 3:
        PrintQueue(listpointer);
        break;
      case 4:
        bubbleSort(listpointer);
        break;
      case 5:
        break;
      default:
        printf(" Invalid menu choice (%d) - try again ", choice);
        char dummy = getchar(); // Eats up our bad menu choice
        break;
    }
} while (choice != 5);
ClearQueue(listpointer);
exit(0);
}                               /* main */

void Menu(int *choice)
{
int num;
printf(" Enter 1 to add item, 2 to remove item ");
printf(" 3 to print queue 4 sort 5 to quit ");
scanf("%d", &num);
*choice = num;
}

listelement *AddItem(listelement *listpointer, int data)
{
// Notice the use of "->" instead of "." for accessing elements of a
// structure. Pointers access elements via ->, whereas a normal
// variable of a structure would access them via a .
if (listpointer != EMPTY)
{
    listelement *lp = listpointer;
    while (listpointer->next != EMPTY)
    { listpointer = listpointer->next; }
    //listpointer->next = (struct listelement_struct *) malloc(sizeof(listelement)); // SAME AS BELOW
    listpointer->next = (listelement *) malloc(sizeof(listelement));
    listpointer = listpointer->next;
    listpointer->next = EMPTY;
    listpointer->dataitem = data;
    return lp;
}
else
{
    //listpointer = (struct listelement_struct *) malloc(sizeof(listelement)); // SAME AS BELOW
    listpointer = (listelement *) malloc(sizeof(listelement));
    listpointer->next = EMPTY;
    listpointer->dataitem = data;
    return listpointer;
}
}

listelement *RemoveItem(listelement *listpointer)
{
listelement *tempp;
printf(" Element removed is %d ", listpointer->dataitem);
tempp = listpointer->next;
free(listpointer);
return tempp;
}

void PrintQueue(listelement *listpointer)
{
if (listpointer == EMPTY)
{ printf(" queue is empty! "); }
else
{
    printf(" Queue Contents: ");
    while (listpointer != EMPTY)
    {
      printf("%d ", listpointer->dataitem);
      listpointer = listpointer->next;
    }
}
printf(" ");
}

void ClearQueue(listelement *listpointer)
{
while (listpointer != EMPTY)
{
    listpointer = RemoveItem(listpointer);
}
}
void bubbleSort(listelement *start)
{
    int swapped, i;
    listelement *ptr1;
    listelement *lptr = NULL;

    /* Checking for empty list */
    if (start == NULL)
        return;

    do
    {
        swapped = 0;
        ptr1 = start;

        while (ptr1->next != lptr)
        {
            if (ptr1->dataitem > ptr1->next->dataitem)
            {
                swap(ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    }
    while (swapped);
}

/* function to swap data of two nodes a and b*/
void swap(listelement *a, listelement *b)
{
    int temp = a->dataitem;
    a->dataitem = b->dataitem;
    b->dataitem = temp;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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