Сортировка шелла питон код

ShellSort

Shell sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of ShellSort is to allow the exchange of far items. In Shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.

Step 1 − Start
Step 2 − Initialize the value of gap size. Example: h
Step 3 − Divide the list into smaller sub-part. Each must have equal intervals to h
Step 4 − Sort these sub-lists using insertion sort
Step 5 – Repeat this step 2 until the list is sorted.
Step 6 – Print a sorted list.
Step 7 – Stop.

Pseudocode :

PROCEDURE SHELL_SORT(ARRAY, N)
WHILE GAP < LENGTH(ARRAY) /3 :
GAP = ( INTERVAL * 3 ) + 1
END WHILE LOOP
WHILE GAP > 0 :
FOR (OUTER = GAP; OUTER < LENGTH(ARRAY); OUTER++):
INSERTION_VALUE = ARRAY[OUTER]
INNER = OUTER;
WHILE INNER > GAP-1 AND ARRAY[INNER – GAP] >= INSERTION_VALUE:
ARRAY[INNER] = ARRAY[INNER – GAP]
INNER = INNER – GAP
END WHILE LOOP
ARRAY[INNER] = INSERTION_VALUE
END FOR LOOP
GAP = (GAP -1) /3;
END WHILE LOOP
END SHELL_SORT

Following is the implementation of ShellSort.

C++

Java

Python3

C#

Javascript

Array before sorting: 12 34 54 2 3 Array after sorting: 2 3 12 34 54

Time Complexity: Time complexity of the above implementation of Shell sort is O(n 2 ). In the above implementation, the gap is reduced by half in every iteration. There are many other ways to reduce gaps which leads to better time complexity. See this for more details.

Worst Case Complexity
The worst-case complexity for shell sort is O(n 2 )
Best Case Complexity
When the given array list is already sorted the total count of comparisons of each interval is equal to the size of the given array.
So best case complexity is Ω(n log(n))
Average Case Complexity

The shell sort Average Case Complexity depends on the interval selected by the programmer.
θ(n log(n)2).

THE Average Case Complexity: O(n*log n)~O(n 1.25 )
Space Complexity
The space complexity of the shell sort is O(1).

Questions:

1. Which is more efficient shell or heap sort?

Ans. As per big-O notation, shell sort has O(n^) average time complexity whereas, heap sort has O(N log N) time complexity. According to a strict mathematical interpretation of the big-O notation, heap sort surpasses shell sort in efficiency as we approach 2000 elements to be sorted.
Note:- Big-O is a rounded approximation and analytical evaluation is not always 100% correct, it depends on the algorithms’ implementation which can affect actual run time.

Shell Sort Applications

1. Replacement for insertion sort, where it takes a long time to complete a given task.
2. To call stack overhead we use shell sort.
3. when recursion exceeds a particular limit we use shell sort.
4. For medium to large-sized datasets.
5. In insertion sort to reduce the number of operations.

Quiz on Shell Sort

Other Sorting Algorithms on GeeksforGeeks/GeeksQuiz:

Solve DSA problems on GfG Practice.

Источник

Алгоритмы сортировки на Python

В этой статье мы вкратце расскажем, какие есть основные алгоритмы сортировки и каковы их главные характеристики. Также по каждому алгоритму покажем реализацию на Python.

Искусство наведения порядка

Сортировка означает размещение элементов в определенном порядке. Этот конкретный порядок определяется свойством сравнения элементов. В случае целых чисел мы говорим, что сначала идет меньшее число, а потом — большее.

Расположение элементов в определенном порядке улучшает поиск элемента. Следовательно, сортировка широко используется в информатике.

В данной статье мы рассмотрим обычные алгоритмы сортировки и их реализации на Python. Для сравнения их производительности мы будем рассматривать задачу с сайта Leetcode о сортировке массива. Размеры данных этой задачи ограничены следующим образом:

Мы решили эту задачу при помощи всех известных алгоритмов сортировки. Вот какие у нас получились результаты:

Сортировка методом пузырька

Это самый простой алгоритм сортировки. В процессе его выполнения мы перебираем наш список и на каждой итерации сравниваем элементы попарно. При необходимости элементы меняются местами, чтобы больший элемент отправлялся в конец списка.

• нерекурсивный;
• устойчивый;
• преобразует входные данные без использования вспомогательной структуры данных (in place);
• имеет сложность O(n 2 );

def bubbleSort(array): swapped = False for i in range(len(array)-1,0,-1): for j in range(i): if array[j]>array[j+1]: array[j], array[j+1] = array[j+1], array[j] swapped= True if swapped: swapped=False else: break return array

Сортировка выбором

В этом алгоритме мы создаем два сегмента нашего списка: один отсортированный, а другой несортированный.

