Week 12 Laboratory — Sorting Algorithms

The focus of the lab this week is sorting on different data structures:

• For Exercise 1, you use code known from lectures as starting point. You need to add a function to implement selection sort on a linked list.
• For Exercise 2, you should use the same basic program from Exercise 1 and simply replace the sort function by an implementation of insertion sort.
• Exercise 3 is different as it uses the quack ADT. You will need to start from scratch here to implement selection sort using 2 stacks.

• Exercise 4 requires you to demonstrate to your tutor that you have completed Stage 2 of the assignment. You do not have submit any code for this exercise.

You can use dry run as usual:

prompt$ ~cs1921/bin/dryrun lab12

prompt$ ~cs1921/bin/dryrun lab12 2

Exercises

1. (Sorting, Linked lists) Download the main function of a program called llselsort.c. The functions that build, print and free a linked list are given; the function that implements selection sort on a linked list is missing. Complete this program without changing the main program.

   Note: For the testcases shown below, we use a UNIX pipeline

   prompt$ prog1 | prog2

   In a pipeline, the output (on stdout) of the first program, prog1, feeds directly as input (on stdin) to the second program, prog2

   Use the following testcases:

   prompt$ echo 12 1 2 3 4 5 6 7 8 9 10 11 12 | ./llselsort Original list: 1->2->3->4->5->6->7->8->9->10->11->12 Sorted list: 1->2->3->4->5->6->7->8->9->10->11->12 prompt$ echo 12 12 11 10 9 8 7 6 5 4 3 2 1 | ./llselsort Original list: 12->11->10->9->8->7->6->5->4->3->2->1 Sorted list: 1->2->3->4->5->6->7->8->9->10->11->12 prompt$ echo 9 2 0 4 -8 6 -4 8 -6 -2 | ./llselsort Original list: 2->0->4->-8->6->-4->8->-6->-2 Sorted list: -8->-6->-4->-2->0->2->4->6->8 prompt$ echo 9 -6 -2 6 4 0 8 -8 2 -4 | ./llselsort Original list: -6->-2->6->4->0->8->-8->2->-4 Sorted list: -8->-6->-4->-2->0->2->4->6->8 prompt$ echo 9 8 6 4 2 0 -2 -4 -6 -8 | ./llselsort Original list: 8->6->4->2->0->-2->-4->-6->-8 Sorted list: -8->-6->-4->-2->0->2->4->6->8 prompt$ echo 2 -2 2 | ./llselsort Original list: -2->2 Sorted list: -2->2 prompt$ echo 1 2 | ./llselsort Original list: 2 Sorted list: 2

   If the data on stdin is incorrect then the following error messages should be generated:

   prompt$ echo | ./llselsort Missing data prompt$ echo a | ./llselsort Missing data prompt$ echo 2 1 | ./llselsort Missing data

   Your algorithm should be 'in-place' (so you may not create a second linked list or use some other data structure such as an array). You may also not use a doubly-linked list.

2. (Sorting, Linked lists) Replace the selection sort in the first exercise with insertion sort, and call the program llinsertsort.c. You can use exactly the same test cases.

   • Insertion sort is more challenging to implement on a linked list than selection sort. You might find it helpful to have your own test script with carefully chosen testcases so that you can see for which inputs your algorithm does and does not work. For example, create a file, called 'testinsert' say, that contains the commands:

   PROG=./llinsertsort echo 4 1 2 3 4 | $PROG echo 4 1 2 4 3 | $PROG echo 4 1 3 2 4 | $PROG echo 4 1 3 4 2 | $PROG echo 4 1 4 2 3 | $PROG echo 4 1 4 3 2 | $PROG echo 4 2 1 3 4 | $PROG echo 4 2 1 4 3 | $PROG echo 4 2 3 1 4 | $PROG echo 4 2 3 4 1 | $PROG echo 4 2 4 1 3 | $PROG echo 4 2 4 3 1 | $PROG echo 4 3 1 2 4 | $PROG echo 4 3 1 4 2 | $PROG echo 4 3 2 1 4 | $PROG echo 4 3 2 4 1 | $PROG echo 4 3 4 1 2 | $PROG echo 4 3 4 2 1 | $PROG echo 4 4 1 2 3 | $PROG echo 4 4 1 3 2 | $PROG echo 4 4 2 1 3 | $PROG echo 4 4 2 3 1 | $PROG echo 4 4 3 1 2 | $PROG echo 4 4 3 2 1 | $PROG

   Each line in this script is a testcase. You can run this script using the UNIX  sh  command, as follows:

   prompt$ sh testinsert

   The testcases in this script will exercise every part of your algorithm. Of course you can also use a test script in the other exercises as well, after changing the shell variable 'PROG' accordingly. You may also re-direct the output to a file using:

   prompt$ sh testinsert > testinsert.out

   As before, the sort algorithm in this exercise should be 'in-place' (so you may not create a second linked list or use some other data structure such as an array) and you may not use a doubly-linked list.

