Реализация 3-way quicksort

Я новичок в алгоритмах, и я смущен относительно того, где ошибки в моем коде, которые я пишу как назначение. Я пытаюсь реализовать алгоритм быстрой сортировки в Python 3, который имеет дело с равными значениями в массиве.Реализация 3-way quicksort

Вот функция быстрой сортировки (а обозначает массив):

def randomized_quick_sort(a, l, r): 
    if l >= r: 
     return 
    k = random.randint(l, r) 
    a[l], a[k] = a[k], a[l] 
    m1, m2 = partition3(a, l, r) 
    randomized_quick_sort(a, l, m1 - 1); 
    randomized_quick_sort(a, m2 + 1, r);

И вот моя статсумма:

def partition3(a, l, r): 
    x, j, t = a[l], l, r 
    for i in range(l + 1, r + 1): 
     if a[i] < x: 
      j +=1 
      a[i], a[j] = a[j], a[i] 
     elif a[i] > x: 
      a[i], a[t] = a[t], a[i] 
      t -=1 
     else: 
      j +=1 
    a[l], a[j] = a[j], a[l] 
    return j, t

источник

2016-05-01 Elen

Я бы порекомендовал заменить «3-way» на «stable» в названии или полностью удалить его. Все виды принципиально меньше, равны, больше. Некоторые алгоритмы сортировки поддерживают порядок элементов, когда элементы равны, которые называются «стабильными» реализациями сортировки. 3-way заставляет меня думать о 3-way diffing или сортировать 3 отдельных списка в более эффективной реализации, чем объединять 3 списка в один список и сортировать их. – IceArdor

@ IceArdor: Я уверен, что Elen ссылается на 3-way _partitioning_ («проблема голландского национального флага» (https://en.wikipedia.org/wiki/Dutch_national_flag_problem) »). Из Википедии: «В частности, варианты алгоритма [quicksort] (https://en.wikipedia.org/wiki/Quicksort), которые должны быть надежными для повторяющихся элементов, нуждаются в трехсторонней функции секционирования, которая группирует элементы, (красный), равный ключу (белый) и больше, чем ключ (синий). " –

Вот мертвая простая реализация быстрой сортировки в питоне. Несмотря на то, что все еще существует nlogn, существует целая серия оптимизаций производительности, которые могут быть сделаны. Например, разбиение на менее, равное, большее может быть выполнено за один проход вместо 3 проходов массива.

def qsort(arr): 
    if len(arr) <= 1: return arr 
    pivot = arr[0] 
    less = [x for x in arr if x < pivot] 
    equal = [x for x in arr if x == pivot] 
    greater = [x for x in arr if x > pivot] 
    return qsort(less) + equal + qsort(greater)

Чтобы сделать этот раздел произойти за один проход массива, сделать вспомогательную функцию, как следует:

def partition(arr, pivot): 
    less, equal, greater = [], [], [] 
    for val in arr: 
     if val < pivot: less.append(val) 
     if val == pivot: equal.append(val) 
     if val > pivot: greater.append(val) 
    return less, equal, greater 

def qsort(arr): 
    if len(arr) <= 1: return arr 
    pivot = arr[0] 
    less, equal, greater = partition(arr, pivot) 
    return qsort(less) + equal + qsort(greater)

источник

2016-05-01 22:36:30 gnicholas

Хотя ваш код является читаемой реализацией алгоритма быстрой сортировки, он не является сортировкой на месте и возвращает новый список, а не оригинальный. –

Вы совершенно правы! И после реализации (более простого и более элегантного) случая возвращения нового списка дело с изменением исходного списка может быть выполнено проще. Если вы исходите из фона функционального программирования, мутирующие списки уродливы и должны выполняться только тогда, когда необходима оптимизация производительности. – gnicholas

Огромное спасибо @gnicholas за действительно страшное и прекрасное решение (в то время это немного выше меня)! Тем не менее, мне нужно оставаться в рамках функции, которая была предоставлена мне, поэтому я просил помочь мне найти ошибки. – Elen

Вы должны исправить вашу функцию раздела:

Вот рабочий пример:

def partition3(a, l, r): 
    x, j, t = a[l], l, r 
    i = j 

    while i <= t : 
     if a[i] < x: 
     a[j], a[i] = a[i], a[j] 
     j += 1 

     elif a[i] > x: 
     a[t], a[i] = a[i], a[t] 
     t -= 1 
     i -= 1 # remain in the same i in this case 
     i += 1 
    return j, t

источник

2016-05-01 22:40:59

Спасибо вам большое! Я ввернул перегородки в порядке, теперь я вижу это ясно. – Elen

Другая реализация с петлей

def partition3(a, l, r): 
    x = a[l] 
    m1 = l 
    m2 = l 
    i = m1 
    for i in range(l + 1, r + 1): 
     if a[i] < x: 
      a[i], a[m1] = a[m1], a[i] 
      a[i], a[m2+1] = a[m2+1], a[i] 
      m1 += 1 
      m2 += 1 
     elif a[i] == x: 
      a[i], a[m2+1] = a[m2+1], a[i] 
      m2 += 1 
    return m1, m2

источник

2017-11-03 07:54:06

ответ

Смежные вопросы