Home » Core Java » Quicksort Java algorithm – Code Example

About Rohit Joshi

Rohit Joshi
Rohit Joshi works as a Software Engineer in the Consumer Product Sector. He is a Sun Certified Java Programmer. He had worked in projects related to different domains. He is also involved in system analysis and system designing. He mainly works in Core Java and J2EE technologies but also have good experience in front-end technologies like Javascript and Jquery.

Quicksort Java algorithm – Code Example

In this article, we will discuss the implementation of Quicksort Java algorithm. Quicksort is the most widely used sorting algorithm. It is faster than most other common sorting algorithms. It was developed by the famous Computer Scientist Tony Hoare and it is based on the Divide and Conquer Algorithm.

First, we are going to explain how Quicksort works on an algorithmic level, with some simple examples. Finally, we will build our implementation in Java and discuss its performance.

1. The Quicksort Java Algorithm

Quicksort works recursively in order to sort a given array. These are the three basic steps of the Quicksort algorithm:

1. Partition the array into left and right sub-arrays, in which the items in the left sub-array are smaller than the specified item and the items in the right sub-array are greater than the specified item.
2. Recursively call the Quicksort to sort the left sub-array.
3. Recursively call the Quicksort to sort the right sub-array.

The partitioning step is the key when sorting an array with Quicksort. Quicksort itself uses a Partition algorithm to partition the given array.

The partition works by using two cursors (let say), one at each end of the array. These cursors move towards each other. If the left cursor finds an item that is smaller than the pivot value, it ignores it and moves forward. But if the item’s value is greater than the pivot value, it stops. Similarly for the right cursor, if an item is greater than the pivot value it ignores it and moves backward, else the cursor stops. When both cursors stop, the items pointed by the cursors get swapped. That’s because these items are on the wrong side of the array. After the swap, both the cursors continue, and stop at the items which are on the wrong side of the array and swap them. And that’s how the algorithm goes on until finally all items are sorted.

The pivot value is the value that is used to partition the array into two sub-arrays. After the partition, the items in the left sub-array are smaller than the pivot value, and the items in the right sub-array are greater than the pivot value.

Quicksort Java - Partition
Partition

In the above figure, we chose 56 as a pivot value. After the partition (which of course consists of more than one sub-steps), all the items on the left of the pivot are smaller, and the items on the right of it are greater than it and the pivot is at its sorted position. Also notice that, at this point, the array is not sorted of course. That was just one partitioning step.

You can choose any random value from the array as a pivot value. Later we will see that choosing a pivot value affects the performance of the algorithm. But for now, lets us take the rightmost item of the array as a pivot value and attempt to create the first version of our Java implementation.

QuicksortExample.java

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package com.javacodegeeks.sorting.quicksort;
 
public class QuicksortExample {
 
    private static int []a;
    public static void main(String[] args) {
        // Get a random generated array
        a = getArray();
         
        // prints the given array
        printArray();
         
        // sort the array
        sort();
         
        System.out.println("");
         
        //prints the sorted array
        printArray();
         
    }
     
    // This method sorts an array and internally calls quickSort
    public static void sort(){
        int left = 0;
        int right = a.length-1;
             
        quickSort(left, right);
    }
     
    // This method is used to sort the array using quicksort algorithm.
    // It takes the left and the right end of the array as the two cursors.
    private static void quickSort(int left,int right){
         
        // If both cursor scanned the complete array quicksort exits
        if(left >= right)
            return;
         
        // For the simplicity, we took the right most item of the array as a pivot
        int pivot = a[right];
        int partition = partition(left, right, pivot);
         
        // Recursively, calls the quicksort with the different left and right parameters of the sub-array
        quickSort(0, partition-1);
        quickSort(partition+1, right);
    }
     
