Skip to content

Instantly share code, notes, and snippets.

@warlock2k
Created May 17, 2020 14:21
Show Gist options
  • Save warlock2k/25d01f8c478801563ac6dfa29b7b4f33 to your computer and use it in GitHub Desktop.
Save warlock2k/25d01f8c478801563ac6dfa29b7b4f33 to your computer and use it in GitHub Desktop.
class Solution
{
public int[] sortArray(int[] nums)
{
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int left, int right)
{
/* right = left
* This means you have recursed to base levels
* left and right represent indexes here.
* Basically we are making sure that the recursion happens until size of array is one.
*/
if(right >= left)
{
/* STEP - 1: Partitioning
* Partition function has two main goals.
* 1. Find the position of a pivot.
* 2. Modify nums array such that all elements less than pivot
* are arranged to left and greater to the right.
* So after partitioning we can exclude the pivot and select a new pivot.
*/
// It is good to select a random pivot. (This is a snippet for generating random numbers between left and right inclusive).
Random r = new Random();
int myRandomNumber = 0;
myRandomNumber = r.nextInt(right-left+1)+left;
// Here I am moving the random number to the left most part of the array, so that I
// can select it as my pivot.
int temp = nums[left];
nums[left] = nums[myRandomNumber];
nums[myRandomNumber] = temp;
int pivotPosition = partition(nums, left, right);
//Quick sort left
// It is important to understand that pivot is already in its correct position. So need need to include it.
quickSort(nums, left, pivotPosition - 1);
//Quick sort right
quickSort(nums, pivotPosition + 1, right);
}
}
public int partition(int[] nums, int left, int right)
{
// x is my pivot
int x = nums[left];
int i = left;
// i represents the pointer for boundary.
// j is simply for iteration.
for(int j = left + 1; j <= right; j++)
{
if(nums[j] <= x)
{
i++;
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
int temp = nums[i];
nums[i] = nums[left];
nums[left] = temp;
return i;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment