Design and Analysis of Algorithms CSC338 Agorithm Design (2018-08 Onsite) S. IS
ID: 3741867 • Letter: D
Question
Design and Analysis of Algorithms
CSC338 Agorithm Design (2018-08 Onsite) S. IS Points) Suppose you are given a partition algorithm, my_partition which takes an array ALL.R) of integers and produces three partitions as shown essentially it retuns two numbers P and Q which are indices to the right and left of the first and second boundaries, respectively of the partitions. In case of only one number in the middle partition, P-o Write a Divide-and-Conguer algorithm, my_sort which makes use of (calls) the my partition algorithm and sorts a given array A[0. 1Explanation / Answer
So these is the simple quick sort Algorithm. In quick sort we find one middle element in the array such that, all the elements left of the middle are less then the middle, and all the elements right to the middle are greater then the middle.
so array is divided in to three parts :-
one part elements containing the element less then the middle
second part is middle element
third part is elements containing the elements greater then the middle element.
then we will recursively call the function on 1st and 3rd part. Since second part has only one element hence no need to sort it.
The implementation of quick sort algorith is given below
public class QuickSortDemo {
public static void main(String[] args) {
int[] numbers = new int[] {1,2,3,7,6,5,4,8,9,10,15,13,14,12,11};
int start = 0;
int end = numbers.length-1;
quickSort(numbers,start,end);
for(int i=0;i<=end;i++) {
System.out.println(numbers[i]);
}
}
private static void quickSort(int[] numbers, int start, int end) {
if(start<end) {
int mid = middle(numbers, start, end);
quickSort(numbers,start,mid-1);
quickSort(numbers, mid+1, end);
}
}
private static int middle(int[] numbers, int start, int end) {
int pivot = numbers[start];
int p = start+1;
int q = end;
while(q>=p){
if(p<=numbers.length-1)
while(numbers[p]<pivot) {
p++;
if(p>=numbers.length-1)
break;
}
if(q>=0)
while(numbers[q]>pivot) {
q--;
if(q<0)
break;
}
if(q>=p) {
int temp = numbers[p];
numbers[p]= numbers[q];
numbers[q]=temp;
}
}
if(q<p) {
numbers[start]=numbers[q];
numbers[q]=pivot;
}
return q;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.