    // This method is used to partition the given array and returns the integer which points to the sorted pivot index
    private static int partition(int left,int right,int pivot){
        int leftCursor = left-1;
        int rightCursor = right;
        while(leftCursor < rightCursor){
                while(a[++leftCursor] < pivot);
                while(rightCursor > 0 && a[--rightCursor] > pivot);
            if(leftCursor >= rightCursor){
                break;
            }else{
                swap(leftCursor, rightCursor);
            }
        }
        swap(leftCursor, right);
        return leftCursor;
    }
     
    // This method is used to swap the values between the two given index
    public static void swap(int left,int right){
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }
     
    public static void printArray(){
        for(int i : a){
            System.out.print(i+" ");
        }
    }
     
    public static int[] getArray(){
        int size=10;
        int []array = new int[size];
        int item = 0;
        for(int i=0;i<size;i++){
            item = (int)(Math.random()*100);
            array[i] = item;
        }
        return array;
    }
 
}

If we run the above code, we will have the following results:

1
2
4 94 87 24 44 30 37 97 47 93
4 24 30 37 44 47 87 93 94 97

Let’s discuss how the above program works.

The quickSort() method takes two parameters, each holding the position of the cursors at the two ends of an array or a sub-array that needs to be sorted. For example, if left = 3, then the left cursor points to element 3 of the array. The method exits, if left is greater than or equal to right, which means that the array is already sorted or the length of the array is one. It also generates a pivot value, in this case, the rightmost value of the array. The pivot value is passed to the partition method which is used to partition the given array.

The partition() method scans the array and swaps the items which are not at their proper place. The items which are greater than the pivot value, are swapped to the right of the pivot value with the values which are smaller than the pivot value. At the end of each scan, the left cursor ends up pointing to the left element of the right sub-array. The pivot is then swapped with it and puts it into its proper sorted place. This method returns an integer that is the position of the sorted pivot value that partitioned the given array or a sub-array.

Then, the quicksort() method spawns the recursive call to sort the left sub-array and the right sub-array. Let’s have a deeper look into the partition method.

int leftCursor = left-1; : This statement initializes a leftCursor to one less than the left parameter. This is because while scanning, it first gets incremented and then used to evaluate. For example, if we are scanning the complete array and not a sub-array, the leftCursor will be at 0-1, i.e., -1.

int rightCursor = right; : This statement initializes a rightCursor to the right end of the given array, i.e., rightCursor = array.lenght-1.

while(leftCursor < rightCursor): The outer while loop runs till the leftCursor is not in the same position or a position greater than the rightCursor. When this condition evaluates to false, it means that the cursors have scanned the complete array.

while(a[++leftCursor] < pivot);: This inner while loop has nothing inside its body. It’s used to move the left cursor towards the right and compare the item it’s pointing with the pivot. The loop terminates if the pointed value is greater than the pivot value.

while(rightCursor > 0 && a[--rightCursor] > pivot);: This loop does a similar work. It moves towards the left of the array and compares each item it points with the pivot. If the pointed value is smaller than the pivot value, it terminates.

When both inner while loops terminate, both the cursors point to the items which are not at their proper place. We first check whether the cursors have crossed each other, which means they have scanned the full array. Then, it exits from the loop, else the items get swapped.

Then, the quicksort() method is called recursively. This time with the two sub-arrays, the left one starting from partition-1, and the right one starting from partition+1. It sorts the sub-arrays, until the full array gets partitioned and sorted, which finally results in the full sorted array.

Generally, quicksort operates in O(nlog n) time. But there are some cases when its performance degrades to O(n2). The problem lies in the selection of the pivot. In the above example, we choose the pivot randomly (the rightmost item of the array). The pivot should be the median of the items to be sorted. So, half of the items in the array should be smaller than the pivot, and the rest should be larger than the pivot. This would result in two equally sized sub-arrays. This is the best situation for the Quicksort algorithm, where it runs at O(nlogn). Having one large and one small sub-array results in less efficiency.

2. Median of 3 Partitioning

The best approach to choose a pivot is by choosing the median of the first, middle, and the last items of the array. This approach is known as the ‘median-of-three’ approach.

