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

QuickSort Algorithm

In this post, we will look in to the Quicksort in Java and its different implementations. Like Mergesort, Quicksort is a Divide and Conquer algorithm.

1. Quicksort Algorithm

Quicksort algorithm is one of the most used sorting algorithm based on the Divide-and-Conquer algorithm. It work by dividing the input in the 2 sub problems and sorting the both side recursively. This algorithm picks one of the element as Pivot and partition the input around the Pivot. There are different variations of choosing the Pivot element:

1. Choose the first element as Pivot.
2. Last element as Pivot.
3. Random element as Pivot.

The core concept of Quicksort algorithm is the partition logic. Once we pick the Pivot element, we group the input into 2 parts and place the Pivot on the correct position so that

• All elements less than pivot are on the left-hand side of the pivot.
• All element greater than pivot will be on the right-hand side.

We sort the both side recursively by repeating the above step (Choose Pivot and put Pivot in the correct position). Before we get in to the Quicksort implementation, let’s see how this work using one example. Let’s take this array as an input:

Let’s choose the Pivot element, in this example, we will choose last element as a pivot. Once we choose the pivot, we will position the pivot element to its correct position so as all element less than pivot are on the left-hand side while element greater than the pivot element are on the right-hand side. On the first iteration, this is how our array look like:

We know this process as Partitioning and it’s the core concept of the Quicksort algorithm. There are multiple ways to partition the input. In our example, we will start with the following steps

1. Take position index which keep trek of the last item swapped.
2. We start from the left side and will push the element to the left if less than pivot else to the right side.
3. Process will go till the end of the input.
4. As the last step, we will swap the pivot with the last swap item index. (This step moves the pivot to its sorted position)

[pullquote align=”normal”]Pay close attention to the pIndex position. Once we swapped the elements, we incremented the pIndex so trek the next element which should be moved to the right of pivot. [/pullquote]

We repeat this process we reach at the end. Once we reach at the end, we swap the pivot element with the pIndex to move the pivot to its sorted position (Pivot is at the sorted element and we left with sorting the right and left side of the pivot)

1.1 Recursive Sorting

With Quicksort, we recursively sort the left and right side of the input by selecting the new pivot element and sorting this pivot to its correct position. At the end of each iteration, we recursively sorting the left and right side of the input.

2. Pseudo Code

Let’s look in to the pseudo-code if you want to implement the Quicksort in Java:

quickSort(array[] input, start, end) < if(start < end)< // we only want to run it till we are not at the end of the input position = partition(input, start, end); // position show the correct place for the pivot element quickSort(input, start, position-1); // we will recursively sort the left side of the pivot quickSort(input, position+1, end) // sort the right side of pivot >> /** * partition is the core of the quick sort algorithm */ partition(array[] a, start, end) < pivot = a[end]; // we picked the last element as pivot pIndex = low; for(i = start; i> // when reached at the end, let's swap the pivot and pInex swap(pivot,pindex); return pIndex; >

3. Quicksort in Java

Let’s see Quicksort in Java by choosing the last element as the pivot element.

public class QucikSortAlgo < public static void main(String[] args) < int[] array = ; // initial input array = quickSort(0, array.length-1,array); for (int i =0; i < array.length; i++)< System.out.println(array[i]); // print the response >> /** * The main quickSort method * */ public static int[] quickSort(int start, int end, int[] array) < if(start < end)< // keep in mind that once we have the partition, pivot is already in the correct sorted position int partition = partitionPoint(start,end,array); // find the correct position for the pivot quickSort(start, partition-1, array); // recursively call the quick sort for the left had side of the pivot quickSort(partition+1, end,array); // sort right hand side of the pivot >return array; > public static int partitionPoint(int start, int end, int[] array) < int pivot = array[end]; // choose the last element as pivot int swapPosition = start; for(int i=start; i> /* At the end swap the pivot with the swapposition. This will move the pivot element to sorted position */ swapElements(swapPosition,end,array); return swapPosition; > /** * Swap the element in the position */ public static void swapElements(int position1, int position2, int[] array) < int temp = array[position1]; array[position1] = array[position2]; array[position2] = temp; >>

4. Algorithm Analysis

Let’s take a quick look at the time and space complexity of the Quicksort algorithm:

4.1 Time Complexity

Quicksort works similar to the merge sort algorithm and recursively breaking the input in small sub problems. In the best case, it will split the input in two 2 equal half. Let’s see the time complexity for worst and best case.

