Question

John Smith teaches seven and eight year olds. Today is school picture day and everybody, including the teacher, has lined up in a single line for the class picture. Initially everyone has lined up in a random order. The photographer wants the following arrangement from left to right: first, all of the seven year olds, in order of increasing height. Next, Mr. Smith in the middle. Last, the eight year olds in decreasing order of height. The only adjustment allowed is a swap, in which two neighboring people swap their positions. Design an O(n log n) algorithm that computes the minimum number of swaps necessary to get the class into the desired order.

Answer 1

Since the class can be divided into two groups 7 year old group and the eight year old group , so we will make the pair of these students into 2 students in each group.

The code is in python:

def s(arr, N) :

    v = [False] * (N + 1)

    ms = 0

    for i in range(2 * N) :

        if (visited[arr[i]] == False) :

            visited[arr[i]] = True

            count = 0

for j in range( i + 1, 2 * N) :

  if (visited[arr[j]] == False) :

                    count += 1

elif (arr[i] == arr[j]) :

                    ms += count

     return ms

    arr = [] #student_entry

    N = len(arr)

    N //= 2

    print(s(arr, N))

The code till now will give the minimum no. of swaps needed to sort 7 year old we can insert the teacher here and the next piece of code will sort the 8 year old student.

def minSwaps(arr):

    n = len(arr)

      

    arrpos = [*enumerate(arr)]

      

    arrpos.sort(key = lambda it:it[1])

      

    vis = {k:False for k in range(n)}

      

    # Initialize result

    ans = 0

    for i in range(n):

          

        if vis[i] or arrpos[i][0] == i:

            continue

              

        cycle_size = 0

        j = i

        while not vis[j]:

              

            vis[j] = True

              

            

            j = arrpos[j][0]

            cycle_size += 1

        if cycle_size > 0:

            ans += (cycle_size - 1)

    return ans

  

    

arr = [] #student entry

print(minSwaps(arr))