CODEWITHSUNDEEP
pythonalgorithmlistcounterquicksort
nanokuro
nanokuro

Reputation: 63

How to count swaps in a quicksort? (Python)

Hello I have this code and I don't know how to count how many exchanges it does :(

def quicksort(lista,izq,der):
i = izq
j = der
pivote = lista[(izq + der)//2]

while i <= j:
    while lista[i] < pivote:
        i += 1
    while pivote < lista[j]:
        j -= 1
    if i <= j:
        aux = lista[i]
        lista[i] = lista[j]
        lista[j] = aux
        i += 1
        j -= 1

if izq < j:
    quicksort(lista, izq, j);
if i < der:
    quicksort(lista, i, der);

So where can I put a counter that says me how many exchanges It does? Edit: I need that the function returns me that number and how many comparisons It does.

Upvotes: 0

Views: 2745

Answers (2)

R Sahu
R Sahu

Reputation: 206697

def quicksort(lista,izq,der):
   i = izq
   j = der
   pivote = lista[(izq + der)//2]

   swap_count = 0
   while i <= j:
      while lista[i] < pivote:
         i += 1
      while pivote < lista[j]:
         j -= 1
      if i <= j:
         aux = lista[i]
         lista[i] = lista[j]
         lista[j] = aux
         swap_count += 1
         i += 1
         j -= 1

   if izq < j:
      swap_count += quicksort(lista, izq, j)
   if i < der:
      swap_count += quicksort(lista, i, der)

   return swap_count

Upvotes: 1

Coffo
Coffo

Reputation: 46

Here's what I would do, if I'm understanding you right.

def quicksort(lista,izq,der):
  i = izq
  j = der
  swap_count = 0
  compare_count = 0
  pivote = lista[(izq + der)//2]

  while i <= j:
    while lista[i] < pivote:
      i += 1
    while pivote < lista[j]:
      j -= 1
    if i <= j:
      aux = lista[i]
      lista[i] = lista[j]
      lista[j] = aux
      swap_count += 1
      i += 1
      j -= 1
    compare_count += 1

  if izq < j:
    other_swap, other_compare = quicksort(lista, izq, j)
    swap_count += other_swap
    compare_count += other_compare
  if i < der:
    other_swap, other_compare = quicksort(lista, i, der)
    swap_count += other_swap
    compare_count += other_compare    

  return (swap_count, compare_count)

This way you add in the swaps and the compares of the recursive calls as you make them.

Upvotes: 0

Related Questions