0
$\begingroup$

This is a homework question. I have been asked to identify what sort this code below implements.

sort(arr of length n, left, right):
  if (left > right): return 

  for i from 0 to n:
    if i >= right and arr[left] > arr[i]:
      left = i

  swap(arr, left, right)
  left = right
  right = right + 2
  if (right < n):
    sort(arr, left + 1, right - 1)
    sort(arr, right - 1, left)

sort(arr):
    sort(arr, 0, 0)

After writing the code's trace on paper, I've come to think that it's a selection sort because from the original table [50, 15, 33, 27, 89, 12, 18] after passing one time through it we obtain [12, 15, 33, 27, 89, 50, 18]. We looked for the smallest element in the table and then put it first. this seems like the typical behavior of selection sort.

I want to confirm if I am right or wrong because I do not have access to the solution of the problem.

$\endgroup$
  • $\begingroup$ It does appear that the algorithm finds the smallest element at each iteration and swaps it forward. Though you may want to determine how right relates to all of this. Consider what it means if the if condition within the for loop never gets hit. Also, it may be worth noting that just before the recursive calls we have right = left + 2, thus the recursive calls would just be sort(arr, left + 1, left + 1) and sort(left + 1, left). What's the difference in these calls? (Hint: one of them does nothing) $\endgroup$ – ryan Apr 15 '19 at 17:27
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. Perhaps a good next step for you would be to try a few more examples. $\endgroup$ – D.W. Apr 15 '19 at 17:36
  • $\begingroup$ I also took some liberties with editing the question to cut it down to the core. Feel free to change them if this is not what you meant. Also make sure to address D.W.'s comment. $\endgroup$ – ryan Apr 15 '19 at 17:38
  • $\begingroup$ Have you tried proving your suspicion? $\endgroup$ – Yuval Filmus Apr 15 '19 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.