Quicksort Java - Median
Median

QuicksortMedianExample.java

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
package com.javacodegeeks.sorting.quicksort;
 
public class QuicksortMedianExample {
 
    private static int []a;
    public static void main(String[] args) {
        // Get a random generated array
        a = getArray();
         
        // prints the given array
        printArray();
         
        // sort the array
        sort();
         
        System.out.println("");
         
        //prints the sorted array
        printArray();
         
    }
     
    // This method sorts an array and internally calls quickSort
    public static void sort(){
        int left = 0;
        int right = a.length-1;
             
        quickSort(left, right);
    }
     
    // This method is used to sort the array using quicksort algorithm.
    // It takes left and the right end of the array as two cursors
    private static void quickSort(int left,int right){
         
        // If both cursor scanned the complete array, quicksort exits
        if(left >= right)
            return;
         
        // Pivot using median of 3 approach
        int pivot = getMedian(left, right);
        int partition = partition(left, right, pivot);
         
        // Recursively, calls the quicksort with the different left and right parameters of the sub-array
        quickSort(0, partition-1);
        quickSort(partition+1, right);
    }
     
    // This method is used to partition the given array and returns the integer which points to the sorted pivot index
    private static int partition(int left,int right,int pivot){
        int leftCursor = left-1;
        int rightCursor = right;
        while(leftCursor < rightCursor){
        while(a[++leftCursor] < pivot);
        while(rightCursor > 0 && a[--rightCursor] > pivot);
            if(leftCursor >= rightCursor){
                break;
            }else{
                swap(leftCursor, rightCursor);
            }
        }
        swap(leftCursor, right);
        return leftCursor;
    }
     
    public static int getMedian(int left,int right){
        int center = (left+right)/2;
         
        if(a[left] > a[center])
            swap(left,center);
         
        if(a[left] > a[right])
            swap(left, right);
         
        if(a[center] > a[right])
            swap(center, right);
         
        swap(center, right);
        return a[right];
    }
     
    // This method is used to swap the values between the two given index
    public static void swap(int left,int right){
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }
     
    public static void printArray(){
        for(int i : a){
            System.out.print(i+" ");
        }
    }
     
    public static int[] getArray(){
        int size=10;
        int []array = new int[size];
        int item = 0;
        for(int i=0;i<size;i++){
            item = (int)(Math.random()*100);
            array[i] = item;
        }
        return array;
    }
 
}

If we run the above code, we will have the following results:

1
2
80 4 33 30 65 14 35 25 31 12
4 12 14 25 30 31 33 35 65 80

In the above example, we have used the median-of-3 approach to find a “good” pivot. We used the first, the middle, and last items of the array to find the median. The median is the middle item between the orderly placed items. This approach is not only used to select the pivot but also to put the three items in their sorted place in the array. Let us look at getMedian() in the above example.

getMedian(int left, int right): This method is used to return a median among the three items specified. The returned median is used as the pivot in quicksort. This method has two parameters, both pointing at each end of the array or the sub-array. We used the middle, left and right items to find the median. In the end, we swapped the median with the item at the rightmost position of the array. So, after the scan, all these three items should be in their proper sorted places in the array. This process is repeated with all the sub-arrays having different left, right and middle positions until the full array gets sorted.

3. Quicksort with String

So far, we have seen quicksort with integer arrays. In this example, we will sort an array of Strings using quicksort.

QuicksortStringExample.java

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package com.javacodegeeks.sorting.quicksort;
 
public class QuicksortStringExample {
 
    private static String []a;
    public static void main(String[] args) {
        // Get an String array
        a = new String[]{"X","E","C","A"};
         
        // prints the given array
        printArray();
         
        // sort the array
        sort();
         
        System.out.println("");
         
        //prints the sorted array
        printArray();
         
    }
     
    // This method sort an array internally and internally calls quickSort
    public static void sort(){
        int left = 0;
        int right = a.length-1;
             
        quickSort(left, right);
    }
     
