Меню

Швидке сортування в Java - алгоритм, ілюстрація та реалізація

  • Головна
  • Інший
  • Швидке сортування в Java - алгоритм, ілюстрація та реалізація

quicksort java algorithm

Спробуйте Наш Інструмент Для Усунення Проблем

Цей посібник пояснює алгоритм швидкого сортування на Java, його ілюстрації, реалізацію QuickSort в Java за допомогою прикладів коду:

Техніка сортування Quicksort широко використовується в програмних додатках. Quicksort використовує стратегію поділу та завоювання, як сортування злиттям.

В алгоритмі швидкого сортування спочатку вибирається спеціальний елемент, який називається “pivot”, і відповідний масив чи список поділяється на два підмножини. Розділені підмножини можуть мати або не мати однаковий розмір.

=> Прочитайте серію Easy Java Training.

Техніка швидкого сортування на Java

Розділи такі, що всі елементи, менше елемента опори, знаходяться вліво від стовпа, а елементи, більші за шарнір, - праворуч від стовпа. Підпрограма Quicksort рекурсивно сортує два підсписки. Quicksort працює ефективно, а також швидше навіть для більших масивів або списків.

Що ви дізнаєтесь:

Quicksort Розділ Java

Розбиття - це ключовий процес техніки Quicksort. То що таке розділення?

яка найкраща операційна система windows - -

Враховуючи масив A, ми вибираємо значення x, яке називається опорним, таким чином, що всі елементи, менші за x, стоять перед x, а всі елементи, більші за x, знаходяться після x.

Значення зведення може бути будь-яким із наступного:

  • Перший елемент у масиві
  • Останній елемент у масиві
  • Середній елемент у масиві
  • Будь-який випадковий елемент у масиві

Потім це зведене значення розміщується у відповідному положенні в масиві шляхом розділення масиву. Таким чином, результатом процесу 'розділення' є значення опори у правильному положенні та елементи, менші за шарнір зліва та елементи, більші за шарнір праворуч.

Розглянемо наступну схему, яка пояснює процес розділення.

процес розділення

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

Далі ми перелічимо алгоритм та псевдокод для техніки швидкого сортування, який також включає процедуру розділення.

Алгоритм швидкого сортування Java

Загальний алгоритм швидкого сортування наведено нижче.

quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low

Нижче наведено псевдокод для техніки швидкого сортування.

Псевдокод для швидкого сортування

Далі наведено псевдокод для техніки швидкого сортування. Зверніть увагу, що ми надали псевдо-код для швидкого сортування та процедури розділення.

//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low

Ілюстрація

Давайте подивимося ілюстрацію алгоритму швидкого сортування. Візьмемо наступний масив як приклад. Тут ми вибрали останній елемент як опорну.

Як показано, перший елемент позначений низьким, а останній - високим.

Ілюстрація алгоритму Quicksort

Як видно з наведеної ілюстрації, є два вказівники - високий і низький, які відповідно вказують на останній і перший елементи масиву. Обидва ці вказівники переміщуються в міру просування швидкої сорти.

Коли елемент, на який вказує низький вказівник, стає більшим за поворотний елемент, а елемент, який вказує високий вказівник, менший за поворотний, ми обмінюємось елементами, вказуваними низьким і високим вказівником, і кожен вказівник просувається на 1 позицію.

Вищезазначені кроки виконуються до тих пір, поки обидва вказівники не перетнуть один одного в масиві. Як тільки вони перетинаються, шарнірний елемент отримує належне положення в масиві. На даний момент масив розділений, і тепер ми можемо сортувати кожен підмасив незалежно, застосовуючи рекурсивний алгоритм швидкого сортування до кожного з підмасивів.

Реалізація Quicksort в Java

Техніка QuickSort може бути реалізована в Java за допомогою рекурсії або ітерації. У цьому розділі ми побачимо обидві ці техніки.

Рекурсивний швидкий сорт

Ми знаємо, що основна техніка швидкого сортування, проілюстрована вище, використовує рекурсію для сортування масиву. У рекурсивному швидкому сортуванні після розділення масиву підпрограма швидкого сортування викликається рекурсивно для сортування підмасивів.

Наведена нижче реалізація демонструє техніку швидкого сортування з використанням рекурсії.

import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j

Вихід:

Оригінальний масив: (4, -1, 6, 8, 0, 5, -3)
Відсортований масив: (-3, -1, 0, 4, 5, 6, 8)

Рекурсивна швидка сортировка - вихід

Ітеративний Quicksort

В ітеративній швидкій сортуванні ми використовуємо допоміжний стек для розміщення проміжних параметрів замість рекурсії та сортування розділів.

Наступна програма Java реалізує ітеративне швидке сортування.

import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1

Вихід:

Оригінальний масив: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Відсортований масив: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)

Ітеративна швидка сортування - вихід

Часті запитання

Q # 1) Як працює Quicksort?

Відповідь: Quicksort використовує стратегію поділу та перемоги. Quicksort спочатку розділяє масив навколо вибраного елемента зведення та генерує підмасиви, які сортуються рекурсивно.

Q # 2) Яка часова складність Quicksort?

Відповідь: Часова складність швидкого сортування в середньому становить O (nlogn). У гіршому випадку це O (n ^ 2) те саме, що і сортування виділення.

Q # 3) Де використовується Quicksort?

Відповідь: Quicksort в основному використовується в рекурсивних додатках. Quicksort є частиною C-бібліотеки. Крім того, майже мови програмування, які використовують вбудоване сортування, реалізують швидке сортування.

Q # 4) У чому перевага Quicksort?

Відповідь:

  • Quicksort - це ефективний алгоритм, який дозволяє легко сортувати навіть величезний список елементів.
  • Це сортування на місці, а отже, йому не потрібно додатковий простір або пам’ять.
  • Він широко використовується і забезпечує ефективний спосіб сортування наборів даних будь-якої довжини.

Q # 5) Чому Quicksort краще сортування?

Відповідь: Основна причина, з якої швидке сортування краще сортування злиттям, полягає в тому, що швидке сортування є методом сортування на місці і не вимагає додаткового місця в пам'яті. Сортування злиття вимагає додаткової пам'яті для проміжного сортування.

Висновок

Quicksort вважається найкращим алгоритмом сортування, головним чином, завдяки його ефективності сортувати навіть величезний набір даних за час O (nlogn).

Quicksort також є сортом на місці і не вимагає додаткового місця в пам'яті. У цьому підручнику ми бачили рекурсивну та ітераційну реалізацію швидкого сортування.

У нашому підручнику ми продовжимо методи сортування на Java.

YouTube в MP4 конвертер онлайн безкоштовно

=> Подивіться тут посібник для початківців Java.

Рекомендована література

^