- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
public class Sorting {
private static void swapElements(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
public static void mergeSort(int[] arr) {
if (arr.length == 1) {
return;
}
final int temp = (arr.length % 2 == 0) ? arr.length / 2 : (arr.length + 1) / 2;
int[] left = new int[temp];
int[] right = new int[arr.length / 2];
System.arraycopy(arr, 0, left, 0, temp);
System.arraycopy(arr, temp, right, 0, arr.length / 2);
Sorting.mergeSort(left);
Sorting.mergeSort(right);
Sorting.mergeSortHelper(arr, left, right);
}
private static void mergeSortHelper(int[] arr, int[] left, int[] right) {
int L = 0, R = 0;
boolean Ltop = false, Rtop = false;
for (int i = 0; i < arr.length; i++) {
if (L < left.length - 1 && R < right.length - 1) {
if (left[L] <= right[R]) {
arr[i] = left[L];
L++;
} else {
arr[i] = right[R];
R++;
}
} else if ((L == left.length - 1) ^ (R == right.length - 1)) {
if (L == left.length - 1) {
if ((left[L] <= right[R]) && !Ltop) {
arr[i] = left[L];
Ltop = true;
} else {
arr[i] = right[R];
R++;
}
} else {
if ((right[R] <= left[L]) && !Rtop) {
arr[i] = right[R];
Rtop = true;
} else {
arr[i] = left[L];
L++;
}
}
} else {
if (i < arr.length - 1) {
arr[i] = (left[L] < right[R]) ? left[L] : right[R];
} else {
arr[i] = (left[L] > right[R]) ? left[L] : right[R];
}
}
}
}
1. Зачем?
2. Почему так много?
3. Где дженерики? -> Где здесь java?
2. Я б-кодер =(
3. До дженериков еще не дошел.
И весь mergeSortHelper сомнителен, особенно название, else if и bool'и в нем.
Ни ifов ни циклов тебе.
отсутствие структур данных высокого порядка портит ИМО функциональные языки. уперлись ж религиозно в односвязные списки...
когда видишь обычную FIFO у которой ассимптотическая производительность O(n) (best case O(1), но в случае FIFO это просто не случается, cue in zippers) то как подталкивает на размышления.
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.2
нету в функциональных языках O(1) оператора для добавления элемента в конец списка.
единственное что придумали это зипперы - http://en.wikipedia.org/wiki/Zipper_%28data_structure%29 - но они предоставляют только амортизированую O(1).
кто вам такое сказал? можно ссылку на источник? конструирование происходит только с помощью cons (и это операция O(1)), car и cdr - просто селекторы. Они нужны для обхода списка и никоим образом его не модифицируют (разве что только могут появиться объекты, пригодные для сборки мусора). Там же написано: "the queue operations to be implemented so that they require O(1) steps".
лисп из всех этих языков наверное самый мощный, бо не пытается красивым теориям следовать, а остается просто практичным.
эрланг так же своей практичностью привлекателен (тем более что я работаю в телекомах) но вот той функциональной фигней, и тем что надо рано начинать думать о производительности (и не только о проце - но так же и о памяти) напрягает.
на хаскель после прочтения пару туториалов я забил, бо очень много теории и сказок о красоте программирования на хаскеле. субстанции очень мало.
а ведь все началась с простого поиска выразительного язычка для быстрого прототипирования...
python?
Если бы Erlang был не функциональным, его модель акторов была бы в глубокой... яме.
Так-то я пишу на Java. Haskell изучаю ради новых идей... И чтобы свободнее себя чувствовать в Scala. Мне он кажется довольно практичным, но на освоение требуется уйма времени и практики. Хотя Lisp тоже доставляет. Жаль, времени мало на всё.
отсутствие варнингов + слабая типизация + общая тормознутость не самая лучшая комбинация, к сожалению.
перл иногда тормозит похлеще, но варнинги (что я может чего не то написал что я думал что я написал) кидает сразу. количество встроеных прямо в язык функций тоже как бы развращает: можно по тупому сложные (но вторичные) проблемы делать.
с перлом моя проблема только в том что иногда напишешь прототип, вроде коротко и работает нормально. а когда начинаешь это в С/С++ конвертить... страницы и страницы кода. эстимэйшены времени разработки на основе перловых прототипов делать в принципе невозможно.
какую, если не секрет?
А так вообще можно? В смысле, одинаковое имя аргументов.
Синтерпретировано в Swi-Prolog
неоптимально, ну да и хер с ним. писал только что бы узнать сколько приблизительно строк (по сравнение с С вариантом) на Перле будет.
другими словами: везде где важна ассимптотическая (не абсолютная!) производительность, все равно надо мерж сорт писать.
на ГК не пройдет.