    // This method is used to sort the array using quicksort algorithm.
    // It takes left and the right end of the array as two cursors
    private static void quickSort(int left,int right){
         
        // If both cursor scanned the complete array quicksort exits
        if(left >= right)
            return;
         
        // Pivot using median of 3 approach
        String pivot = getMedian(left, right);
        int partition = partition(left, right, pivot);
         
        // Recursively, calls the quicksort with the different left and right parameters of the sub-array
        quickSort(0, partition-1);
        quickSort(partition+1, right);
    }
     
    // This method is used to partition the given array and returns the integer which points to the sorted pivot index
    private static int partition(int left,int right,String pivot){
        int leftCursor = left-1;
        int rightCursor = right;
        while(leftCursor < rightCursor){
        while(((Comparable<String>)a[++leftCursor]).compareTo(pivot) < 0);
        while(rightCursor > 0 && ((Comparable<String>)a[--rightCursor]).compareTo(pivot) > 0);
            if(leftCursor >= rightCursor){
                break;
            }else{
                swap(leftCursor, rightCursor);
            }
        }
        swap(leftCursor, right);
        return leftCursor;
    }
     
    public static String getMedian(int left,int right){
        int center = (left+right)/2;
         
        if(((Comparable<String>)a[left]).compareTo(a[center]) > 0)
            swap(left,center);
         
        if(((Comparable<String>)a[left]).compareTo(a[right]) > 0)
            swap(left, right);
         
        if(((Comparable<String>)a[center]).compareTo(a[right]) > 0)
            swap(center, right);
         
        swap(center, right);
        return a[right];
    }
     
    // This method is used to swap the values between the two given index
    public static void swap(int left,int right){
        String temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }
     
    public static void printArray(){
        for(String i : a){
            System.out.print(i+" ");
        }
    }
     
}

If we run the above code, we will have the following results:

1
2
X E C A
A C E X

In the above example, we sorted an array of Strings, using the quicksort. The String class implements the Comparable interface and overrides the compareTo() method. We used the compareTo() method to compare the Strings. We downcasted the String to the Comparable type and used the compareTo() method to find the greater or the smaller between them.

The comparison is done using the natural ordering of the String. The natural ordering in String is maintained alphabetically from A – Z and then from a – z. The rest of the code works the same as shown in the previous example.

4. Quicksort Objects

In this example, we will see how to sort Objects of a class using the Quicksort. We will create a generic quicksort method that can be used to sort objects of any class. The class needs to implement the Comparable interface and override the method compareTo in order to use the quicksort, otherwise, it will throw a ClassCastException.

Let’s create an Employee class and sort employees on the basis of their employeeCode using the Quicksort.

Employee.java

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package com.javacodegeeks.entity;
 
public class Employee implements Comparable<Employee>{
 
    private String firstName;
    private String lastName;
    private int emplyeeCode;
     
    public Employee(String fistName,String lastName,int emplyeeCode){
        this.firstName = fistName;
        this.lastName = lastName;
        this.emplyeeCode = emplyeeCode;
    }
     
    public String getFirstName() {
        return firstName;
    }
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
    public String getLastName() {
        return lastName;
    }
    public void setLastName(String lastName) {
        this.lastName = lastName;
    }
    public int getEmplyeeCode() {
        return emplyeeCode;
    }
 
    public void setEmplyeeCode(int emplyeeCode) {
        this.emplyeeCode = emplyeeCode;
    }
 
    public String toString(){
        return "Employee Code: "+getEmplyeeCode()+", Name:"+getFirstName()+" "+getLastName();
    }
 
    public int compareTo(Employee o) {
        Employee e = (Employee)o;
        if(this.emplyeeCode > e.getEmplyeeCode())
            return 1;
        if(this.emplyeeCode < e.getEmplyeeCode())
            return -1;
        if(this.emplyeeCode == e.getEmplyeeCode())
            return 0;
        return 0;
    }
}

