Улучшение времени выполнения сортировки вставки

Question

Просто для того, чтобы попрактиковаться и улучшить свои навыки программирования, я решил решить вопросы на InterviewStreet. Я решил начать использовать простой InsertionSort (я ожидал, что это будет просто). https://www.interviewstreet.com/challenges/dashboard/#problem/4e90477dbd22b Я могу получить правильные ответы. Однако время выполнения является проблемой. Максимальное допустимое время выполнения для тестовых случаев - 5 секунд. Однако я немного за бортом. Я использовал несколько трюков (например, удаление чего-то из кода. Сохранение результата str.lenght() и т. Д.). Однако я все еще немного за борт.

В настоящее время автономной работы для десяти тестовых случаев являются:

1 Passed Успех 0.160537

2 Passed Успех 0.182606

3 Passed Успех 0.172744

4 Passed Успех 0,186676

5 Неверное превышение лимита времени. 5.19279

6 Сбой Превышен лимит времени. 5,16129

7 Зачет Успех 2,91226

8 Failed Ограничение по времени превышен. 5.14609

9 Сбой Превышен лимит времени. 5.14648

10 Неисправность превышена. 5.16734

Я не знаю, что такое тестовые примеры. Просьба помочь мне улучшить время выполнения. Спасибо.

import java.util.Scanner; 
import java.io.*; 
//import java.io.BufferedWriter; 
//import java.io.FileInputStream; 
//import java.io.FileOutputStream; 

public class Solution { 
    public static int[] A=new int[100001]; 
    public static int swap=0; 
    public static void InsertionSort(int n){ 
    for (int i=1; i<=n; i++){  
     for (int var=i; var>0; var--){ 
      if (A[var]<A[var-1]){ 
       int temp=A[var-1]; 
       A[var-1]=A[var]; 
       A[var]=temp; 
       swap++; 
      } 
      else { 
       break; 
      } 
     } 
    } 
    } 


    public static void main(String[] args) throws IOException { 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

     String str = br.readLine(); 
     int number_of_cases =Integer.parseInt(str); 
     int counter; 
     int [] spacearray = new int[100000]; 

     for (int j=0; j<number_of_cases; j++){ 
      swap=0; 
      str = br.readLine(); 
      int arraylength = Integer.parseInt(str); 

      str = br.readLine(); 
      counter=0; 
      int strlen=str.length(); 
      for (int i=0; i<strlen-1; i++){ 
       if (str.charAt(i) == ' '){ 
        spacearray[counter]=i; 
        counter++; 
       } 
      } 
      spacearray[counter]=strlen; 

      A[0]=Integer.parseInt(str.substring(0, spacearray[0])); 
      for (int i=1; i<=arraylength-1; i++){ 
       A[i] = Integer.parseInt(str.substring(spacearray[i-1]+1,spacearray[i])); 
      } 

      InsertionSort(arraylength-1); 

      System.out.println(swap); 
     } 
    } 
} 

Answer 1

Используйте бинарные индексированные деревья, чтобы решить эту проблему

Answer 2

Узким здесь алгоритм вставки сортировки. Сложность времени - это O (n^2) и с n до 10^5, можно легко превысить 5 секунд на машине для интервьюера. Также, когда выдается сигнал TLE, ваша программа перестает выполняться. Таким образом, незначительные накладные расходы до 5 на самом деле не являются показателем фактического времени, которое требуется для запуска. Он вводится задержка между обнаружением TLE и прекращением выполнения.

Для истории этот вопрос появился первоначально как часть кода-1. Использование сортировки вставки не является продолжением здесь, иначе вопрос был бы полной отдачей.

Подсказка

Используйте тот факт, что все значения будут в [1,10^6]. То, что вы действительно делаете здесь, - это найти количество инверсий в массиве A, т.е. найти все пары i < j s.t. A [i]> A [j]. Подумайте о структуре данных, которая позволяет вам найти количество свопов, необходимых для каждой операции вставки в логарифмической временной сложности (например, Binary Indexed Trees). Конечно, есть и другие подходы.