My quicksort algorithm works fine in sorting a list in place when the list contains individual items. For example '''
def quicksort(l):
if len(l) <= 1:
return l
pivot = l[0]
lower,upper = 1,1
#all elements from 1 to lower-1 is lower than or equal to the pivot
#all elements from lower to upper-1 is greater than pivot
for i in range(1,len(l)):
if l[i] > pivot:
upper += 1
else:
l[i],l[lower] = l[lower],l[i]
upper += 1
lower += 1
l[0],l[lower-1] = l[lower-1],l[0]
#pivot is now at index lower-1
#recursive calls to left of the pivot and to the right of the pivot
quicksort(l[:lower-1])
quicksort(l[lower:])
q = [4,5,8,9,4,12]
quicksort(q)
print(q)
The resulting output is as expected:
[4, 4, 8, 9, 5, 12]
But when I try to sort a list which contains tuples on basis of a particular index of the tuple, the list isn't sorted in place. For example:
I have the list :
L = [('Ajay',1,'M'),('Ishan',4,'M'),('Priya',4,'F'),('Ravi',7,'M'),('Dheeraj',2,'M'),('Neha',3,'F'),('Akash',8,'M'),('Gauri',6,'F'),('Hema',0,'F'),('Rani',10,'F')]
and I sort it on the basis of index number 2 of each tuple, that is, I want all tuples which have 'F' at the 2nd index to come before the tuples which have 'M'.
I write the following code, modifying the original quicksort a bit:
def quicksort(l):
if len(l) <= 1:
return l
pivot = l[0][2]
lower,upper = 1,1
#all elements from 1 to lower-1 is lower than or equal to the pivot
#all elements from lower to upper-1 is greater than pivot
for i in range(1,len(l)):
if l[i][2] > pivot:
upper += 1
else:
l[i],l[lower] = l[lower],l[i]
upper += 1
lower += 1
l[0],l[lower-1] = l[lower-1],l[0]
#pivot is now at index lower-1
quicksort(l[:lower-1])
quicksort(l[lower:])
L = [('Ajay',1,'M'),('Ishan',4,'M'),('Priya',4,'F'),('Ravi',7,'M'),('Dheeraj',2,'M'),('Neha',3,'F'),('Akash',8,'M'),('Gauri',6,'F'),('Hema',0,'F'),('Rani',10,'F')]
quicksort(L)
print(L)
But what I get as output is
[('Rani', 10, 'F'), ('Ishan', 4, 'M'), ('Priya', 4, 'F'), ('Ravi', 7, 'M'), ('Dheeraj', 2, 'M'), ('Neha', 3, 'F'), ('Akash', 8, 'M'), ('Gauri', 6, 'F'), ('Hema', 0, 'F'), ('Ajay', 1, 'M')]
I don't understand why it works in one case and not in the other.
This line isn't doing what you seem to think it's doing:
quicksort(l[:lower-1])
That statement actually creates a new sub-list and then sorts that, it does not touch the original list. Ditto for sub-sub-lists and so on.
The only reason it works on your integer list is because that list becomes fully sorted on the first pass (which is modifying the original list) before any recursion takes place. If you change your original list to something that's a bit more unordered, you'll see that it fails as well:
[5, 9, 2, 8, 3, 7, 4, 6, 5] ->
[5, 2, 3, 4, 5, 7, 8, 6, 9]
You would be better off passing the entire (original) list in at each recursion level, and just specifying the upper and lower bounds for the section you want to sort. For example, something like this:
def quicksort(coll, start=None, end=None):
# Allow simpler call.
if start is None:
start, end = 0, len(coll)
# Recursion terminator - one-element range is sorted by definition.
if end - start <= 1:
return
# Pivot on first element in range, prepare new pivot position.
pivot = coll[start]
new_pos = start + 1
# Process every element in range (other than pivot).
for i in range(start + 1, end):
# Correctly allocate to below/above-pivot sections.
if coll[i] < pivot:
if i != new_pos:
coll[i], coll[new_pos] = coll[new_pos], coll[i]
new_pos += 1
# Make order below-pivot, pivot, above-pivot.
coll[start], coll[new_pos-1] = coll[new_pos-1], coll[start]
# Recursively sort areas below and above that pivot point.
quicksort(coll, start, new_pos)
quicksort(coll, new_pos, end)
test_data = [24, 21, 22, 23, 20, 25, 5, 9, 2, 8, 3, 37, 34, 6, 5]
print(test_data)
quicksort(test_data)
print(test_data)
You can see a few changes there, such as:
upper variable, since you only need the new position for the pivot to do the swaps and recursion.And, just for completeness, you can use the following (very similar) code for your tuple list:
def quicksort(coll, start=None, end=None):
# Allow simpler call.
if start is None:
start, end = 0, len(coll)
# Recursion terminator - one-element range is sorted by definition.
if end - start <= 1:
return
# Pivot on first element in range, prepare new pivot position.
pivot = coll[start][2]
#SPEC: pivot = (coll[start][2], coll[start][0], coll[start][1])
new_pos = start + 1
# Process every element in range (other than pivot).
for i in range(start + 1, end):
# Correctly allocate to below/above-pivot sections.
if coll[i][2] < pivot:
#SPEC: if (coll[i][2], coll[i][0], coll[i][1]) < pivot:
if i != new_pos:
coll[i], coll[new_pos] = coll[new_pos], coll[i]
new_pos += 1
# Make order below-pivot, pivot, above-pivot.
coll[start], coll[new_pos-1] = coll[new_pos-1], coll[start]
# Recursively sort areas below and above that pivot point.
quicksort(coll, start, new_pos)
quicksort(coll, new_pos, end)
test_data = [('Ajay',1,'M'),('Ishan',4,'M'),('Priya',4,'F'),('Ravi',7,'M'),('Dheeraj',2,'M'),('Neha',3,'F'),('Akash',8,'M'),('Gauri',6,'F'),('Hema',0,'F'),('Rani',10,'F')]
print(test_data)
quicksort(test_data)
print(test_data)
The results are as expected:
[('Ajay', 1, 'M'), ('Ishan', 4, 'M'), ('Priya', 4, 'F'),
('Ravi', 7, 'M'), ('Dheeraj', 2, 'M'), ('Neha', 3, 'F'),
('Akash', 8, 'M'), ('Gauri', 6, 'F'), ('Hema', 0, 'F'),
('Rani', 10, 'F')]
[('Rani', 10, 'F'), ('Priya', 4, 'F'), ('Neha', 3, 'F'),
('Gauri', 6, 'F'), ('Hema', 0, 'F'), ('Ajay', 1, 'M'),
('Akash', 8, 'M'), ('Ravi', 7, 'M'), ('Dheeraj', 2, 'M'),
('Ishan', 4, 'M')]
See the lines marked with a #SPEC: comment if you want to sort with multi-field keys (gender, then name, then value, in the example given).