Skip to content

Instantly share code, notes, and snippets.

@wangtzINT

wangtzINT/bubblesort1.java

Last active December 13, 2015 17:39
Show Gist options
  • Save wangtzINT/4949588 to your computer and use it in GitHub Desktop.
Save wangtzINT/4949588 to your computer and use it in GitHub Desktop.
Download ZIP
Topcoder 469 DIV 1 250 A good practice for sort algorithm!
Raw
bubblesort1.java
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;
public class TheMoviesLevelOneDivOne
{
public long find(int n, int m, int[] row, int[] seat)
{
sort(row, seat, 0, seat.length-1);
for(int i=0; i<seat.length; i++){
//System.out.print(row[i] + " ");
//System.out.println(seat[i]);
}
long count = 0;
int last =0, next = last+1;
if(last < seat.length){
count += countSeat(seat[last]-1) + (long)(m-1) * (row[last]-1);
for(; next<seat.length; last ++, next++){
if(row[last] == row[next]){
count+= countSeat(seat[next]-seat[last]-1);
}else{
count+= countSeat(m-seat[last]) + (long)(m-1) * (row[next]-row[last]-1) + countSeat(seat[next]-1);
}
}
count += countSeat(m-seat[last]) + (long)(m-1) * (n-row[last]);
}else{
count += (long)(m) * (n-1);
}
return count;
}
private long countSeat(int capacity){
return (capacity - 1 > 0)? (capacity-1):0;
}
private void sort(int[] row, int[] seat, int start, int end){
// incremental order
for(int i=end; i>start; i--){
boolean isFinished = true;
for(int j=start; j<i; j++){
if(isSmallerThan(j+1, j, row, seat)){
swap(j+1, j, row, seat);
isFinished = false;
}
}
if(isFinished) break;
}
}
private void swap(int i, int j, int[] row, int[] seat){
swap(i, j, row);
swap(i, j, seat);
}
private void swap(int i, int j, int[] arr){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private boolean isSmallerThan(int i, int j, int[] row, int[] seat){
if(row[i] < row[j]) return true;
else if(row[i] == row[j] && seat[i] < seat[j]) return true;
return false;
}
private boolean isSmallerOrEqualThan(int i, int j, int[] row, int[] seat){
if(row[i] < row[j]) return true;
else if(row[i] == row[j] && seat[i] <= seat[j]) return true;
return false;
}
}
//Powered by [KawigiEdit] 2.0!
Raw
quicksort1.java
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;
public class TheMoviesLevelOneDivOne
{
public long find(int n, int m, int[] row, int[] seat)
{
sort(row, seat, 0, seat.length-1);
for(int i=0; i<seat.length; i++){
//System.out.print(row[i] + " ");
//System.out.println(seat[i]);
}
long count = 0;
int last =0, next = last+1;
if(last < seat.length){
count += countSeat(seat[last]-1) + (long)(m-1) * (row[last]-1);
for(; next<seat.length; last ++, next++){
if(row[last] == row[next]){
count+= countSeat(seat[next]-seat[last]-1);
}else{
count+= countSeat(m-seat[last]) + (long)(m-1) * (row[next]-row[last]-1) + countSeat(seat[next]-1);
}
}
count += countSeat(m-seat[last]) + (long)(m-1) * (n-row[last]);
}else{
count += (long)(m) * (n-1);
}
return count;
}
private long countSeat(int capacity){
return (capacity - 1 > 0)? (capacity-1):0;
}
private void sort(int[] row, int[] seat, int start, int end){
// quick sort
int len = end - start + 1;
if(len <= 1){
return;
}else{
int pivot = (end + start)/2;
pivot = partition(row, seat, start, end, pivot);
sort(row, seat, start, pivot -1);
sort(row, seat, pivot+1, end);
}
}
private int partition(int[] row, int[] seat, int start, int end, int pivot){
// we already know that len > 1
// return pivot': new position of pivot element
// output: a[i] < a[pivot'] -> i<pivot', same for >
swap(pivot, end, row, seat);
int startP = start, endP = end-1;
while(startP <= endP){
if(isSmallerThan(startP, end, row, seat)){
startP++;
}else if(isSmallerOrEqualThan(end, endP, row, seat)){
endP--;
}else{
swap(startP, endP, row, seat);
startP++;
endP--;
}
}
swap(endP+1, end, row, seat);
return endP+1;
}
private void swap(int i, int j, int[] row, int[] seat){
swap(i, j, row);
swap(i, j, seat);
}
private void swap(int i, int j, int[] arr){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private boolean isSmallerThan(int i, int j, int[] row, int[] seat){
if(row[i] < row[j]) return true;
else if(row[i] == row[j] && seat[i] < seat[j]) return true;
return false;
}
private boolean isSmallerOrEqualThan(int i, int j, int[] row, int[] seat){
if(row[i] < row[j]) return true;
else if(row[i] == row[j] && seat[i] <= seat[j]) return true;
return false;
}
}
//Powered by [KawigiEdit] 2.0!
Raw
quicksort2.java
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;
public class TheMoviesLevelOneDivOne
{
public long find(int n, int m, int[] row, int[] seat)
{
sort(row, seat, 0, seat.length-1);
for(int i=0; i<seat.length; i++){
//System.out.print(row[i] + " ");
//System.out.println(seat[i]);
}
long count = 0;
int last =0, next = last+1;
if(last < seat.length){
count += countSeat(seat[last]-1) + (long)(m-1) * (row[last]-1);
for(; next<seat.length; last ++, next++){
if(row[last] == row[next]){
count+= countSeat(seat[next]-seat[last]-1);
}else{
count+= countSeat(m-seat[last]) + (long)(m-1) * (row[next]-row[last]-1) + countSeat(seat[next]-1);
}
}
count += countSeat(m-seat[last]) + (long)(m-1) * (n-row[last]);
}else{
count += (long)(m) * (n-1);
}
return count;
}
private long countSeat(int capacity){
return (capacity - 1 > 0)? (capacity-1):0;
}
private void sort(int[] row, int[] seat, int start, int end){
// incremental order
int len = end - start + 1;
if( len<=1 ) return;
else{
int pivot = (start+end)/2;
pivot = partition(row, seat, start, end, pivot);
sort(row, seat, start, pivot-1);
sort(row, seat, pivot+1, end);
}
}
private int partition(int[] row, int[] seat, int start, int end, int pivot){
// len >= 2
swap(pivot, end, row, seat);
int startP = start, endP= end-1; // elements before startP and after endP are sorted
while(startP <= endP){
if(isSmallerThan(startP, end, row, seat)){
startP++;
}else if(isSmallerOrEqualThan(end, endP, row, seat)){
endP--;
}else{
swap(startP, endP, row, seat);
startP++;
endP--;
}
}
swap(endP + 1, end, row, seat);
return endP+1;
}
private void swap(int i, int j, int[] row, int[] seat){
swap(i, j, row);
swap(i, j, seat);
}
private void swap(int i, int j, int[] arr){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private boolean isSmallerThan(int i, int j, int[] row, int[] seat){
if(row[i] < row[j]) return true;
else if(row[i] == row[j] && seat[i] < seat[j]) return true;
return false;
}
private boolean isSmallerOrEqualThan(int i, int j, int[] row, int[] seat){
if(row[i] < row[j]) return true;
else if(row[i] == row[j] && seat[i] <= seat[j]) return true;
return false;
}
}
//Powered by [KawigiEdit] 2.0!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment