Рубрики

Программа Python для быстрой сортировки

Как и сортировка слиянием , QuickSort — это алгоритм «разделяй и властвуй». Он выбирает элемент как сводную и разделяет данный массив вокруг выбранной сводной. Существует много разных версий быстрой сортировки, которые выбирают сводную информацию по-разному.

  1. Всегда выбирайте первый элемент как опорный.
  2. Всегда выбирайте последний элемент как опорный (реализован ниже)
  3. Выберите случайный элемент как опорный.
  4. Выберите медиану как опору.

Ключевым процессом в быстрой сортировке является partition (). Цель разделов, заданная для массива и элемента x массива как pivot, поместить x в правильную позицию в отсортированном массиве и поместить все меньшие элементы (меньше x) перед x, а все большие элементы (больше x) после Икс. Все это должно быть сделано за линейное время.
Псевдокод для рекурсивной функции быстрой сортировки:

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

# Программа Python для реализации сортировки Quicksort

  
# Эта функция принимает последний элемент в качестве точки, мест
# элемент поворота в правильном положении в отсортированном
# массив, и все места меньше (меньше, чем сводная)
# слева от точки поворота и всех больших элементов справа
Количество точек разворота

def partition(arr,low,high):

    i = ( low-1 )         # индекс меньшего элемента

    pivot = arr[high]     # пивот

  

    for j in range(low , high):

  

        # Если текущий элемент меньше или

        # равно развороту

        if   arr[j] <= pivot:

          

            # индекс приращения меньшего элемента

            i = i+1 

            arr[i],arr[j] = arr[j],arr[i]

  

    arr[i+1],arr[high] = arr[high],arr[i+1]

    return ( i+1 )

  
# Основная функция, реализующая QuickSort
# arr [] -> Массив для сортировки,
# low -> Начальный индекс,
# high -> Конечный индекс

  
# Функция для быстрой сортировки

def quickSort(arr,low,high):

    if low < high:

  

        # pi - индекс разделения, теперь arr [p]

        # в нужном месте

        pi = partition(arr,low,high)

  

        # Отдельно сортировать элементы перед

        # раздел и после раздела

        quickSort(arr, low, pi-1)

        quickSort(arr, pi+1, high)

  
# Код драйвера для проверки выше

arr = [10, 7, 8, 9, 1, 5]

n = len(arr)

quickSort(arr,0,n-1)

print ("Sorted array is:")

for i in range(n):

    print ("%d" %arr[i]),

  
# Этот код предоставлен Мохитом Кумрой

Пожалуйста, обратитесь к полной статье на QuickSort для более подробной информации!

Рекомендуемые посты:

Программа Python для быстрой сортировки

0.00 (0%) 0 votes