ADJSRT - Editorial

editorial
, ,
1

Problem Link - Sort by Adjacent Swaps Practice Problem in Jump from 2* to 3*

Problem Statement:

You are given an array A (of size n) and you can only perform the adjacent swaps on the array, i.e. you can choose an index i (0≤i≤n−2) and swap the values present in A_i and A_i+1.
Sort the array using minimum number of adjacent swap operations.

Approach:

The problem can be solved using a modified version of bubble sort:

  1. Basic Bubble Sort Concept:
  • Traverse the array from the beginning to the end.
  • If the current element is greater than the next element, swap them.
  • Repeat this process until the array is sorted.
  1. Tracking Swaps:
  • Maintain a counter for the number of swaps performed.
  • Store the indices of each swap in a vector or array for output.
  1. Stopping Condition:
  • If a full pass through the array results in no swaps, the array is already sorted.

Implementation Steps:

  • Initialize an array or list to keep track of the indices where swaps are made.
  • Initialize a counter for the number of swaps.
  • Perform the bubble sort:
    • Traverse the array from the beginning to the end.
    • Compare each element with the next one.
    • If the current element is greater than the next, swap them and record the index.
    • Increment the swap counter each time a swap is made.
  • Repeat the above process until no swaps are needed (indicating that the array is sorted).
  • Output the total number of swaps and the recorded indices.

Complexity:

  • Time Complexity: O(n^2) in the worst case, where n is the size of the array. This occurs when the array is sorted in reverse order.
  • Space Complexity: O(m), where m is the number of swaps, to store the indices.