Worst Case: In the worst case, partition might always pick the largest or smallest element from the input. In our example last element always picked as pivot element. This can happen if we sort the input array in increasing or decreasing order. In the worst case it’s possible for the complexity to get as high as O<(n 2 .

Best Case: In the best case, the partition process always pick the middle element as Pivot. The best-case time and average case complexity of Quicksort is O(nLogn).

4.2 Space Complexity

Quicksort is an in-place algorithm. This means, it does not need any extra array or data structure to store the intermediate results. This algorithm has a space complexity of O(n) where there are O(n) recursive calls (Worst case).

4.3 QuickSort vs MergeSort

Both Quicksort and Mergesort algorithm have an average time complexity of O(n log n). but Quicksort is a preferred sorting algorithm for sorting Arrays. Here are some points which makes Quicksort a preferred sorting algorithm for Arrays.

1. 1. It is an in place sorting algorithm (Don’t need any extra storage).
   2. Allocating or reallocating the Array is expensive (especially with big input) and add extra running time. Time take to copy the array to the new Array, etc.
   3. Quick Sort is a cache friendly sorting algorithm.
   4. Mergesort is a preferred sorting algorithm for the Linked-list.

   5. Sorting With First Element as Pivot

   Let’s see another variation of the Quicksort algorithm by selecting the first element as Pivot

   public class QuckSortFirstElement< public static void main(String[] args)< int[] input = ; quickSort(0, input.length-1, input); for(int i=0; i < input.length; i++)< System.out.println(input[i]); >> protected static void quickSort(int start, int end, int[] a) < if(startreturn; > protected static int partition(int start, int end, int[] a) < int p = start; int i = start; int j= end; while (i< j)< while(a[i]while(a[j]> a[p] && j > start) < j--; >if(i < j)< swap(i,j,a); >> swap(j,p,a); return j; > private static void swap(int p1, int p2, int[] a) < int temp = a[p1]; a[p1] = a[p2]; a[p2] = temp; >>

   6. Quicksort – Randomization

   The worst case time complexity for the Quicksort is O(n 2). We can work on the randomization version of Quicksort algorithm where the expected time complexity is O(nLogn). Here is one of the variation of the randomized Quicksort algorithm.

   • Select random item as a pivot from the input.
   • Swap the random pivot with the last item and start the sorting as explained in the first section.
   • After every iteration, swap the last item (Pivot element) with the swap index to move the pivot to the correct position.

   Let’s see the code in action:

   public class QuickSortRandom< public static void main(String[] args)< int[] input = ; quickSort(0, input.length-1, input); for(int i =0 ; i < input.length; i++)< System.out.println(input[i]); >> public static void quickSort(int start, int end, int[] a) < if(startreturn; > protected static int partition(int start, int end, int[] a) < Random rand = new Random(); int median = rand.nextInt(end-start)+start; int pIndex=start; swap(median,end,a); int pivot = end; for(int i=start; i> swap(pivot, pIndex,a); return pIndex; > protected static void swap(int s1, int s2, int[] a) < int temp =a[s1]; a[s1] = a[s2]; a[s2] = temp; >>

   Summary

   In this article, we saw the Quicksort in Java. We discussed the different variations of the Quicksort algorithms. This is a very efficient algorithm and used in multiple places. At the end of our article, we learned the randomized version of Quicksort where the expected time complexity is O(nLogn) and not O(n 2 ) for most cases.

   Источник

   Метод быстрой сортировки в Java (Quick sort)

   Быстрая сортировка является одной из наиболее эффективных из существующих в Java. В её основе лежит рекурсивный алгоритм Quick sort. В среднем сортировка в Java выполняется за время O(n logn), причём точная скорость зависит от выбора опорного элемента.

   Принято считать, что алгоритм быстрой сортировки Quick sort использует известную стратегию «разделяй и властвуй». Речь идёт о том, чтобы разбивать задачу на подзадачи до той поры, пока перед нами не будет элементарная единица. В нашем случае массив делится на несколько массивов, а каждый из них сортируется отдельно, а потом объединяется в один массив.

   Как работает быстрая сортировка в Java

   Пошаговое описание алгоритма сортировки: 1.Выбираем опорный элемент из массива. Как правило, это средний элемент. 2.Делим массив на 2 подмассива. Элементы, которые меньше опорного, и элементы, которые больше опорного. 3.Рекурсивно применяем сортировку к обоим подмассивам.

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

   Анализ алгоритма быстрой сортировки

   Исходный массив: Выбираем опорный компонет, берём 3: Теперь разобьём массив на подмассивы: те, что больше трёх и те, что меньше: То же сделаем с левым подмассивом: Выбираем опорный элемент: Разбиваем на подмассивы: Выбираем опорный компонент и выполняем разбиение на подмассивы. Проделываем это, пока в подмассиве не останется один элемент. Левая часть отсортирована. То же делается и для правой части, начиная от опорного элемента 3.

   Что же, осталось реализовать java-код.

    
   import java.util.Arrays; public class QuickSort < public static void quickSort(int[] array, int low, inthigh) < if (array.length == 0) return;//завершить выполнение, если длина массива равна 0 if (low >= high) return;//завершить выполнение если уже нечего делить // выбрать опорный элемент int middle = low + (high - low) / 2; int opora = array[middle]; // разделить на подмассивы, который больше и меньше опорного элемента int i = low, j = high; while (i while (array[j] > opora) < j--; >if (i  > // вызов рекурсии для сортировки левой и правой части if (low < j) quickSort(array, low, j); if (high >i) quickSort(array, i, high); > public static void main(String[] args) < int[] x = < 8, 0, 4, 7, 3, 7, 10, 12, -3 >; System.out.println("Было"); System.out.println(Arrays.toString(x)); int low = 0; int high = x.length - 1; quickSort(x, low, high); System.out.println("Стало"); System.out.println(Arrays.toString(x)); > >
    
   Мы рассмотрели алгоритм, благодаря которому реализуется быстрая сортировка в Java. В заключение скажем, что Quick sort — это действительно эффективный способ, идеально подходящий даже для сортировки больших массивов.
    
   Хотите узнать о Java-программировании больше? Записывайтесь на наш курс «Разработчик Java»!
    
   Источник