Home Data Structures and Algorithms with Java Quicksort in Java

Lesson 25 of 48

In Progress

← Previous Next→

Quicksort in Java

Yasin Cakal

Quicksort is a popular sorting algorithm that is commonly used in computer programming. It is considered to be one of the fastest sorting algorithms with an average time complexity of O(n log n). Quicksort is a divide and conquer algorithm that works by partitioning a given array into two smaller arrays based on a pivot element. It then recursively sorts the two arrays in a similar fashion until the array is fully sorted. In this article, we will explore Quicksort in detail and discuss its time complexity, space complexity and provide a Java code example. We will also provide five coding exercises with solutions to test the reader’s understanding of the topic.

What is Quicksort?

Quicksort is an efficient sorting algorithm that works by partitioning a given array into two smaller arrays based on a pivot element. The pivot element is chosen from the array and used to partition the array into two smaller arrays. The pivot element will be placed in its correct position in the sorted array and all elements that are smaller than the pivot element will be placed to the left of it and all elements that are larger than the pivot element will be placed to the right of it. Once the array has been partitioned, quicksort is applied recursively to the two smaller arrays until the array is fully sorted.

How does Quicksort work?

The quicksort algorithm works by selecting a pivot element from the array and using it to partition the array into two smaller arrays. The pivot element is chosen from the array and used to partition the array into two smaller arrays. The pivot element will be placed in its correct position in the sorted array and all elements that are smaller than the pivot element will be placed to the left of it and all elements that are larger than the pivot element will be placed to the right of it. Once the array has been partitioned, quicksort is applied recursively to the two smaller arrays until the array is fully sorted.

The quicksort algorithm involves three steps:

Select a pivot element from the array.
Partition the array into two smaller arrays based on the pivot element.
Recursively apply quicksort to the two smaller arrays until the array is fully sorted.

Time Complexity

The time complexity of Quicksort is O(n log n), on average. This means that for a given array of size n, the algorithm will take O(n log n) time to complete. In terms of the worst-case time complexity, it is O(n^2). This means that for a given array of size n, the algorithm may take up to O(n^2) time to complete.

In terms of access, search, insertion and deletion, the time complexity for each is O(n). This means that for a given array of size n, the algorithm will take O(n) time to access, search, insert or delete elements.

Space Complexity

The space complexity of Quicksort is O(n). This means that for a given array of size n, the algorithm will require O(n) space to complete.

Java Code Example

Below is a Java code example of the Quicksort algorithm.

public void quicksort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); 
  
        quicksort(arr, low, pi-1); 
        quicksort(arr, pi+1, high); 
    } 
} 
  
public int partition(int[] arr, int low, int high) { 
    int pivot = arr[high];  
    int i = (low-1);
    for (int j=low; j<high; j++) { 
        if (arr[j] <= pivot) { 
            i++; 
            int temp = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = temp; 
        } 
    } 
  
    int temp = arr[i+1]; 
    arr[i+1] = arr[high]; 
    arr[high] = temp; 
  
    return i+1; 
}

Conclusion

In conclusion, Quicksort is a popular sorting algorithm that is commonly used in computer programming. It is considered to be one of the fastest sorting algorithms with an average time complexity of O(n log n). Quicksort is a divide and conquer algorithm that works by partitioning a given array into two smaller arrays based on a pivot element. It then recursively sorts the two arrays in a similar fashion until the array is fully sorted. The time complexity for access, search, insertion and deletion is O(n) and the space complexity is O(n).

Exercises

Write a Java program to sort an array of integers using the quicksort algorithm.

public class QuickSortExample { 
  
    public static void main(String[] args) { 
        int[] arr = {10, 7, 8, 9, 1, 5}; 
        int n = arr.length; 
  
        QuickSortExample ob = new QuickSortExample(); 
        ob.sort(arr, 0, n-1); 
  
        System.out.println("Sorted array:"); 
        printArray(arr); 
    } 
  
