Understanding and Improving an Insertion Sort Function

Sorting is a basic task in programming, and knowing how sorting works can help you solve many problems. In this post, we’ll look at a sorting function in TypeScript.

function sortArray(nums: number[]): number[] {
   for(let i = 1; i < nums.length; i++) {
      let j = i - 1;
      while(j >= 0 && nums[j + 1] < nums[j]) {
         let temp = nums[j + 1];
         nums[j + 1] = nums[j];
         nums[j] = temp;
         j--;
      }
   }
   return nums;
}

Working

• Looping through the numbers: The function starts with the second number in the list and moves through each number one by one.

• Comparing numbers: It compares the current number with the ones before it.

• Swapping if needed: If the current number is smaller than the one before it, the two numbers switch places.

• Finding the right spot: This continues until the current number is in the right spot, and then it moves on to the next number.

• Returning the sorted list: After going through all the numbers, the sorted list is returned.

Time Complexity and Stability

Time Complexity: The time it takes to run this function is O(n²) in the worst case and O(n) in case of sorted array.

Stable Sort: This sort is "stable," meaning if two numbers are the same, their order stays the same after sorting.

The Improved Function

function insertionSort(nums: number[]): number[] {
   for (let i = 1; i < nums.length; i++) {
      let currentValue = nums[i];
      let j = i - 1;

      // Move numbers that are bigger than currentValue one spot to the right
//nums[j + 1]  is the leftmost element of the unsorted array
// nums[j] is the rightmost element of the sorted array
      while (j >= 0 && nums[j] > currentValue) {
         nums[j + 1] = nums[j];
         j--;
      }

      // Place currentValue in its correct spot
      nums[j + 1] = currentValue;
   }
   return nums;
}

By moving the numbers instead of swapping each time, the function does less work.

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase