Sorting an array

Given an array of integers, nums sorting the array without using any build in fuction.
Input: [-1, 0, 1, 2, -1, -4]
Output: [-4, -1, -1, 0, 1, 2]

I will use two approach for sorting array. Bubble sort and quick sort.

Thought Process:

Minimal Approach

• Here i will use bubble sort algorithm to sort this array.
• Compare adjacent element of the array.
• If they are wrong order then swap like arr[j] to arr[j+1].
• Keep swapping untill array is sorted.

Optimal Approach

• I will use quick sort algorithm to sort this array.
• Use Devide and conquer technique.
• Pick a pivot element
• Partition the array:
• If element smaller then pivot move left side.
• If element larger then pivot move right side.

Brute-force Approach:

Minimal Approach

for i = 0 to n-1
   for j = 0 to n-2
      if arr[j] > arr[j+1]
         swap(arr[j], arr[j+1])

Optimal Approach

quicksort(arr):
   if length(arr) <= 1 return arr

   pivot = arr[last]
   left = elements < pivot
   right = elements >= pivot

   return quicksort(left) + pivot + quicksort(right)

Visualization: [5, 3, 8, 4, 2]

Pick pivot=2
[5,3,8,4] | 2 | []
          ↓
Sort left: []            Sort right: [5,3,8,4]
                         Pivot=4
                         [3] | 4 | [5,8]

Final result:
[2] + [3,4,5,8] → [2,3,4,5,8]

Time and Space Complexity

• Time Complexity: For bubble sort: O(n²) and quick sort: O(n log n)
• Space Complexity: For bubble sort: O(1) and quick sort: O(log n).

JavaScript Solution

const bubbleSort = function (nums) {
  let n = nums.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        let temp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = temp;
      }
    }
  }
  return nums;
};

const quickSort = function (nums) {
  let n = nums.length;
  if (n <= 1) return nums;
  let pivot = nums[n - 1];
  let left = [];
  let right = [];
  for (let i = 0; i < n - 1; i++) {
    if (nums[i] < pivot) {
      left.push(nums[i]);
    } else {
      right.push(nums[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
};