    public void sort(int arr[], int low, int high) { 
        if (low < high) { 
            int pi = partition(arr, low, high); 
  
            sort(arr, low, pi-1); 
            sort(arr, pi+1, high); 
        } 
    } 
  
    public int partition(int arr[], int low, int high) { 
        int pivot = arr[high];  
        int i = (low-1);
        for (int j=low; j<high; j++) { 
            if (arr[j] <= pivot) { 
                i++; 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        } 
  
        int temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 
  
        return i+1; 
    } 
  
    public static void printArray(int arr[]) { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 
  
}

Write a Java program to search an element in an array using the quicksort algorithm.

public class QuickSortSearch { 
  
    public static void main(String[] args) { 
        int[] arr = {10, 7, 8, 9, 1, 5}; 
        int n = arr.length; 
        int x = 8; 
        
        QuickSortSearch ob = new QuickSortSearch(); 
        int result = ob.search(arr, 0, n-1, x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at index "+result); 
    } 
  
    public int search(int arr[], int low, int high, int x) { 
        if (high < low) 
            return -1; 
        int mid = low + (high - low)/2; 
        if (arr[mid] == x) 
            return mid; 
        if (arr[mid] > x) 
            return search(arr, low, mid-1, x); 
        return search(arr, mid+1, high, x); 
    } 
  
}

Write a Java program to insert an element into an array using the quicksort algorithm.

public class QuickSortInsert { 
  
    public static void main(String[] args) { 
        int[] arr = {10, 7, 8, 9, 1, 5}; 
        int n = arr.length; 
        int x = 11; 
        
        QuickSortInsert ob = new QuickSortInsert(); 
        int result = ob.insert(arr, n, x); 
        System.out.println("Element inserted at index "+result); 
    } 
  
    public int insert(int arr[], int n, int x) { 
        int low = 0; 
        int high = n - 1; 
        int mid; 
        while (low <= high) { 
            mid = low + (high - low) / 2; 
            if (arr[mid] == x) 
                return mid; 
            if (arr[mid] > x) 
                high = mid - 1; 
            else
                low = mid + 1; 
        } 
  
        arr[low] = x; 
        return low; 
    } 
  
}

Write a Java program to delete an element from an array using the quicksort algorithm.

public class QuickSortDelete { 
  
    public static void main(String[] args) { 
        int[] arr = {10, 7, 8, 9, 1, 5}; 
        int n = arr.length; 
        int x = 7; 
        
        QuickSortDelete ob = new QuickSortDelete(); 
        int result = ob.delete(arr, n, x); 
        System.out.println("Element deleted at index "+result); 
    } 
  
    public int delete(int arr[], int n, int x) { 
        int low = 0; 
        int high = n - 1; 
        int mid; 
        while (low <= high) { 
            mid = low + (high - low) / 2; 
            if (arr[mid] == x) { 
                int temp = arr[mid]; 
                arr[mid] = arr[high]; 
                arr[high] = temp; 
                return mid; 
            } 
            if (arr[mid] > x) 
                high = mid - 1; 
            else
                low = mid + 1; 
        } 
  
        return -1; 
    } 
  
}

Write a Java program to access an element from an array using the quicksort algorithm.

public class QuickSortAccess { 
  
    public static void main(String[] args) { 
        int[] arr = {10, 7, 8, 9, 1, 5}; 
        int n = arr.length; 
        int x = 7; 
        
        QuickSortAccess ob = new QuickSortAccess(); 
        int result = ob.access(arr, 0, n-1, x); 
        System.out.println("Element found at index "+result); 
    } 
  
    public int access(int arr[], int low, int high, int x) { 
        if (high < low) 
            return -1; 
        int mid = low + (high - low)/2; 
        if (arr[mid] == x) 
            return mid; 
        if (arr[mid] > x) 
            return access(arr, low, mid-1, x); 
        return access(arr, mid+1, high, x); 
    } 
  
}

Data Structures and Algorithms with Java

Participants 433