Question

Create a quick and merge sort algorithm that sorts 6 9 8 12 3 1 7

In java please.

Answer 1

CODE:

OUTPUT:

RAW CODE:

import java.util.*; // for Arrays.toString(array)
class quick_sort {

    void sort(int array[], int low, int high)
   {
       if (low < high)
       {
           int pi = partition(array, low, high); // correct place
           sort(array, low, pi-1); // sorting
           sort(array, pi+1, high); // sorting
       }
   }

   int partition(int array[], int low, int high)
   {
       int i = low-1 , j ,temp;
       int pivot = array[high]; // takes last element as pivot
       for (j=low; j<high; j++)
       {
           if (pivot > array[j] ) // if the j'th value is smaller then the pivot element then increment i and swap i'th and j'th elements
           {
               ++i;
               temp = array[j];
               array[j] = array[i];
               array[i] = temp;
           }
       }
       // at last swap i+1'th position value and high position value
       temp = array[high];
       array[high] = array[i+1];
       array[i+1] = temp;

       return i+1;
   }
  
}
class merge_sort {
   void merge(int array[], int left, int middle, int right)
   {
       // creating two new arrays : left_array[l : m] and right_array[m+1 : r]
       int size1 = middle - left + 1;
       int []left_array = new int[size1];

       int size2 = right - middle;
       int []right_array = new int[size2];

       int i,j;
       // assiging values from array to left_array and right_array
       for (i = 0; i < size1; ++i)
           left_array[i] = array[left + i];
       for (j = 0; j < size2; ++j)
           right_array[j] = array[middle + 1 + j];

       // merging two arrays from index 0
       i = 0;
       j = 0;
       int k = left;
       while (i < size1 && j < size2) {
           if (left_array[i] <= right_array[j]) { // checking if the left_array[i] is less than or equal to right_array[j] , if it is
               array[k] = left_array[i]; // then assign left_array[i] value to array[k]
               i++; // increase 'i' value means go to next element of left_array
           }
           else {
               array[k] = right_array[j]; // else assign right_array[i] value to array[k]
               j++; // increase 'j' value means go to next element of right_array
           }
           k++; // increase 'k' value means go to next element of array
       }

       // if the left_array is completed and right_array is remaining then add right_array to array at last
       while (j < size2) {
           array[k] = right_array[j];
           j++;// go to next element of right_array
           k++;
       }

       // if the right_array is completed and left_array is remaining then add left_array to array at last
       while (i < size1) {
           array[k] = left_array[i];
           i++; // go to next element of left_array
           k++; // go to next element of array
       }

      
   }
   // sort method
   void sort(int array[], int left, int right)
   {
       if (left < right) {
           int middle = (left + right) / 2; // middle
           sort(array, left, middle); // sorting first half
           sort(array, middle + 1, right); // sorting second half
           merge(array, left, middle, right); // merging two halfs
       }
   }
}
public class Main{
   public static void main(String args[])
   {
       int array1[] = {6, 9, 8, 12, 3, 1,7}; // given array
       int array2[] = {6, 9, 8, 12, 3, 1,7}; // given array
       System.out.println("Array Before Sorted : ");
       System.out.println(Arrays.toString(array1));

       quick_sort quick = new quick_sort(); // creating new quick_sort instance
       quick.sort(array1, 0, array1.length - 1 ); // calling sort method
       System.out.println("Quick Sort : ");
       System.out.println(Arrays.toString(array1)); // printing array after sorted

       merge_sort merge = new merge_sort(); // creating new merge_sort instance
       merge.sort(array2, 0, array2.length - 1); // calling sort method
       System.out.println("Merge Sort : ");
       System.out.println(Arrays.toString(array2)); // printing array after sorted
   }
}

NOTE:
If You have any doubts feel free to comment in comment section.
DO VOTE(LIKE).