В процессе выполнения алгоритма мы каждый раз удаляем самый маленький элемент из несортированного сегмента списка и добавляем его в отсортированный сегмент. Мы не меняем местами промежуточные элементы. Следовательно, этот алгоритм сортирует массив с минимальным количеством перестановок.

• нерекурсивный;
• может быть как устойчивым, так и неустойчивым;
• преобразует входные данные без использования вспомогательной структуры данных (in place);
• имеет сложность O(n 2 );

def selectionSort(array): for i in range(len(array)-1): min_idx = i for idx in range(i + 1, len(array)-1): if array[idx] < array[min_idx]: min_idx = idx array[i], array[min_idx] = array[min_idx], array[i] return array

Сортировка вставками

Подобно алгоритму сортировки выбором, мы делим наш список на две части. Далее мы перебираем неотсортированную часть и вставляем каждый элемент из данного сегмента на его правильное место в отсортированной части списка.

• нерекурсивный;
• устойчивый;
• преобразует входные данные без использования вспомогательной структуры данных (in place);
• имеет сложность O(n 2 );

def insertionSort(array): for i in range(1, len(array)): key = array[i] j = i-1 while array[j] > key and j >= 0: array[j+1] = array[j] j -= 1 array[j+1] = key return array

Сортировка Шелла

Сортировка Шелла является оптимизированным вариантом сортировки вставками.

Оптимизация достигается путем сравнения не только соседних элементов, но и элементов на определенном расстоянии, которое в течении работы алгоритма уменьшается. На последней итерации это расстояние равно 1. После этого алгоритм становится обычным алгоритмом сортировки вставками, что гарантирует правильный результат сортировки.

Но следует отметить один момент: к тому времени, когда это произойдет, наш массив будет почти отсортирован, поэтому итерации будут выполнятся очень быстро.

• нерекурсивный;
• устойчивый;
• преобразует входные данные без использования вспомогательной структуры данных (in place);
• имеет сложность O(n 2 ), но это также зависит от выбора длины интервала;

def shellSort(array): n = len(array) k = int(math.log2(n)) interval = 2**k -1 while interval > 0: for i in range(interval, n): temp = array[i] j = i while j >= interval and array[j - interval] > temp: array[j] = array[j - interval] j -= interval array[j] = temp k -= 1 interval = 2**k -1 return array

Пирамидальная сортировка («сортировка кучей»)

Как и в двух предыдущих алгоритмах, мы создаем два сегмента списка: отсортированный и несортированный.

В данном алгоритме для эффективного нахождения максимального элемента в неотсортированной части списка мы используем структуру данных «куча».

Метод heapify в примере кода использует рекурсию для получения элемента с максимальным значением на вершине.

• нерекурсивный;
• неустойчивый;
• преобразует входные данные без использования вспомогательной структуры данных (in place);
• имеет сложность O(nlog(n));

