I am solving the following code challenge:
Let N be the size of a list. Implement the Selection Sort algorithm with the following modifications:
- In odd iterations, find the element with the lowest value and place it in the location adequate.
- In even iterations, find the element with the highest value and place it in the location adequate. With each iteration, print the state of the list. Perform N – 1 iterations.
The input is composed of two lines, the first with the list size and the second with the list elements.
This is my code:
def ordenacao_por_selecao_modificada(arr):
n = len(arr)
for i in range(1,n):
if i % 2 == 0:
# Nas iterações pares, encontre o elemento com o maior valor
indice_maior = i
for j in range(i, len(arr)):
if arr[j] > arr[indice_maior]:
indice_maior = j
print(lista)
arr[i],arr[indice_maior] = arr[indice_maior],arr[i]
else:
# Nas iterações ímpares, encontre o elemento com o menor valor
indice_menor = i
for j in range(i, n):
if arr[j] < arr[indice_menor]:
indice_menor = j
print(lista)
arr[i], arr[indice_menor] = arr[indice_menor], arr[i]
lista = [8, 2, 5, 1, 10, 4]
ordenacao_por_selecao_modificada(lista)
When I make the implementation change between odd or even, I can get the expected result, however, when I add the condition, the results are still out of order after each change.
An example of the output with checking for even or odd:
[1, 2, 5, 8, 10, 4]
[1, 10, 5, 8, 2, 4]
[1, 10, 2, 8, 5, 4]
[1, 10, 2, 8, 5, 4]
[1, 10, 2, 8, 4, 5]
The list should be sorted at the end. What is my mistake?
The main mistake is that i is not the place where the swap must occur:
It should be a completely different index in odd iterations than in even iterations. In odd iterations that index should be 0 (for first iteration), 1 (for third iteration), 2 (for fifth iteration), ... And for even iterations that index should n 𝑛−1 (for second iteration), 𝑛−2 (for fourth iteration), ...etc, so this is generally not the value of i
You should also adapt the range to search for the minimum/maximum. As iterations occur, the right side of the array also gets a sorted segment, and so the search should not go all the way to the end of the array.
It will be easier if you maintain the leftmost and rightmost index of the segment that is not sorted yet. This window will get smaller and smaller as iterations are made.
Here is the corrected code:
def ordenacao_por_selecao_modificada(arr):
n = len(arr)
left = 0
right = n - 1
for i in range(1,n):
if i % 2 == 1:
indice_maior = right
for j in range(left, right + 1):
if arr[j] > arr[indice_maior]:
indice_maior = j
print(lista)
arr[right], arr[indice_maior] = arr[indice_maior], arr[right]
right -= 1
else:
indice_menor = left
for j in range(left, right + 1):
if arr[j] < arr[indice_menor]:
indice_menor = j
print(lista)
arr[left], arr[indice_menor] = arr[indice_menor], arr[left]
left += 1