Быстрая сортировка python рекурсия

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

Идея быстрой сортировки была придумана информатиком Чарльзом Хоаром в 1960 году. Рассмотрим её преимущества над пузырьковой сортировкой и реализуем алгоритм в Python.

Одно из первых заданий программиста в любом языке программирования — разработка алгоритма сортировки массива. Большинство выбирает пузырьковый метод, то есть упорядочивание элементов после сравнения друг с другом. В Python это выглядит так:

nums = [4, 1, 6, 3, 2, 7, 8] n = 1 while n  len(nums): for i in range(len(nums) - n): if nums[i] > nums[i + 1]: nums[i], nums[i + 1] = nums[i + 1], nums[i] n += 1

Однако на практике он неэффективен, так как предполагает многократное прохождение по всему массиву. Альтернативный метод, впоследствии получивший название «быстрая сортировка», изобрел информатик Чарльз Хоар в 1960. Он предполагает деление массива на две части, в одной из которых находятся элементы меньше определённого значения, в другой – больше или равные. Рассмотрим реализацию в Python быстрой сортировки Хоара.

def quicksort(nums): if len(nums)  1: return nums else: q = random.choice(nums) s_nums = [] m_nums = [] e_nums = [] for n in nums: if n  q: s_nums.append(n) elif n > q: m_nums.append(n) else: e_nums.append(n) return quicksort(s_nums) + e_nums + quicksort(m_nums)

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

Впрочем, описанный алгоритм можно прокачать, сократив количество используемой памяти:

def quicksort(nums, fst, lst): if fst >= lst: return i, j = fst, lst pivot = nums[random.randint(fst, lst)] while i  j: while nums[i]  pivot: i += 1 while nums[j] > pivot: j -= 1 if i  j: nums[i], nums[j] = nums[j], nums[i] i, j = i + 1, j - 1 quicksort(nums, fst, j) quicksort(nums, i, lst)

В этом случае вы используете память только для организации рекурсии и в Python быстрая сортировка становится по-настоящему «быстрой». В заключении темы опишем на питоне сортировку Хоара в функциональном виде:

def quicksort(nums): if len(nums)  1: return nums else: q = random.choice(nums) l_nums = [n for n in nums if n  q] e_nums = [q] * nums.count(q) b_nums = [n for n in nums if n > q] return quicksort(l_nums) + e_nums + quicksort(b_nums)

Также важно упомянуть, что в питоне методов сортировки чисел в массиве – множество, практически в каждой библиотеке, предназначенной для работы с числами. Однако знать и понимать описанные – важно не только для общего развития, но и для прохождения собеседований. Там это один из самых популярных вопросов.

Источник

Quicksort implementation in Python

I’m trying to implement quicksort in python. However, my code doesn’t properly sort (not quite). For example, on the input array [5,3,4,2,7,6,1], my code outputs [1,2,3,5,4,6,7]. So, the end result interposes the 4 and 5. I admit I am a bit rusty on python as I’ve been studying ML (and was fairly new to python before that). I’m aware of other python implementations of quicksort, and other similar questions on Stack Overflow about python and quicksort, but I am trying to understand what is wrong with this chunk of code that I wrote myself:

#still broken 'quicksort' def partition(array): pivot = array[0] i = 1 for j in range(i, len(array)): if array[j] < array[i]: temp = array[i] array[i] = array[j] array[j] = temp i += 1 array[0] = array[i] array[i] = pivot return array[0:(i)], pivot, array[(i+1):(len(array))] def quick_sort(array): if len(array)  

6 Answers 6

I'm a little confused about what the algorithm's connection to quicksort is. In quicksort, you typically compare all entries against a pivot, so you get a lower and higher group; the quick_sort function clearly expects your partition function to do this.

However, in the partition function, you never compare anything against the value you name pivot. All comparisons are between index i and j, where j is incremented by the for loop and i is incremented if an item was found out of order. Those comparisons include checking an item against itself. That algorithm is more like a selection sort with a complexity slightly worse than a bubble sort. So you get items bubbling left as long as there are enough items to the left of them, with the first item finally dumped after where the last moved item went; since it was never compared against anything, we know this must be out of order if there are items left of it, simply because it replaced an item that was in order.

Thinking a little more about it, the items are only partially ordered, since you do not return to an item once it has been swapped to the left, and it was only checked against the item it replaced (now found to have been out of order). I think it is easier to write the intended function without index wrangling:

def partition(inlist): i=iter(inlist) pivot=i.next() low,high=[],[] for item in i: if item 

Источник

QuickSort in Python (Algorithm & Program)

QuickSort in Python (Algorithm & Program)

Sorting algorithms are essential for organizing data in computer science, and QuickSort is among the most well-known and efficient of these tools. This article examines QuickSort in Python, and its algorithm, with an emphasis on recursive implementation. We will also do sorting an array using user input with it.

What is QuickSort in Python?

Quicksort is a popular sorting algorithm that sorts an array using a divide-and-conquer strategy, which implies that it sorts an array by repeatedly dividing it into smaller subarrays and then sorting the subarrays recursively.

It is one of the most effective data-sorting algorithms available. It is typically faster than other sorting algorithms such as merge sort for large arrays. In practical applications, it outperforms other sorting algorithms such as Bubble Sort and Insertion Sort despite having a worst-case time complexity of O(n^2).

The basic idea behind the QuickSort algorithm is to divide an array into two subarrays, one containing all the elements smaller than the pivot element and the other containing all the elements larger than the pivot element.

Frequently, the median of the array serves as the pivot point. After the array has been partitioned, the QuickSort algorithm sorts the two subarrays recursively. All subarrays are emptied sequentially until the entire array is sorted.

QuickSort Algorithm

Listed below are the components of the QuickSort algorithm:

  1. A pivot element is used to divide a larger array into subarrays.
  2. When dividing the array in half, the pivot should be positioned such that elements smaller than the pivot are maintained on the left and elements larger than the pivot are maintained on the right.
  3. The same technique is used to separate the left and right subarrays.
  4. This procedure is repeated until every subarray contains a single value.
  5. Currently, the components have been sorted. The items are finally combined into a single sorted array.

The pseudo-code for the algorithm is as follows:

quicksort(arr) if length(arr)  1 return arr else pivot = arr[0] left = empty array right = empty array for each element x in arr[1:] if x  pivot append x to left else append x to right sorted_left = quicksort(left) sorted_right = quicksort(right) return sorted_left + [pivot] + sorted_right

QuickSort Program in Python

The implementation begins with a test to determine whether the length of the array is less than or equal to one. In this case, the array is already sorted, so it can be returned.

If not, the first element is used as a pivot to divide the array into two parts: those with values less than or equal to the pivot, and those with values greater than or equal to the pivot. Next, we sort the subarrays recursively and join them to the pivot to create the final sorted array. This array can be sorted by passing it through the quicksort() function.

Here is the code for the implementation of QuickSort in Python:

def quicksort(arr): if len(arr)  1: return arr else: pivot = arr[0] left = [x for x in arr[1:] if x  pivot] right = [x for x in arr[1:] if x >= pivot] return quicksort(left) + [pivot] + quicksort(right) arr = [5, 1, 8, 3, 2] print("original array:", arr) sorted_arr = quicksort(arr) print("Sorted array:", sorted_arr)
original array: [5, 1, 8, 3, 2] Sorted array: [1, 2, 3, 5, 8]

Quicksort in Python with user input

Here the user's input, which consists of an array of integers separated by spaces, is first converted into a string. Through a string argument passed to the ‘input’ function, the user is prompted to enter the array's elements. The final step is to create an integer for each substring using a list comprehension.

We utilise the ‘quicksort’ function to sort the array. The 'print' function is then used to display the sorted array to the user.Let’s look at the code:

def quicksort(arr): if len(arr)  1: return arr else: pivot = arr[0] left = [x for x in arr[1:] if x  pivot] right = [x for x in arr[1:] if x >= pivot] return quicksort(left) + [pivot] + quicksort(right) user_input = input("Enter the array elements separated by spaces: ") arr = [int(x) for x in user_input.split()] sorted_arr = quicksort(arr) print("Sorted array:", sorted_arr)
Enter the array elements separated by spaces: 1 5 6 2 4 7 9 Sorted array: [1, 2, 4, 5, 6, 7, 9]

Here, we use the ‘split’ function to separate a set of substrings from the input string based on whether they contain the space character. A string can be divided into a list of substrings based on a delimiter using the split() function in Python. The delimiter can be changed from the default space character to any other character or string.

Recursion in QuickSort?

Recursion has been utilized in the above programs. The ‘quicksort’ function, a recursive function that calls itself twice, sorts the left and right halves of an array separately after partitioning it.

The following describes how the recursive algorithm works. When all 'arr' is passed to the 'quicksort' function, the array is quickly sorted, and the function returns the sorted array if the array's length is one or less.

When this isn't the case, the pivot element is selected as the array's first element, and two new arrays are made: the ‘left’ array contains all elements smaller than the pivot, and the ‘right’ array contains all elements larger than or equal to the pivot.

Recursively calling the ‘quicksort’ function with the ‘left’ and right’ sub-arrays produces a sorted array by appending the output to the pivot element. This process is repeated until the length of each subarray is 0 or 1 (when 'len(arr) = 1').

Conclusion

This is a complete guide for the Quick Sort algorithm in Python for sorting large datasets due to its speed and precision. It uses a divide-and-conquer approach that can be implemented recursive or iterative, and there are a variety of methods for determining which element will serve as the pivot. Happy Learning 🙂

Источник

Читайте также:  Относительные единицы
Оцените статью