We created an Employee class that implements the Comparable interface and overrides the compareTo() method. The comparison between the Employee objects are defined by comparing the employeeCode property of the Employee objects. The comparTo() method returns an integer, which tells whether the current employeeCode is greater than, or smaller than or equal to the compared employeeCode. It returns 1 if the current employeeCode is greater than the compared employeeCode, -1 if, the current employeeCode is smaller than the compared employeeCode, else it returns 0 if both are equal. Since the employeeCode is of type integer, we have compared it using the simple integer comparison operators.

QuicksortObjectExample.java

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
package com.javacodegeeks.sorting.quicksort;
 
import com.javacodegeeks.entity.Employee;
 
public class QuicksortObjectExample<T extends Comparable<T>> {
 
    private T []a;
    public static void main(String[] args) {
         
        Employee []employees = new Employee[5];
        Employee employee = new Employee("John","Carter",5658);
        employees[0] = employee;
        employee = new Employee("Mary","Carter",7412);
        employees[1] = employee;
        employee = new Employee("Alex","Lumb",1158);
        employees[2] = employee;
        employee = new Employee("David","Jhonson",1254);
        employees[3] = employee;
        employee = new Employee("Shaun","Smith",4587);
        employees[4] = employee;
         
        QuicksortObjectExample<Employee>ex = new QuicksortObjectExample<>();
        // Assigned array
        ex.a = employees;
         
         
        // prints the given array
        ex.printArray();
         
        // sort the array
        ex.sort();
         
        System.out.println("");
         
        //prints the sorted array
        ex.printArray();
         
    }
     
    // This method sort an array and internally calls quickSort
    public void sort(){
        int left = 0;
        int right = a.length-1;
             
        quickSort(left, right);
    }
     
    // This method is used to sort the array using quicksort algorithm.
    // It takes left and the right end of the array as two cursors
    private void quickSort(int left,int right){
         
        // If both cursor scanned the complete array quicksort exits
        if(left >= right)
            return;
         
        // Pivot using median of 3 approach
        T pivot = getMedian(left, right);
        int partition = partition(left, right, pivot);
         
        // Recursively, calls the quicksort with the different left and right parameters of the sub-array
        quickSort(0, partition-1);
        quickSort(partition+1, right);
    }
     
    // This method is used to partition the given array and returns the integer which points to the sorted pivot index
    private int partition(int left,int right,T pivot){
        int leftCursor = left-1;
        int rightCursor = right;
        while(leftCursor < rightCursor){
        while(((Comparable<T>)a[++leftCursor]).compareTo(pivot) < 0);
        while(rightCursor > 0 && ((Comparable<T>)a[--rightCursor]).compareTo(pivot) > 0);
            if(leftCursor >= rightCursor){
                break;
            }else{
                swap(leftCursor, rightCursor);
            }
        }
        swap(leftCursor, right);
        return leftCursor;
    }
     
    public T getMedian(int left,int right){
        int center = (left+right)/2;
         
        if(((Comparable<T>)a[left]).compareTo(a[center]) > 0)
            swap(left,center);
         
        if(((Comparable<T>)a[left]).compareTo(a[right]) > 0)
            swap(left, right);
         
        if(((Comparable<T>)a[center]).compareTo(a[right]) > 0)
            swap(center, right);
 
        swap(center, right);
        return a[right];
    }
     
    // This method is used to swap the values between the two given index
    public void swap(int left,int right){
        T temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }
     
    public void printArray(){
        for(T i : a){
            System.out.println(i+" ");
        }
    }
     
}

If we run the above code, we will have the following results:

01
02
03
04
05
06
07
08
09
10
11
Employee Code: 5658, Name:John Carter
Employee Code: 7412, Name:Mary Carter
Employee Code: 1158, Name:Alex Lumb
Employee Code: 1254, Name:David Jhonson
Employee Code: 4587, Name:Shaun Smith
 
