CS_8251 - Unit 2 - Selection Sort

For students learning C programming. Selection Sort is presented via the flashcards.

21 flashcards · Programming Languages · by SAGAR PATEL

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

   True

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

   True

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

   True

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

   False

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

   True

6. The function used to compare two strings is strcmp

   takes two arguments

7. 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

8. The code snippet for swapping two character arrays in C is as follows: char *source = "first"; char *dest = "second"; strcpy(source, dest); strcpy(dest, source); 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: char *source = "first"; char *dest = "second"; char temp[30]; strcpy(temp, source); // temp <--- "first" strcpy(source, dest); // source <--- "second" strcpy(dest, temp); // dest <---"first"

9. 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;

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 unsorted array given is [2, 4, 0, 3]. When SelectionSort processes the list, the contents of the array at the end of the inner loop is follows: True or False?

    True

12. 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?

13. midx 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[midx]) < 0) { midx = i; } The above code will update midx 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 midx will get updated with the index of "english".

14. midx 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[midx], array[i]) > 0) { midx = i; } The above code will update midx 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 midx will get updated with the index of "english".

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

    True

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

    True

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

    takes two arguments

18. #include <stdio.h> #include <string.h> int main() { int res = strcmp("abcde", "abcd"); printf("%d ", res); int res2 = strcmp("abc", "abcde"); printf("%d ", res2); int res3 = strcmp("abcdz", "abcde"); printf("%d ", res3); int res5 = strcmp("english", "english"); printf("%d ", res5); return 0; } 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

19. midx 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 sort in descending order. Fill in the blanks below: if (strcmp(array[i], array[midx]) > 0) // what is the operator? { // which index goes where? midx = i; }

    Think carefully - and will get it right!

20. 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.

21. 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.