So, apparently there are cases in which my algorithm needs less changes of pivot to complete the sorting of the list. My algorithm does in fact sort the list correctly but the Number of pivots is less or equal to the examples I have been given. One example given in my assignment is this array:
3 45 12 -3 4 -3 21 0 6 20
This is how the Output is supposed to look like:
Number of pivots: 7
First Element: -3
Last Element: 45
This is what I get:
Number of pivots: 5
First Element: -3
Last Element: 45
With another example it works with the right amount of pivots:
9 2 4 7 3 7 10 11 12 13 13 10 13 13
What I should get and also what I get:
Number of pivots: 10
First Element: 2
Last Element: 13
I'm especially confused that it works in some cases and in others it doesnt.
Here is the code:
public static void quickSort(int[] arr, int start, int end, CountObject count){
int partition = partition(arr, start, end, count);
//partition will return the position the pivot. The pivot will be at the right place, hence if either side
//of the pivot consists of only one element, it should not be sorted
//check whether the part left from the pivot should still be sorted
if(partition-1>start) {
quickSort(arr, start, partition - 1, count);
}
//check whether the part right from the pivot should still be sorted
if(partition+1<end) {
quickSort(arr, partition + 1, end, count);
}
}
public static int partition(int[] arr, int start, int end, CountObject count){
int pivot = arr[start];
count.increaseCount();
//checks if left pointer < pivot
for(int i=end; i>start; i--){
if(arr[i]>pivot){
int temp= arr[end];
arr[end]=arr[i];
arr[i]=temp;
end--;
}
}
int temp = arr[start];//=pivot
arr[start] = arr[end];
arr[end] = temp;
return end;
}
}
I'm using a CountObject class to count. It contains a method increaseCount and an instance variable count.
So I finally figured it out. I had to use another technique to traverse through the list. In my OP I used the first element as pivot and compared it with all the elements beginnign from the end of the list. Now I start with the 2nd element of the list / the current sublist.
Here is the Code that solved my problem, I hope this will spare someone 2 days of work though it was educational for me to do it myself.
import java.util.Scanner;
public class Quickie {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int temp;
int size = sc.nextInt();
int[] list = new int[size];
for (int i = 0; i < size; i++) {
temp = sc.nextInt();
list[i] = temp;
}
int end = size - 1;
CounterClass count = new CounterClass(0);
quickSort(list, 0, end, count);
int firstElement = list[0];
int lastElement = list[size - 1];
System.out.println("Number of pivots: " + count.getCount());
System.out.println("First Element: " + firstElement);
System.out.println("Last Element: " + lastElement);
}
private static void quickSort (int []arr, int start, int end, CounterClass count){
int partition = partition(arr, start, end, count);
if (partition-1>start){
quickSort(arr, start, partition-1,count);
}
if (partition+1<end){
quickSort(arr, partition+1,end,count);
}
}
private static int partition (int[]arr, int start, int end, CounterClass count){
int pivot = arr[start];
count.count++;
int pointer = start+1;
int i =pointer;
for (int j=pointer; j<=end;j++){
if (arr[j]<pivot){
int temp = arr[j];
arr[j]=arr[i];
arr[i]=temp;
i++;
}
}
i-=1;
int temp=arr[start];
arr[start]=arr[i];
arr[i]=temp;
return (i);
}
}
class CounterClass{
int count;
public CounterClass(int count){
this.count = count;
}
public int getCount() {
return count;
}
}