Albert Grithum 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. Grithum 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.
Complexity should be O(n log n) that computes the minimum number of swaps necessary to get the class into the desired order.
Java swap question with complexity


@ritikashah017gmail.com my idea, is to do bubble sorting for 7 years olds first, treating teacher and 8 years old as semiinfinite and infinite. after that, do reverse bubble sorting for 8 years old.

I wrote some code for how I would do it.
 put 7 years olds on left, put 8 year olds on right (like Dutch flag partition)
 sort 7 year olds, sort 8 year olds
Time: O(N lg N)
import java.util.Arrays; import java.util.Comparator; public class PictureDay { class Student { int age; int height; Student(int age, int height) { this.age = age; this.height = height; } } static class IncreasingHeight implements Comparator<Student> { public int compare(Student x1, Student x2) { return x1.height  x2.height; } } static class DecreasingHeight implements Comparator<Student> { public int compare(Student x1, Student x2) { return x2.height  x1.height; } } PictureDay(int numStudents, double alpha) { Student[] students = new Student[1+numStudents]; int N = students.length; for (int i = 0; i < N  1; i++) { if (Math.random() < alpha) students[i] = new Student(7, i); else students[i] = new Student(8, i); } students[N1] = new Student(7, Integer.MAX_VALUE); // professor arrangeStudents(students); } void printStudents(Student[] students) { for (Student s : students) { System.out.print("("+s.age+","+s.height+") "); } System.out.println(); } void arrangeStudents(Student[] students) { System.out.println("Initial lineup"); printStudents(students); int N = students.length  1; int i = 0, j = N; while (i < j) { while (students[i].age == 7) i++; while (students[j].age == 8) j; if (i < j) exch(students, i, j); } System.out.println("Swapped by ages"); printStudents(students); Arrays.sort(students, 0, i, new IncreasingHeight()); Arrays.sort(students, i, N, new DecreasingHeight()); System.out.println("Sorted by heights"); printStudents(students); } void exch(Student[] students, int i, int j) { Student temp = students[i]; students[i] = students[j]; students[j] = temp; } public static void main(String[] args) { new PictureDay(10, .25); } }

@ritikashah017gmail.com said in Java swap question with complexity:
The only adjustment allowed is a swap, in which two neighboring people swap their positions.
Complexity should be O(n log n) that computes the minimum number of swaps necessary to get the class into the desired order.Neither of the proposed solutions meet both of these conditions. I can't do it either.