Quick Sort in Java

1. Time complexity : O(n*n) - Worst case , O(nlogn) - Best Case
2. Space complexity : O(logn) - height of recursion tree

Best case :

n/2^k = 1 
2^k = n 
k= log(n)
 Worst case :
Worst case occur when when the pivot partition the array in an extreme way e.g.
one array is empty and other array contains n-1 elements. 

So, for calculating quick sort time complexity in the worst case, 
we put i = n — 1 in the above equation of 
T(n) => T(n) = T(n — 1) + T(0) + cn = T(n — 1) + cn . 
In this method, we draw the recursion tree and sum the partitioning cost 
for each level => cn + c(n−1) + c(n−2) +⋯+ 2c + c ​= 
c (n + n−1 + n−2 + ⋯+ 2 + 1) = c(n(n+1)/2) = O(n²). 
So worst case time complexity of quick sort is O(n²).

_______________

    static void swap(int arr[],int a,int b){
        int temp =arr[a];
        arr[a]=arr[b];
        arr[b] = temp;
    }
    
    static void quickSort(int arr[], int low, int high)
    {
        // code here
        
        if(high>low){
            int piv = partition(arr,low,high);
            quickSort(arr,low,piv-1);
            quickSort(arr,piv+1,high);
        }
    }
    static int partition(int arr[], int low, int high)
    {
        // your code here
        
        int piv = low;
        int i = low;
        int j = high;
        
        while(i<j){
            while(arr[i]<=arr[piv] && i<=high-1){i++;}
            while(arr[j]>arr[piv] && low+1<=j){j--;}
            
            if(i<j){
                swap(arr,i,j);
            }
        }
        
        swap(arr,piv,j);
        return j;
        
    } 

 Time Complexity of important sorting algorithms

Time Complexity of important sorting algorithms

Given an unsorted array arr[] of size N. Rotate the array to the left (counter-clockwise direction) by D steps, where D is a positive integer.

 Rotate the array to the left (counter-clockwise direction) by D steps in O(n) time

1. Time complexity : O(n)
2. Space Complexity : O(1)

If D is the number of steps and N is the number of element in the array. First find the D%N to reduce the number of steps. If D>N ,then we have to same steps D/N times. 

Now partition the array taking d as pivot. Reverse the array from arr[0] to arr[d-1] and arr[d] to arr[n-1]. 

Eg : If the array is 

1 2 3 4 5, where d=2 and n=5

after taking d as pivot the new array will be  2 1 5 4 3

Now reverse the whole array . Over all time complexity will be O(n)

_____________________

 static void rotateArr(int arr[], int d, int n)

    {

       

        d = d%n;

        

        int temp;

        

        for(int i=0;i<d/2;i++){

            temp = arr[i];

            arr[i] = arr[d-1-i];

            arr[d-1-i] = temp;

        }

        

        for(int i=d;i<(n+d)/2;i++){

            temp = arr[i];

            arr[i] = arr[n+d-1-i];

            arr[n+d-1-i] = temp;

        }

        

        for(int i=0;i<n/2;i++){

            temp = arr[i];

            arr[i] = arr[n-1-i];

            arr[n-1-i] = temp;

        }

        

        

    }

 

Reverse a string in Java without using any inbuilt function

 Reverse a string in Java without using any inbuilt function 

1. Time Complexity : O(n)
2. Space Complexity : O(n)

public static String reverseWord(String str)
    {
        // Reverse the string str
        
        int n = str.length();
        String temp="" ;
        
        for(int i=n-1;i>=0;i--){
            
            temp+=str.charAt(i);
            
        }
        
        return temp;
    }