Answer to Question #168064 in Java | JSP | JSF for A

Question

Sort the sequence 40 6 18 20 99 5 21 43 3 by hand with (you may upload you hand writing sketches): write the time complexity for each sorting method.

1. Insertion sort

2. Selection sort

3. Quicksort (picking the last element as the pivot)

4. Quicksort (using the median-of-three pivot)

5. Heap sort

Answer 1

Time complexities in worst case:

1. Insertion sort - O(n²)

2. Selection sort - O(n²)

3. Quicksort (picking the last element as the pivot) - O(n²)

4. Quicksort (using the median-of-three pivot) - O(n²)

5. Heap sort - O(nlogn)

Given sequence: [40 6 18 20 99 5 21 43 3]

Picking 3 (last element as the pivot):

  40 6 18 20 99 5 21 43 3

  (3 is the pivot)

[]     [3]     [40 6 18 20 99 5 21 43]

           (43 is pivot)

        [40 6 18 20 5 21]   [43]   [99]

        (21 is pivot)

     [6 18 20 5]  [21]  [40]  

     (5 is pivot)  

      []  [5]  [6 18 20]                                

        (20 is pivot)

         [6 18] [20] []

         (18 is pivot)

       [6] [18] []  

Thus, sorted sequence is: [3 5 6 18 20 21 40 43 99]  

Finding median element from first element in sequence, middle element in sequence and last element in the given sequence ie, 40 99 3

median is 40 thus, our pivot is 40

           40 6 18 20 99 5 21 43 3

Swap 40,99,3 such that smallest of them is first,largets number is at last and median is in the middle.

This gives us:

3 6 18 20 40 5 21 43 99

                 3 6 18 20 40 5 21 43 99

                 (40 is the pivot)

              [3 6 18 20 5 21]   [40]   [43 99]

     from 3,18,21; 18 is median and

     all elemetns are in correct place

     Thus, 18 is our median

     [3 6 5] [18]  [20 21]  

as above, 5 is our

pivot element now thus,

  [3]  [5]  [6]

Thus, sorted sequence is [3 5 6 18 20 21 40 43 99]

import java.util.*;

class Main

{

  public static void boolean_sort(boolean arr[])

  {

     int len=arr.length;

     int false_count=0,true_count=0;

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

     {

        if(arr[i])

           true_count++;

        else

           false_count++;

     }

     int index=0;

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

     {

        arr[index]=false;

        index++;

     }

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

     {

        arr[index]=true;

        index++;

     }

  }

  public static void main(String args[])  

  {

     boolean arr[]={true, false, true, false, false};

     System.out.println(Arrays.toString(arr));  // prints [true, false, true, false, false]

     boolean_sort(arr);

     System.out.println(Arrays.toString(arr));  // prints [false, false, false, true, true]

  }  

}

def bitonic(arr):

  max_len=0     // max_len used to store length of max bitonic subarray

  start_index=-1  // start_index used to store first index of longest bitonic subarray

  length=arr.length  

  

  // traverse from 0 to end of array

  for i=0 to length-1:

     // traverse from i+1 to end of array

     for j=i+1 to length-1:

        // if length of subarray is greater than 2, then do the following

        if(j-i>=2):

           // start from i

           a=i

           // check for strictly increasing sequence

           while(a<j and arr[a]<arr[a+1]):

              a=a+1

           

           // if we have increasing sequence, then search for decreasing sequence

           if(a!=j):

              while(a<j and arr[a]>arr[a+1]):  

                 a=a+1

              // if at the end, the index is j, then update max_len values and start_index

              if(a==j):

                 if(max_len<j-i):

                    max_len=j-i

                    start_index=i

  

  // if start_index is -1, the return empty list

  if(start_index==-1):

     return []

  // else return subarray from start_index to max_len

  return arr[start_index:start_index+max_len+1]

print(bitonic([3,5,8,4,5,9,10,8,5,3,4]))  // prints [4,5,9,10,8,5,3]

print(bitonic([1,2,3,4,5]))              // prints []

print(bitonic([1,3,2,4,5]))              // prints [1,3,2]