Question

Sorting Sort the following array using the quick sort algorithm: (4 Marks) a. 12 26 8 9 7 0 4 Pivot selection is defined to be the first element of each sub-list. Show the array before and after each quicksort round (when the array is partitioned after placing the pivot at its correct position). Also, clearly highlight the pivot in each partition b. Consider an unsorted array of integers of size n. Write a Java program to arrange the array so that all negative values appear before non-negative values in the array. Your solution should require no more than (n) time and (1) extra space. For example the list -5, 10, 3, -2, 1, 01 could be arranged as-5, -2, 3, 10, ,0. (Hint : recall the partitioning technique used in quick sort.) (4 Marks) provided with a function getMin) c. Consider the Selection Sort algorithm and assume you are returns the index of the minimum element in a given array. The function also takes as parameter the startIndex and endlndex, and the search for minimum is performed in this range. Write a modified version of the Selection Sort algorithm (in any programming language) that uses this getMin) to perform sorting of an array in descending order (from largest to smallest). Explain the run time and space complexity of your algorithm. (State and justify assumptions for getMin)) on the runtime (3+1+1 Marks) LO

Answer 1

Ques1

package sort;

/*pseudo code
* sort( ar[], low, high):
*    if low<hight{
*    int pi=partition(ar,low,high)
*        sort(ar,low,pi)
*        sort(ar,pi,high)
*        }
* partition(ar[],low,high){
*    int p=ar[low]
*    int j=high
*    while i<-high+1 greater then l{
*    if ar[j] less then p{
*            i--
*            swap ar[i],ar[j]
*            j--
*        }
* swap ar[i-1],ar[l]
* return i-1
*    }
* }
*/
public class QuickSort
{
static int k=1;
public static int part(int ar[], int l, int h)
{
int p = ar[l]; //to first element for array as pivote   
int j=h; //j as highest
int i = (h+1); //after highest index
while (j>l) //run loop j greater the low
{
  
if (ar[j]>= p) { //if jth element greater then p
  
i--; //swap ith and jth element
int t = ar[i];
ar[i] = ar[j];
ar[j] = t;
}
j--; //go to lower element
}   
  
int t = ar[i-1]; //swap pivot if it is not at right place
ar[i-1] = ar[l];
ar[l] = t;
return i-1;
}
  
public static void sort(int ar[], int l, int h)
{
if (l < h)
{
   //using divide and concor
int pi = part(ar, l, h); //find pivote index
System.out.println("Swap :"+(k++)+" Pivot: "+ar[pi]);
for (int i=0; i<ar.length; ++i)
System.out.print(ar[i]+" ");
System.out.println();
sort(ar, l, pi-1); //sort array before pivot
sort(ar, pi+1, h); //after pivot
}
}
  
// Driver program
public static void main(String args[])
{
int ar[] = {4,0,12,2,6,1,8,5,9,7};
System.out.println("Initial array "+"\n Pivot: "+ar[0]);
for (int i=0; i<ar.length; ++i)
System.out.print(ar[i]+" ");
System.out.println();
sort(ar, 0, ar.length-1);
System.out.println("Sorted Array:");
for (int i=0; i<ar.length; ++i)
System.out.print(ar[i]+" ");
  
}
}

output

Initial array
Pivot: 4
4 0 12 2 6 1 8 5 9 7
Swap :1 Pivot: 4
2 0 1 4 12 6 8 5 9 7
Swap :2 Pivot: 2
1 0 2 4 12 6 8 5 9 7
Swap :3 Pivot: 1
0 1 2 4 12 6 8 5 9 7
Swap :4 Pivot: 12
0 1 2 4 7 6 8 5 9 12
Swap :5 Pivot: 7
0 1 2 4 5 6 7 8 9 12
Swap :6 Pivot: 5
0 1 2 4 5 6 7 8 9 12
Swap :7 Pivot: 8
0 1 2 4 5 6 7 8 9 12
Sorted Array:
0 1 2 4 5 6 7 8 9 12

