Question 10 in Fall 2015 Final Exam (Intermediate)

Consider the following C struct and typedef declarations:

struct studentRecord {
  char *name;
  double GPA;
};
typedef struct studentRecord Record;

Write a complete C function bubbleSortRecords, for which the prototype is given below, that uses the bubble sort algorithm to sort an array of n elements of type Record. The function should sort the elements in ascending order of GPA, and in the event of a tie, should break ties in alphabetical order of name, where name is a pointer to a string. You may use a function from the string library, string.h, in your answer. Hint: use the library function to compare two strings.

void bubbleSortRecords(Record records[], int n);

My solution

...

Question 11 in Winter 2019 Final Exam (Challenging)

In general, the bubble sort algorithm can be explained in two steps.

1. For each pair of adjacent elements: if they are out-of-order, then swap.
2. Repeat the first step until no swaps are done.

Write a function, bubbleSortLinkedList, that sorts a linked list using the bubble sort algorithm. The function has one parameter: a pointer to a LinkedList (assume that this pointer is not NULL). The function will modify the linked list in-place so that the values are in ascending order (i.e., 1 comes before 2). The definitions for a LinkedList and Node are shown below.

You must abide by the following constraints. Failure to meet a constraint will result in a grade of zero for this question.

1. Your function must not modify the next pointer of any node.
2. You cannot create any other data structures (e.g., an array, another linked list, etc.).
3. Your function cannot call any other functions.
4. Your function must not cause a segmentation fault.

typedef struct node {
  int data;
  struct node *next;
} Node;
typedef struct linkedList {
  Node *head;
} LinkedList;

My solution

void bubbleSortLinkedList(LinkedList *list) {
	// sorts LinkedList using bubble sort
	int numSwaps = 0;
	while (numSwaps > 0) {
		numSwaps = 0;
		Node *current = list->head;
		while (current != NULL && current->next != NULL) {
			if (current->data > current->next->data) {
				// sorting condition
				int tmp = current->next->data;
				current->next->data = current->data;
				current->data = tmp;
				++numSwaps;
			}
			current = current->next;
		}
		free(current);
	}
}