3. (Sorting, Stacks) Write a program called selsortQ.c that implements selection sort using just 2 stacks. You may not use any other data structure. An algorithm to do this (taken from the lecture) is the following:

   • Assume we have 2 stacks, A and B, and n unsorted numbers in stack A, and stack B is empty:
   • pop the n numbers from A and push onto B, but not the maximum number, which should be temporarily stored
   • (after this step is complete, A is empty, and B contains n-1 unsorted numbers)
   • push the stored maximum number onto A
   • pop everything from B and push back onto A
   • (after this step is complete, B is empty, and A contains n numbers, the top n-1 are unsorted)
   • let n = n-1 and repeat the steps above until n=1
   • (when complete, the stack A should contain the sorted elements and stack B should be empty)

   Naturally, this algorithm should be implemented using our Quack ADT. The input of your program should come from the command line. The numbers on the command line should be inserted into a stack to be processed as outlined above. It is recommended that you implement the selection sort in a function. The prototype of the function could be:

   void selectionSort(Quack sq, int num);

   where:
   • the stack sq has been populated with the command-line arguments beforehand and is the main stack (and plays the role of stack A in the algorithm above) and
   • num is the number of arguments.

   As you will be using 2 stacks, you will need to declare a second stack in this function (to play the role of B).

   The output of the program should be the main stack before and after the data has been sorted. Use the printQuack() function in the quack ADT for this purpose. Sample testcases are the following:

   prompt$ ./selsortQ 1 4 3 2 Original Quack: <<2, 3, 4, 1>> Sorted Quack: <<1, 2, 3, 4>>

   A reminder that the top of stack is on the left, so the first argument on the command line is initially at the bottom of the stack, and the last argument at the top. Once sorted, the minimum number is on the top of the stack, and the maximum at the bottom.

   prompt$ ./selsortQ 10 20 30 40 50 60 70 80 90 Original Quack: <<90, 80, 70, 60, 50, 40, 30, 20, 10>> Sorted Quack: <<10, 20, 30, 40, 50, 60, 70, 80, 90>>

   prompt$ ./selsortQ 10 -10 8 -8 6 -6 4 -4 2 -2 0 Original Quack: <<0, -2, 2, -4, 4, -6, 6, -8, 8, -10, 10>> Sorted Quack: <<-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10>>

   prompt$ ./selsortQ 12 345 14 16 18 9 7 5 33 1 17 21 2 3 4 19 18 Original Quack: <<18, 19, 4, 3, 2, 21, 17, 1, 33, 5, 7, 9, 18, 16, 14, 345, 12>> Sorted Quack: <<1, 2, 3, 4, 5, 7, 9, 12, 14, 16, 17, 18, 18, 19, 21, 33, 345>>

   If there is no argument on the command line:

   prompt$ ./selsortQ Original Quack: << >> Sorted Quack: << >>

   If there is any problem with reading the command line:

   prompt$ ./selsortQ 1 a 3 Error in arguments

   Finally, you are implementing the sort using stacks, not queues, hence you should not use the qush() command.

4. (Assignment) You should demonstrate to your tutor that you have completed Stage 2 of the assignment. Recall that this involves implementing the following commands:

   x: force exit h: print this help message p: print all lines .: print current line +: increment line and print <return>: same as '+' -: decrement line and print number: make 'number' the current line

   You are not required to submit any code for this exercise. However, you MUST demonstrate this during the lab to obtain the 2 marks for this exercise.

Submit the rest of your work using:

  give  cs1921  lab12  llselsort.c  llinsertsort.c  selsortQ.c