Домашка по алгоритмам (#2)

Итак, вот моя домашка по алгоритмам.Сортировка вставкой с бинарным поиском индекса для вставки.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.lang.Comparable;

public class sorting {
public static void main (String [] args) {
List test = new ArrayList();
Random generator = new Random();
for (int i = 0; i < 10000; i++) {
test.add(i, new Integer(generator.nextInt(100000)));
}
List sorted = new ArrayList(test);
long millis = System.currentTimeMillis();
sort(sorted);
millis = System.currentTimeMillis() – millis;
for (int i = 0; i < 10000; i++) {
System.out.println(test.get(i) + “\t\t” + sorted.get(i));
}
System.out.println(“Sorting time (ms): ” + millis);

}

public static void sort (List a) {
if(a.size() < 2) return;
for(int i = 1; i < a.size(); i++) {
Comparable b = (Comparable)a.remove(i);
int mid = -1;
int low = 0;
int high = i – 1;
while (low <= high) {
mid = (low + high) / 2;
Comparable midVal = (Comparable)a.get(mid);
int cmp = midVal.compareTo(b);

if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid – 1;
else {
low = mid;
break;
}
}
a.add(low, b);
}
return;
}
}

4 Responses to Домашка по алгоритмам (#2)

  1. fieral says:

    Ха! Моя домашка по алгоритмам выглядела так:
    “Разбить язык a*bb(ab)*abbb на классы эквивалентности, построить конечный недетерменированный автомат, преобразовать в детерменированный автомат.”

    Вроде так было🙂

  2. А вы где учитесь, товарищь?!

  3. fieral says:

    Механико-математический факультет

  4. Я тебе не завидую🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: