Алгоритм быстрой сортировки си шарп

Quicksort in C# and C++

Quicksort is another common sorting algorithm. Its a divide and conquer based algorithm. Quicksort is better to use with bigger collections as the time complexity is better in the long run. For smaller collections its better to use the Bubble Sort or the Insertion Sort.

Algorithm explained:

1. Pick a pivot value. In Quicksort, the pivot value is used to partition the array; and, in a unsorted array, it can either be the first value of the array, the middle, end, or rather randomly choosing a value within the array can be the pivot. In this tutorial, the median value will be the pivot. In theory, any value can be considered a pivot because any value is as good as the other. However, ideally for good performance measures, it is good practice to obtain a pivot value that is in the middle of the array (it can be obtained by selecting 3 random values, and setting the middle value as the pivot). Choosing a middle value lessens the chance that extreme values such as those that are too high or too low are chosen, and this is more efficient (less work done).
2. Move anything less than the pivot, left of the pivot value, move anything greater than the pivot, right of the pivot (assuming ascending order)
3. Recurse on each side (basically, repeat steps 1 & 2 for the left side until the left side is sorted, and do the same for the right side)
4. Once we run out of comparisons to make, sorting is done

Quick sort has O(nlog n) time complexity, for BEST and AVERAGE case. The reason for this is that it consists of two parts. The first is the partitioning of the array which had a run time of O(n) each time its executed. The QuickSort recursion has a run time of O(log n) due to every time Partition does an operation (as in pivot, split, and sort), the recursion from it creates a binary tree of calls. For the WORST case, Quicksort has O(n²) runtime, this is when the collection is nearly sorted or sorted already.

For this implementation, there is a single method called QuickSort that takes 3 parameters: array[], integer begin, integer end. The partitioning will also be done inside this method. We have a separate swap method that swaps two values in the array.

Sample code in C#

static void Main(string[] args) < int[] arr = < 6, 2, 4, 9, 1, 7, 3, 5, 8 >; quicksort(arr, 0, arr.Length — 1); Console.WriteLine(); for (int i = 0; i < arr.Length; i++) < Console.Write("", arr[i]); > Console.ReadLine(); > static void quicksort(int[] arr, int begin, int end) < int pivot = arr[(begin + (end - begin) / 2)]; int left = begin; int right = end; while (left while (arr[right] > pivot) < right--; >if (left > if (begin < right) < quicksort(arr, begin, left - 1); >if (end > left) < quicksort(arr, right + 1, end); >> static void swap(int[] items, int x, int y)

C++:

#include #include using namespace std; void quicksort(int items[], int begin, int end); void swap(int items[], int &x, int &y); int main() < int items[] = ; int sizeOfArray = (sizeof(items)/sizeof(*items)); quicksort(items, 0, sizeOfArray - 1); for(unsigned int i = 0; i < sizeOfArray; i++) < coutcin.get(); > void quicksort(int items[], int begin, int end) < int pivot = items[(begin+(end-begin)/2)]; int left = begin; int right = end; while(left while(items[right] > pivot) < right--; >if(left > if(begin < right) < quicksort(items, begin, left - 1); >if(end > left) < quicksort(items, right + 1, end); >> void swap(int items[], int &x, int &y)

Источник

Quick Sort algorithm in C#

Quick Sort is a widely used sorting algorithm that is based on the divide-and-conquer approach. It is considered one of the most efficient sorting algorithms with an average time complexity of O(n log n). The basic idea behind quick sort is to partition the array into two sub-arrays, one containing elements less than a pivot element and the other containing elements greater than the pivot element. The pivot element is chosen in such a way that it divides the array into two roughly equal-sized partitions. This process is then repeated recursively on the two sub-arrays until the entire array is sorted. Quick sort algorithm in C# is represented as a built-in method, however, you can rewrite it on your own.

In C#, the built-in Array.Sort() method and the List.Sort() method use a variant of the QuickSort algorithm to sort the elements of the array or list. However, sometimes you may need to implement your own custom QuickSort algorithm to suit your specific needs. For example, if you have a custom type of object that doesn’t implement the IComparable interface, you can’t use the built-in sorting methods.

Custom version of Quick sort

Here is an example of how to implement a custom quick sort algorithm in C#:

This code is an implementation of the Quick Sort algorithm, which is a divide-and-conquer algorithm used to sort an array of integers. The Sort() method is a public static method that takes in an integer array, arr, and two integers, left and right, as arguments. The method first checks if the left index is less than the right index. If it is, the method calls the private static Partition() method and assigns the returned value to a variable named pivot.

The Partition() method takes in the same three arguments as the Sort() method and is used to partition the array and select a pivot element. The pivot element is chosen to be the last element of the array. The method initializes a variable named i to be left – 1 and a variable named j to be left. It then enters a for loop that iterates from the left index to the right index (not including the right index). Inside the for loop, the method checks if the current element is less than or equal to the pivot element. If it is, the method increments i and swaps the current element with the element at the i index.

After the for loop, the method swaps the element at the i+1 index with the pivot element, and return i+1 as the pivot index.

Finally, back in the Sort() method, the method is called recursively to sort the left and right partitions of the array, taking the pivot-1 index and pivot+1 index as the new right and left bounds, respectively. This process continues until the left index is no longer less than the right index, at which point the array is fully sorted.

This implementation of the quick sort algorithm is for an array of integers, but the same logic can be applied to arrays of other data types or even to custom types of objects by making a few modifications. For example, you can pass a custom comparison delegate or a custom comparer object to the Sort and Partition methods to define the sorting logic.

Visualization

Let’s imagine that we want to sort an array with the Quick sort and will go along with our algo.

As you know, the actual sorting happening in our Partition method. So let’s see what happens on each level of recursion. You can see them in the picture below:

The value underlined in red color is our pivot. On the first level, it is 0 on the second, 3, and on the third, it is 7.

The blue line highlights the unsorted part of our array. And arrows represent changes. The orange one shows changes made by the first swap, and the green one by the second swap.

Now that you know the rules, you see that on the first line, our pivot is the smallest value. And the only action we did was the second swap, which, actually, just put our pivot between values that are smaller and bigger than it is. Moreover, as you see, we do it on each recursion level.

The next line shows us two types of swaps. Because the pivot is three and it is one of the best possible pivots in this case, as there are smaller and bigger values. And as you see, here we have done the biggest part of our sorting process. So I would like you to take a close look at this level in the picture below:

This picture schematically shows us the for loop from the Partition method and the changes that have been made. First, we were looking for the best place for our pivot. And, at the same time, we were sorting the left side of our array. And in the end, we just placed the pivot where it should be.

Summary

In conclusion, quick sort is an efficient sorting algorithm that can be effectively implemented in C#. The built-in Array.Sort() method and the List.Sort() method use a variant of the QuickSort algorithm to sort the elements of the array or list, but sometimes you may need to implement your own custom quick-sort algorithm to suit your needs.

Want to know more about another top sorting algorithm? Follow the link.

Related posts:

Источник

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

Быстрая сортировка (quick sort), или сортировка Хоара – один из самых быстрых алгоритмов сортирования данных.

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

Принцип работы алгоритма быстрой сортировки

• Необходимо выбрать опорный элемент массива, им может быть любой элемент, от этого не зависит правильность работы алгоритма;
• Разделить массив на три части, в первую должны войти элементы меньше опорного, во вторую — равные опорному и в третью — все элементы больше опорного;
• Рекурсивно выполняются предыдущие шаги, для подмассивов с меньшими и большими значениями, до тех пор, пока в них содержится больше одного элемента.

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

Реализация быстрой сортировки

using System; class Program < //метод для обмена элементов массива static void Swap(ref int x, ref int y) < var t = x; x = y; y = t; > //метод возвращающий индекс опорного элемента static int Partition(int[] array, int minIndex, int maxIndex) < var pivot = minIndex - 1; for (var i = minIndex; i < maxIndex; i++) < if (array[i] < array[maxIndex]) < pivot++; Swap(ref array[pivot], ref array[i]); > > pivot++; Swap(ref array[pivot], ref array[maxIndex]); return pivot; > //быстрая сортировка static int[] QuickSort(int[] array, int minIndex, int maxIndex) < if (minIndex >= maxIndex) < return array; > var pivotIndex = Partition(array, minIndex, maxIndex); QuickSort(array, minIndex, pivotIndex - 1); QuickSort(array, pivotIndex + 1, maxIndex); return array; > static int[] QuickSort(int[] array) < return QuickSort(array, 0, array.Length - 1); > static void Main(string[] args) < Console.Write("N hljs-keyword">var len = Convert.ToInt32(Console.ReadLine()); var a = new int[len]; for (var i = 0; i < a.Length; ++i) < Console.Write("a[] hljs-string">"Упорядоченный массив: ", string.Join(", ", QuickSort(a))); Console.ReadLine(); > > 

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

Результат работы программы:

Источник

Quick Sort — The Sorting Algorithm Family Reunion

Graduated first in his class, runs a successful business, owns a boat, married to a brilliant accountant, with two beautiful children. He does not slow down; he does everything fast and thoroughly. Keeping up with his family is quite the endeavor. When he picks something to get done, it gets DONE.

Sometimes, though, he wonders. He wonders if maybe there’s more to life than climbing the org chart, buying soulless things, or making money. He wonders if maybe, just maybe, he could slow down and enjoy the scenery for once. And then he decides that’s for wimps and goes back to working all hours of the night.

The Rundown

• Created By:C. A. R. «Tony» Hoare (1959)
• Type:Exchange
• Stable? No
• Best-Case:O(n log n)
• Average-Case:O(n log n)
• Worst-Case:O(n 2 )
• Space Complexity:O(n)
• Sample Project: Over on GitHub

Algorithm

1. SELECT a pivot point. (Our implementation selects the last number in the collection).
2. REORDER the collection such that all values less than the pivot are before the pivot, and all values greater than the pivot are after it.
3. RECURSIVE CONTINUE: Return to Step 1, selecting a new pivot in each of the divided higher and lower sections, until the array is sorted.

Visualization

The critical thing Quick Sort does is select a pivot point, but different varieties do this differently. In the above animation (and the below implementation), the first pivot point is merely the last item in the collection, and it continues to pick the last item in each «partition» caused by the sort as a pivot point.

Reader James Curran also contributed another visualization of this sort:

Finally, check out this audibilization on YouTube:

Источник