# Implementing Quick Sort in Java

6

Implementing Quick Sort in Java

Sorting is a fundamental operation in computer science, and Quick Sort is a well-known and efficient algorithm for this task. In this blog post, we’ll explore the implementation of Quick Sort in Java, discuss its logic, and provide examples to enhance understanding.

## Quick Sort Overview

Quick Sort is a divide-and-conquer sorting algorithm that works by selecting a ‘pivot’ element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The process is then applied recursively to the sub-arrays.

## Implementing Quick Sort in Java

Let’s dive into a simple Java implementation of Quick Sort:

Java Program – Quick Sort
``````import java.util.Arrays;

public class QuickSort {

// Main method to start the Quick Sort process
public static void main(String[] args) {
int[] array = {29, 10, 14, 37, 13};

System.out.println("Original Array: " + Arrays.toString(array));

// Call the sort method to perform Quick Sort
sort(array);

System.out.println("Sorted Array: " + Arrays.toString(array));
}

// Main method to start the Quick Sort process
public static void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
quickSort(array, 0, array.length - 1);
}

// Recursive method to perform the Quick Sort
private static void quickSort(int[] array, int low, int high) {
if (low < high) {
// Partition the array and get the pivot index
int pivotIndex = partition(array, low, high);

// Recursively apply Quick Sort to the sub-arrays
quickSort(array, low, pivotIndex - 1);
quickSort(array, pivotIndex + 1, high);
}
}

// Helper method to partition the array and return the pivot index
private static int partition(int[] array, int low, int high) {
// Choose the rightmost element as the pivot
int pivot = array[high];
int i = low - 1;

// Iterate through the array and reorganize elements
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
// Swap elements if they are less than the pivot
swap(array, i, j);
}
}

// Swap the pivot element into its correct position
swap(array, i + 1, high);

// Return the pivot index
return i + 1;
}

// Helper method to swap two elements in the array
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}``````

### Understanding the Logic

`sort `:

• Entry point to the Quick Sort algorithm. It checks for null or empty arrays and calls `quickSort` to start the sorting process.

`quicksort` :

• Recursive method that performs the actual sorting.
• Chooses a pivot, partitions the array, and recursively applies Quick Sort to the sub-arrays.

`partition` :

• Selects the rightmost element as the pivot.
• Reorganizes the array so that elements less than the pivot are on the left, and elements greater than the pivot are on the right.

`swap` :

• Helper method to swap two elements in the array.

### Example:

Let’s consider an example array: `{29, 10, 14, 37, 13}`.

Initial Step:

• Choose 13 as the pivot (rightmost element).

Partition:

• Reorganize the array: `{10, 13, 14, 37, 29}`.

Recursion:

• Apply Quick Sort to the left and right sub-arrays.

Final Result:

• The sorted array: `{10, 13, 14, 29, 37}`.

Output:

Output – Quick Sort
``````Original Array: [29, 10, 14, 37, 13]
Sorted Array: [10, 13, 14, 29, 37]``````

## Conclusion

Quick Sort is a powerful and widely used sorting algorithm, known for its efficiency and average-case time complexity of O(n log n). By understanding its logic and implementation in Java, you can appreciate its effectiveness in sorting arrays with speed and elegance. Happy Coding!

Latest Posts: