JAVA | Quick sort with explaination
In-place,Not Stable,Not adaptive,Divide and conquer.\n\nFor primitive it is preferred and for objects merge sort is preferred. As merge sort takes extra o(n) me
In-place,Not Stable,Not adaptive,Divide and conquer.\n\nFor primitive it is preferred and for objects merge sort is preferred. As merge sort takes extra o(n) memory it is not preferred for array. But for linked list merge sort does not need extra space.\n\n# Approach\nWe will take one element as pivot(here the last one) and will try to put it in correct position. By correct position we mean that all element to the left of it are small and right to it are greater than pivot. So, basically we fixing pivot position one by one.\n\n![quickPartition.JPG](https://assets.leetcode.com/users/images/30ff6f60-bf82-4e78-b4ca-570d47db3331_1671347685.4171877.jpeg)\n\n\nSo,now swap high with low. and return low i.e. index 2. So,that we will have two partition {13,6} {17,15} now and index 2 element is fixed.\n\n# Complexity\n- Time complexity:\n $$O(nlogn)$$, but in worst case when data is already sorted it might go to $$O(n2)$$. To avoid worst case we can make pivot as random or mid element always.\n\n- Space complexity:\n$$O(logn)$$ if pivot chosen correctly. else it recursion call might take entire array length and hence will be $$O(n)$$ in worst case.\n\n# Code\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        quickSort(nums, 0, nums.length - 1);\n        return nums;\n    }\n    public void quickSort(int[] arr,int i, int j){\n       if (i < j) {\n\t\t\tint p = partition(arr, i, j); \n            // p is fixed and call quickSort again for left and right array\n\t\t\tquickSort(arr, i, p-1); \n\t\t\tquickSort(arr, p+1, j); \n\t\t}\n    }\n    public int partition(int[] arr,int l,int h) {\n        // In worst case it will be o(n^2). i.e. if data is already sorted\n\t\t// we can improve it by using middle element as pivot and then before starting\n\t\t// anything just swap it with high. so, that high will remain pivot.\n\n\t\t// Find mid of the array\n\t\tint mid = (low + high) / 2;\n\t\t// swap array element present in mid and high index\n\t\tswapIntArray(arr, mid, high);\n\t\t// now pivot is high again.\n\t\t// we goes from low till high-1 because high is reserved for pivot\n\t\tfor (int j = low; j < high; j++) {\n\t\t\tif (arr[j] < arr[high]) {\n\t\t\t\tswapIntArray(arr, j, low);\n\t\t\t\tlow++;\n\t\t\t}\n\t\t}\n\t\t// when j reached high,we know that low is in pivot position. so we just swap it\n\t\tswapIntArray(arr, high, low);\n\t\treturn low;\n    }\n    private void swapIntArray(int[] a, int i,int j){\n        int temp=a[i];\n        a[i]=a[j];\n        a[j]=temp;\n    }\n}\n```
['Sorting', 'Java']