Employee Code: 1158, Name:Alex Lumb
Employee Code: 1254, Name:David Jhonson
Employee Code: 4587, Name:Shaun Smith
Employee Code: 5658, Name:John Carter
Employee Code: 7412, Name:Mary Carter

In the above example, we have created a generic class which can be used to sort any objects of any type, using Quicksort. Any class T which implements the Comparable interface can be used. It performs the same functionality as shown in the previous example. The only difference is that this class is generic and it accepts any class T in its generic parameter which implements the Comparable interface.

In the previous code, we created the Employee class which implements Comparable interface and provides its own rule on how to compare its objects. The above class creates an array of the Employee class and assigns it to the array a. We print to show the current unsorted array of objects. Then, we called the sort() method which sorted the array of Employee type.

Please note that the comparison of the objects of the type Employee, is done by the rule defined in the compareTo() method in the Employee class i.e. on the basis of the employeeCode property of the class.

4. Complexity and comparison with other sorting techniques

As we noticed earlier, the Quicksort works well when the pivot is in the middle. The best case is O(nlogn) and the worst case would be O(n2). Let us now check how it fares against the other sorting techniques. Comparison is usually done based on time and space complexity.

  1. Bubble Sort: This simplest sorting technique works by iterating through the array and comparing each element. The complexity in best and worst cases is O(n2).
  2. Selection Sort: In this technique, elements are selected and placed in sorted order. Similar to Bubble sort, the best and worst-case complexity is O(n2).
  3. Insertion Sort: In this technique, each element of the array is inserted in the proper position. The best case would be when the array is already sorted. The best case would take O(n) and the worst case would be O(n2). This is best suitable when we have a small array to sort.
  4. Quick Sort: Quick Sort, as we saw, would take O(nlogn) for the best case when the right pivot is chosen. The worst case is when the array is already sorted or reverse sorted. The complexity in such a scenario would be O(n2). This is an in-place sorting mechanism and hence is space-efficient.
  5. Merge Sort: Like Quick Sort, this is also a divide and conquer recursive mechanism. The best, worst and average case for this mechanism is O(nlogn). But the sorting doesn’t happen in-place and hence is not space-efficient.
  6. Heap Sort: This in-place sorting mechanism has best, worst and average complexity as O(nlogn).
Sorting mechanismBest caseAverage caseWorst case
Bubble Sort O(n2) O(n2) O(n2)
Selection Sort O(n2) O(n2) O(n2)
Insertion SortO(n) O(n2) O(n2)
Quick SortO(nlogn) O(nlogn) O(n2)
Merge SortO(nlogn) O(nlogn) O(nlogn)
Heap Sort O(nlogn) O(nlogn) O(nlogn)

5. Download the source code

This was an example on Quicksort algorithm in Java.

Download
You can download the source code of this example from here: Quicksort Java algorithm – Code Example

Last updated on Feb. 12th, 2020

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

 

2
Leave a Reply

avatar
1 Comment threads
1 Thread replies
1 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
PhishHammerStylianos Recent comment authors

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
newest oldest most voted
Notify of
Stylianos
Guest
Stylianos

Hey, thank you very much for your help, just some debugging for one of the parts. In the “2. Median of 3 Partitioning” approach you are making a mistake. On line 44 “quickSort(0, partition-1);” you should actually be doing “quickSort(left, partition-1);” because as it stands you are always trying to sort from the beginning of the array and makes it really really wrong. Once that is fixed it runs properly again though, so you should consider fixing it for any people looking at your code in the future.
Again, thanks for your help.

PhishHammer
Guest
PhishHammer

He’s right you know ^^… the algorithm will still sort, but will re-examine already sorted sections of the array with every recursive call to quick sort — which becomes extremely inefficient the larger the array size is. Even for sizes of 75-100 it will take several minutes. While with the adjustment, it runs almost instantly on my machine for an array of size 100000. helluva difference.

Hope you don’t put this on your CV ;)