Структуры данных и алгоритмы Python: быстрая сортировка

Поиск и сортировка в Python: упражнение 9 с решением

Напишите программу на Python для сортировки списка элементов с использованием алгоритма быстрой сортировки.
Примечание. Согласно Википедии «Быстрая сортировка - это сортировка сравнения, это означает, что она может сортировать элементы любого типа, для которых определено отношение« меньше »(формально, общий порядок). В эффективных реализациях это не стабильная сортировка, Это означает, что относительный порядок элементов одинаковой сортировки не сохраняется. Быстрая сортировка может работать на месте с массивом, требуя небольших дополнительных объемов памяти для выполнения сортировки. "

Пример решения :

Код Python:

def quickSort(data_list):
   quickSortHlp(data_list,0,len(data_list)-1)
def quickSortHlp(data_list,first,last):
   if first < last:
       splitpoint = partition(data_list,first,last)
       quickSortHlp(data_list,first,splitpoint-1)
       quickSortHlp(data_list,splitpoint+1,last)
def partition(data_list,first,last):
   pivotvalue = data_list[first]
   leftmark = first+1
   rightmark = last
   done = False
   while not done:
       while leftmark <= rightmark and data_list[leftmark] <= pivotvalue:
           leftmark = leftmark + 1
       while data_list[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1
       if rightmark < leftmark:
           done = True
       else:
           temp = data_list[leftmark]
           data_list[leftmark] = data_list[rightmark]
           data_list[rightmark] = temp
   temp = data_list[first]
   data_list[first] = data_list[rightmark]
   data_list[rightmark] = temp
   return rightmark
data_list = [54,26,93,17,77,31,44,55,20]
quickSort(data_list)
print(data_list)

Пример вывода:

 [17, 20, 26, 31, 44, 54, 55, 77, 93] 

Блок - схема:

Редактор кода Python:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите программу на Python для сортировки списка элементов с использованием алгоритма сортировки слиянием.
Далее: Написать программу Python Program для подсчета сортировки.