CS_8251 - Unit 2 - Selection Sort

The Selection Sort (the algorithm, associated code in C language) is presented using a well designed set of byte-sized 30 flashcards. It delivers an incremental-style learning that avoids high cognitive load, maximizes completion, and eventually "sticks".

30 flashcards · Programming Languages · by kgashok

1. The valid indexes range from 0 to 14 for a string of size 15. True of False?

   True

2. char *string1 = "Hello"; char *string2 = "Hello"; if (string1 == string2) func_call(); Will the function func_call get called?

   No. Unless == has been explicitly overloaded, this is the wrong way to compare the value of two strings. What is really being compared here are the values of the two pointers. To compare the values of the strings (which is much more likely to be what is wanted), use strcmp. The error is classified as a "model" error, since the user may well have a wrong model about what == can do.

3. The function used to compare two strings is strcmp

   takes two arguments

4. int res = strcmp("abcd", "abcd"); res will have the value 0. True or False?

   True

5. int res = strcmp("abcda", "abcde"); res will have negative value. True or False?

   True

6. int res = strcmp("abcdz", "abcde"); res will have positive value. True or False?

   True

7. int res = strcmp("english", "tamil"); res will have positive value. True or False?

   False

8. The output for the above program is: Choice A -1 -1 1 0 Choice B 1 -1 1 0 Choice C 0 1 1 0 Choice D 1 -1 1 1

   Choice B "abcde" is longer than "abcd", so strcmp returns 1 "abc" is shorter than "abcde", so strcmp returns -1 "abcdz" is after "abcde", so strcmp returns 1 Both are same, so strcmp returns 0

9. int res4 = strcmp("english", "Tamil"); int res6 = strcmp("11", "12"); int res7 = strcmp("110", "12"); The value of res4, res6 and res7 is 1, -1, -1 1, -1, 1 -1, -1, 1 None of the above

   Choice 1

10. What are the values returned by the following Python expressions? print(4 < 5 < 50) print("Tamil" < "english" < "tamil")

    True True Go to https://repl.it/@ashokb/ascendingValues and press "Run" to evaluate the expressions. Try out some of your own strings and see what values you get. In contrast, strcmp can only compare two strings lexicographically. It returns -1 (less than 0) when first string is "less" than second string 0 if both first and second values are equal +1 (more than 0) when first string is "greater" than second string

11. The code snippet for swapping two character arrays in C is given below: If you run this in the PythonTutor, you will get the following image: True or False?

    False To swap two character arrays, you will need to use another temporary character array. The correct code snippet will be as follows:

12. Is it possible to swap the values in two integer variables without using a temporary variable? Write the code snippet, assuming a and b are the two variables. CLUE: Use the XOR operator.

    Yes. a = a ^ b; b = b ^ a; a = a ^ b;

13. One of the most simplest algorithms for sorting is selectionsort. True or False?

    True

14. The following pseudo code represents Selection Sort algorithm. True or False?

    True

15. The unsorted array given is [2, 4, 0, 3]. When SelectionSort processes the list, the contents of the array at the end of each iteration of the inner loop is as follows: True or False?

    True

16. The unsorted array given is [4, 3, 2, 1]. What will the contents of the array be at the end of each iteration of the inner loop of a SelectionSort run?

17. mindx is the index of the lexicographically smallest string in the array so far. i is the index of the current string being evaluated in the iteration of a selectionsort function. if (strcmp(array[i], array[mindx]) < 0) { mindx = i; } The above code will update mindx appropriately. True or False?

    True It is correct. When in doubt, check with an actual test case. strcmp("english", "tamil") == -1 , then the expression will evaluate to less than 0 and so mindx will get updated with the index of "english".

18. mindx is the index of the lexicographically smallest string in the array so far. i is the index of the current string being evaluated in the iteration of a selectionsort function. if (strcmp(array[mindx], array[i]) > 0) { mindx = i; } The above code will update mindx appropriately. True or False?

    True It is correct. When in doubt, check with an actual test case. strcmp("tamil", "english") == 1 , then the expression will evaluate to greater than 0 and so mindx will get updated with the index of "english".

19. maxdx is the index of the lexicographically greatest string in the array so far. i is the index of the current string being evaluated in the iteration of a selectionsort function that needs to be sorted in descending order. Fill in the blanks below: if (strcmp(array[i], array[maxdx]) > 0) // what is the operator? { // which index goes where? maxdx = i; }

    Think carefully - and will get it right!

20. The function used to copy from one string to another is strcpy

    takes two arguments

21. The C function that performs ascending order SelectionSort on an array of strings is as follows: True or False?

    True

22. The C function that performs descending order SelectionSort on an array of strings is as follows: True or False?

    False. Requires one character change (symbol) associated with strcmp :

23. Write the minimum code that is required for a valid C program.

24. You have to write a program that can read a maximum of 1000 names, each containing a maximum of 30 letters in each name. Define names appropriately in C so that it is suitable for the above program. ---- CLUE: names - is a single dimensional array or two-dimensional array?

    char names[1000][30]; names has to be a two-dimensional array.

25. You have to write a program that can read a maximum of 40 address locations, each containing a maximum of 2000 characters in each location. Define address appropriately in C so that it is suitable for the above program.

    char address[40][2000]; address has to be a two-dimensional array.

26. Enter a program that reads strings from the standard input and prints the same to standard output. The program must be able to read a maximum of 100 strings, each containing a maximum of 30 characters. CLUE: Use scanf and printf.

27. Write a function that performs selectionsort on an array of strings. It must accept an appropriate two-dimensional character array and an integer representing the size of the array.

28. Write a full C program that implements a selectionsort of an array of strings.

29. begin Sort1 list : array of items n : size of list for i from 0 to n for j from i+1 to n if list[j] < list[i]: swap list[j] and list[i] end if end for end Sort1 Sort_1 goes by the name QuickSort InsertionSort BubbleSort SelectionSort

    Choice 3. The usual confusion is between BubbleSort and SelectionSort.

30. begin Sort2 list : array of items n : size of list for i from 0 to n-1 set indexMin = i for j from i+1 to n if list[j] < list[indexMin]: indexMin = j end if # swap only if necessary! if indexMin != i then swap list[indexMin] and list[i] end if end for end Sort2 Sort_2 goes by the name QuickSort InsertionSort BubbleSort SelectionSort

    Choice 4 SelectionSort improves on the BubbleSort in that swapping is only done (n-1) times at the most.