def heapify(array, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and array[i] < array[l]: largest = l if r < n and array[largest] < array[r]: largest = r if largest != i: array[i], array[largest] = array[largest], array[i] heapify(array, n, largest) def heapSort(array): n = len(array) for i in range(n//2, -1, -1): heapify(array, n, i) for i in range(n-1, 0, -1): array[i], array[0] = array[0], array[i] heapify(array, i, 0) return array

Сортировка слиянием

Этот алгоритм работает по принципу «разделяй и властвуй».

Здесь мы делим список ровно пополам и продолжаем это делать, пока в нем не останется только один элемент. Затем мы объединяем уже упорядоченные части нашего списка. Мы продолжаем это делать, пока не получим отсортированный список со всеми элементами несортированного входного списка.

• рекурсивный;
• устойчивый;
• требует дополнительной памяти;
• имеет сложность O(nlog(n));

def mergeSort(nums): if len(nums)==1: return nums mid = (len(nums)-1) // 2 lst1 = mergeSort(nums[:mid+1]) lst2 = mergeSort(nums[mid+1:]) result = merge(lst1, lst2) return result def merge(lst1, lst2): lst = [] i = 0 j = 0 while(ilen(lst1)-1: while(j<=len(lst2)-1): lst.append(lst2[j]) j+=1 else: while(i<=len(lst1)-1): lst.append(lst1[i]) i+=1 return lst

Быстрая сортировка

В этом алгоритме мы разбиваем список при помощи опорного элемента, сортируя значения вокруг него.

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

• рекурсивный;
• неустойчивый;
• преобразует входные данные без использования вспомогательной структуры данных (in place);
• имеет сложность O(nlog(n));

def quickSort(array): if len(array)> 1: pivot=array.pop() grtr_lst, equal_lst, smlr_lst = [], [pivot], [] for item in array: if item == pivot: equal_lst.append(item) elif item > pivot: grtr_lst.append(item) else: smlr_lst.append(item) return (quickSort(smlr_lst) + equal_lst + quickSort(grtr_lst)) else: return array

Сортировка подсчетом

Этот алгоритм не производит сравнение элементов. Для сортировки используются математические свойства целых чисел. Мы подсчитываем вхождения числа в массиве и сохраняем результат во вспомогательном массиве, где индексу соответствует значение ключа.

• нерекурсивный;
• устойчивый;
• преобразует входные данные без использования вспомогательной структуры данных (in place), но все же требует дополнительной памяти;
• имеет сложность O(n);

def sortArray(self, nums: List[int]) -> List[int]: i_lower_bound , upper_bound = min(nums), max(nums) lower_bound = i_lower_bound if i_lower_bound < 0: lb = abs(i_lower_bound) nums = [item + lb for item in nums] lower_bound , upper_bound = min(nums), max(nums) counter_nums = [0]*(upper_bound-lower_bound+1) for item in nums: counter_nums[item-lower_bound] += 1 pos = 0 for idx, item in enumerate(counter_nums): num = idx + lower_bound for i in range(item): nums[pos] = num pos += 1 if i_lower_bound < 0: lb = abs(i_lower_bound) nums = [item - lb for item in nums] return nums

Следует также упомянуть поразрядную сортировку, которая использует сортировку подсчетом либо блочную (корзинную) сортировку в качестве подпрограммы. Этот метод сортировки заслуживает отдельной статьи для разбора.

Для удобства соберем весь наш код вместе:

class Solution: def sortArray(self, nums: List[int]) -> List[int]: # Сортировка пузырьком def bubbleSort(array): swapped = False for i in range(len(array)-1,0,-1): for j in range(i): if array[j]>array[j+1]: array[j], array[j+1] = array[j+1], array[j] swapped= True if swapped: swapped=False else: break return array # Сортировка вставками def insertionSort(array): for i in range(1, len(array)): key = array[i] j = i-1 while array[j] > key and j >= 0: array[j+1] = array[j] j -= 1 array[j+1] = key return array # Сортировка выбором def selectionSort(array): for i in range(len(array)-1): min_idx = i for idx in range(i + 1, len(array)-1): if array[idx] < array[min_idx]: min_idx = idx array[i], array[min_idx] = array[min_idx], array[i] return array # Пирамидальная сортировка def heapify(array, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and array[i] < array[l]: largest = l if r < n and array[largest] < array[r]: largest = r if largest != i: array[i], array[largest] = array[largest], array[i] heapify(array, n, largest) def heapSort(array): n = len(array) for i in range(n//2, -1, -1): heapify(array, n, i) for i in range(n-1, 0, -1): array[i], array[0] = array[0], array[i] heapify(array, i, 0) return array # Сортировка слиянием def mergeSort(nums): if len(nums)==1: return nums mid = (len(nums)-1) // 2 lst1 = mergeSort(nums[:mid+1]) lst2 = mergeSort(nums[mid+1:]) result = merge(lst1, lst2) return result def merge(lst1, lst2): lst = [] i = 0 j = 0 while(ilen(lst1)-1: while(j <=len(lst2)-1): lst.append(lst2[j]) j+=1 else: while(i<=len(lst1)-1): lst.append(lst1[i]) i+=1 return lst # Быстрая сортировка def quickSort(array): if len(array)>1: pivot=array.pop() grtr_lst, equal_lst, smlr_lst = [], [pivot], [] for item in array: if item == pivot: equal_lst.append(item) elif item > pivot: grtr_lst.append(item) else: smlr_lst.append(item) return (quickSort(smlr_lst) + equal_lst + quickSort(grtr_lst)) else: return array # Сортировка Шелла def shellSort(array): n = len(array) interval = n // 2 while interval > 0: for i in range(interval, n): temp = array[i] j = i while j >= interval and array[j - interval] > temp: array[j] = array[j - interval] j -= interval array[j] = temp interval //= 2 return array #nums = bubbleSort(nums) #nums = insertionSort(nums) #nums = selectionSort(nums) #nums = heapSort(nums) #nums = mergeSort(nums) #nums = quickSort(nums) return nums

Испытав все эти алгоритмы, мы ради любопытства запустили встроенную в Python функцию sorted() . Она показала весьма быстрое время в 152 мс. В данной функции используется алгоритм Timsort, который сочетает в себе сортировку слиянием и сортировку вставками. Реализация данного алгоритма также может быть рассмотрена в отдельной статье.

Мы нашли потрясающий плейлист, в котором алгоритмы сортировки демонстрируются при помощи народного танца. Посмотрите это видео, оно того стоит!

Источник