Quicksort is an efficient, general-purpose sorting
algorithm. Quicksort was developed by British computer scientist Tony Hoare in
1959[1] and published in 1961.[2] It is still a commonly used algorithm for
sorting. Overall, it is slightly faster than merge sort and heapsort for
randomized data, particularly on larger distributions.[3]
Quicksort is a divide-and-conquer algorithm. It works by
selecting a 'pivot' element from the array and partitioning the other elements
into two sub-arrays, according to whether they are less than or greater than
the pivot. For this reason, it is sometimes called partition-exchange sort.[4]
The sub-arrays are then sorted recursively. This can be done in-place,
requiring small additional amounts of memory to perform the sorting.
Quicksort is a comparison sort, meaning that it can sort
items of any type for which a "less-than" relation (formally, a total
order) is defined. It is a comparison-based sort since elements a and b are
only swapped in case their relative order has been obtained in the transitive
closure of prior comparison-outcomes. Most implementations of quicksort are not
stable, meaning that the relative order of equal sort items is not preserved.
java
|
package
com.kartik.sorting; import
com.kartik.sorting.tree.BTreePrinter; /** * * *
@author MandalKC This method use First Divide method and after than Selection *
Sort algo * */ public class
QuickSort { private
int array[]; private
int length; /** * *
@param inputArr */ public
void sort(int[] inputArr) { System.out.println("Before
Quick Soring --->>"); printNumbers(inputArr); System.out.println("After
Quick Soring start--->>"); if
(inputArr == null || inputArr.length == 0) { return; } this.array
= inputArr; length
= inputArr.length; quickSort(0,
length - 1); } /** * *
@param lowerIndex *
@param higherIndex */ private
void quickSort(int lowerIndex, int higherIndex) { int
i = lowerIndex; int
j = higherIndex; //
calculate pivot number, I am taking pivot as middle index number int
pivot = array[lowerIndex + (higherIndex - lowerIndex) / 2]; //
Divide into two arrays while
(i <= j) { /**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a
* number from right side which is less then the pivot value. Once
* the search is done, then we exchange both numbers.
*/ while
(array[i] < pivot) { i++; } while
(array[j] > pivot) { j--; } if
(i <= j) { exchangeNumbers(i,
j); //
move index to next position on both sides i++; j--; }
BTreePrinter.printNode(HeapSort.drawTree(array)); printNumbers(array); } //
call quickSort() method recursively if
(lowerIndex < j) quickSort(lowerIndex,
j); if
(i < higherIndex) quickSort(i,
higherIndex); } /** * *
@param i *
@param j */ private
void exchangeNumbers(int i, int j) { int
temp = array[i]; array[i]
= array[j]; array[j]
= temp; } /** * *
@param input */ private
static void printNumbers(int[] input) { for
(int i = 0; i < input.length; i++) { System.out.print(input[i]
+ ", "); } System.out.println("\n"); } /** * *
@param a */ public
static void main(String a[]) { QuickSort
sorter = new QuickSort(); int[]
input = { 10, 34, 2, 56, 7, 67, 88, 42 }; //
int[] input = {24,2,45,20,56,75,2,56,99,53,12}; sorter.sort(input); for
(int i : input) { System.out.print(i); System.out.print("
"); } } } |
The provided code implements the Quick Sort algorithm in
Java. This implementation includes additional features for visualizing the
sorting process by printing the array as a binary tree after key operations
using the BTreePrinter and HeapSort.drawTree methods.
Explanation of the Code:
- Variables:
- array[]:
The array to be sorted.
- length:
The length of the array.
- Main
Method:
- Creates
an instance of QuickSort.
- Calls
the sort() method with an input array of integers.
- Sorting
Process:
- The sort()
method checks if the input array is null or empty. If it is valid, it
initializes the array and length fields and starts the sorting process by
calling quickSort().
- quickSort()
is the recursive function that implements the core of the Quick Sort
algorithm. It selects a pivot (in this case, the middle element of the
current subarray), partitions the array into two halves based on the
pivot, and then recursively sorts the two halves.
- The exchangeNumbers()
method is used to swap elements in the array.
- Visualization:
- After
each exchange operation, the array is printed using printNumbers().
- The
array is also visualized as a binary tree after each partitioning step
using BTreePrinter.printNode(HeapSort.drawTree(array)). This requires
custom classes (BTreePrinter and HeapSort) to be implemented separately.
Example Output:
When you run the code, the console will display the initial
array, followed by the array after each step of the sorting process, both in
linear format and as a binary tree (assuming the BTreePrinter and HeapSort
classes are implemented).
plaintext
|
Before Quick
Sorting --->> 10, 34, 2,
56, 7, 67, 88, 42, After Quick
Sorting start--->> 10, 34, 2,
42, 7, 67, 88, 56, ... 2, 7, 10, 34,
42, 56, 67, 88, |
Important Notes:
- Pivot Selection: The pivot is selected as the middle element of the array. Different pivot selection strategies (e.g., first element, last element, random element) can affect the performance of Quick Sort.
- Custom Classes: Ensure that BTreePrinter and HeapSort classes are correctly implemented and available in your project. These classes are necessary for the visualization part of the code.
- Edge Cases: Consider testing the algorithm with edge cases, such as an array with duplicate values, an already sorted array, or a completely reversed array.
Potential Enhancements:
- Pivot Strategy: Explore different pivot selection strategies to optimize performance for specific types of input arrays.
- Parallel
Processing: Implement parallel Quick Sort for large arrays to leverage
multi-core processors.
- Generic
Implementation: Modify the implementation to work with generic types
instead of just integers.
- Error
Handling: Add more robust error handling, such as dealing with invalid
input arrays.
Running the Code:
To run this code, ensure that your project includes the
necessary custom classes (BTreePrinter and HeapSort) and any other dependencies
required for the visualization. Once set up, you can observe how the Quick Sort
algorithm works step-by-step, both through console output and tree
visualization.
Out Put:
|
Before Quick
Soring --->> 10, 34, 2,
56, 7, 67, 88, 42, After Quick
Soring start--->> 10 / \
/
\ /
\ /
\ 34
2 / \
/ \ /
\ / \ 42
7 67 88 / 56 10, 34, 2,
42, 7, 67, 88, 56, 10 / \
/
\ /
\ /
\ 34
2 / \
/ \ /
\ / \ 42
7 67 88 / 56 10, 34, 2,
42, 7, 67, 88, 56, 2 / \
/
\ /
\ /
\ 34
10 / \
/ \ /
\ / \ 42
7 67 88 / 56 2, 34, 10,
42, 7, 67, 88, 56, 2 / \
/
\ /
\ /
\ 34
10 / \
/ \ /
\ / \ 42
7 67 88 / 56 2, 34, 10,
42, 7, 67, 88, 56, 2 / \
/
\ /
\ /
\ 7
10 / \
/ \ /
\ / \ 42
34 67 88 / 56 2, 7, 10, 42,
34, 67, 88, 56, 2 / \
/
\ /
\ /
\ 7
10 / \
/ \ /
\ / \ 42
34 67 88 / 56 2, 7, 10, 42,
34, 67, 88, 56, 2 / \
/
\ /
\ /
\ 7
10 / \
/ \ /
\ / \ 34
42 67 88 / 56 2, 7, 10, 34,
42, 67, 88, 56, 2 / \
/
\ /
\ /
\ 7
10 / \
/ \ /
\ / \ 34
42 67 56 / 88 2, 7, 10, 34,
42, 67, 56, 88, 2 / \
/
\ /
\ /
\ 7
10 / \
/ \ /
\ / \ 34
42 56 67 / 88 2, 7, 10, 34,
42, 56, 67, 88, 2 7 10 34 42
56 67 88 |
 |
| Quick Sort |
0 Comments