Ques2

package sort;
/*Time complexity =O(N)
* as it is comparing each element(0,n) to piovt and swapping
* Space complexity=O(1) no extra space needed to store array element
*
*/

public class SeperateNegativeElement {

   public static void arrangeNegAndPos(int ar[]) {
  
   int pivot=0; //initiate pivot as 0th index
   for (int i = 0; i < ar.length; i++) { //from 0 to n
  
       if (ar[i] < 0) { //if ith element -ve
   if (i != pivot) { //and ith index is not pivot
   int temp = ar[i]; //swap them
   ar[i] = ar[pivot];
   ar[pivot] = temp;
   }
   pivot++; //now increase the pivot
   }
   }
   }
   public static void main(String[] args) {
       int[] ar = {-5,10,3,-2,1,0};
       arrangeNegAndPos(ar);
       for(int i:ar){
  
   System.out.print(i);
   System.out.print(", ");
   }

   }

}

output

-5, -2, 3, 10, 1, 0,

Ques 3.

public class SelectionSort {
   public static void selSort(int[] arr){

   for (int i=0;i<arr.length;i++)
   {
       // int smallerNumber = arr[i]; //make current element as smallest
       int index=getMin(arr,i,arr.length-1);
      
  
         
     
   if(index!=-1){ //if smallest found
   int smallerNumber=arr[i]; //swap it
   arr[i]=arr[index];
   arr[index] = smallerNumber;
   }
   }
     
  
   }

   public static int getMin(int arr[],int startIndex,int endIndex){
       int index=startIndex;
       for(int j=startIndex+1;j<=endIndex;j++){ //find smallest element in ar[i.....n]
      
    if(arr[index]<arr[j]){   
       
        index=j; //remember i of smallest
    }
       }
    return index;
   }
   public static void main(String[] args) {
     
int[] arrayOne = {10,34,2,56,12,64,18,14,43,52,69,
7,67,88,42,27,45,6,19,39,34,51,70};
selSort(arrayOne);
for(int i:arrayOne){
  
System.out.print(i);
System.out.print(", ");
}

   }

}

output

88, 70, 69, 67, 64, 56, 52, 51, 45, 43, 42, 39, 34, 34, 27, 19, 18, 14, 12, 10, 7, 6, 2,

Answer 2

// Java implementation of QuickSort

import java.io.*;

class GFG{

// A utility function to swap two elements

static void swap(int[] arr, int i, int j)

{

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

/* This function takes last element as pivot, places

the pivot element at its correct position in sorted

array, and places all smaller (smaller than pivot)

to left of pivot and all greater elements to right

of pivot */

static int partition(int[] arr, int low, int high)

{

// pivot

int pivot = arr[high];

// Index of smaller element and

// indicates the right position

// of pivot found so far

int i = (low - 1);

for(int j = low; j <= high - 1; j++)

{

// If current element is smaller

// than the pivot

if (arr[j] < pivot)

{

// Increment index of

// smaller element

i++;

swap(arr, i, j);

}

}

swap(arr, i + 1, high);

return (i + 1);

}

/* The main function that implements QuickSort

arr[] --> Array to be sorted,

low --> Starting index,

high --> Ending index

*/

static void quickSort(int[] arr, int low, int high)

{

if (low < high)

{

// pi is partitioning index, arr[p]

// is now at right place

int pi = partition(arr, low, high);

// Separately sort elements before

// partition and after partition

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

}

// Function to print an array

static void printArray(int[] arr, int size)

{

for(int i = 0; i < size; i++)

System.out.print(arr[i] + " ");

System.out.println();

}

// Driver Code

public static void main(String[] args)

{

int[] arr = { 10, 7, 8, 9, 1, 5 };

int n = arr.length;

quickSort(arr, 0, n - 1);

System.out.println("Sorted array: ");

printArray(arr, n);

}

}