Modify the quicksort algorithm so that it sorts Strings instead of integers. Pro
ID: 653453 • Letter: M
Question
Modify the quicksort algorithm so that it sorts Strings instead of integers. Provide code for the partition and quicksort methods, as well as for any helper methods you might need to use (such as swap).
public static void quickSort(int [] a, int start, int end) {
if (start<end) { // general case int pivot = partition(a, start, end);
// sort left sublist
quicksort(a,start,pivot-1);
// sort the right sublist
quicksort(a,pivot+1,end);
}
}
public static int partition(int [] a, int start, int end) {
int pivot;?
int endOfLeft;
?int midIndex = (start+end)/2;
swap(a,start,midIndex);
pivot=a[start];?
endOfLeft=start;?
for (int i=start+1; i<=end; i++) {
if (a[i]<pivot) {
endOfLeft=endOfLeft+1;
swap(a,endOfLeft,i);
}
}
swap(a,start,endOfLeft);
return endOfLeft;
}
Explanation / Answer
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class QuickSort {
static String[] strings;
@SuppressWarnings("resource")
public static void main(String[] args) {
List<String> values = new ArrayList<>();
System.out.println("Please Enter Number of Strings you want to sort!!");
Scanner input = new Scanner(System.in);
int numofStrings = input.nextInt();
for (int i = 0; i < numofStrings; i++) {
System.out.println("Please Enter ");
String string = input.next();
values.add(string);
}
strings = new String[numofStrings];
values.toArray(strings);
System.out.println("Before Sorting");
for (int i = 0; i < strings.length; i++) {
System.out.print(strings[i] + " ");
}
System.out.println("");
qsort(0, strings.length - 1);
System.out.println("The array, quicksorted: ");
for (int i = 0; i < strings.length; i++) {
System.out.print(strings[i] + " ");
}
System.out.println(" ");
}
static void qsort(int low, int high) {
int i = low, j = high;
// Get the pivot element
int pivot = low + (high - low) / 2;
String value = strings[pivot];
// Divide into two lists
while (i <= j) {
while (strings[i].compareTo(value) < 0) {
i++;
}
while (strings[j].compareTo(value) > 0) {
j--;
}
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// Recursion
if (low < j) {
qsort(low, j);
}
if (i < high) {
qsort(i, high);
}
}
static void exchange(int i, int j) {
String temp = strings[i];
strings[i] = strings[j];
strings[j] = temp;
}
}
Sample:
Please Enter Number of Strings you want to sort!!
6
Please Enter
frog
Please Enter
apple
Please Enter
dog
Please Enter
cat
Please Enter
ice
Please Enter
gem
Before Sorting
frog apple dog cat ice gem
The array, quicksorted:
apple cat dog frog gem ice
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.