Java swap question with complexity


  • 0

    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.


  • 0
    U

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


  • 0
    C

    I wrote some code for how I would do it.

    1. put 7 years olds on left, put 8 year olds on right (like Dutch flag partition)
    2. 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[N-1] = 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);
    	}
    }

  • 0
    O

    @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.


  • 0
    H

    Merge sort is the one you want to use


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.