Методы сортировки смешанных данных (текст + числа)

#база_данных #сортировка #алгоритм

                    
Какие есть способы сортировки данных типа:

Профессиональное училище № 21
Профессиональное училище № 30
Профессиональное училище № 120

или:

pgAdmin v1.8.4
pgAdmin v1.10.5
pgAdmin v1.12.3

Есть ли возможность сделать это на уровне БД?
Вопрос касается не только приведенных примеров, но вообще любых возможных вкраплений
в текстовые поля чисел.    

Ответы

Ответ 1

имхо у вас проблема не с сортировкой данных а с проэктированием СУБД. значения то
неатомарные, - посему должна иметь место оптимизация и разбиение данных на 2 поля:
имя + номер или продукт + версия
если вы не слышали ничего про реляционные СУБД (втч. про нормальные формы) есть и
для вас пару вариантов:

для всех полей которые являются комплексными нужно добавить по одному numeric полю
в таблицу. и на вставку/обновление повесить триггер который будет для каждого такого
поля заполнять соответствующие им поля _order. которые и будут использоватся
для сортировки. или же сами можете заполнять при вставке. (имеет смысл хранить эти
данные в отдельной таблице)
можно добавить функцию которая будет подсчитывать order для сортировки на лету. выглядеть
это будет как-то так:

1)    select x.afield from xtable x order by get_order (x.afield)
или
2)    select x.afield from xtable x order by get_order ('xtable', 'xfield', x.afield)

настройки для функции get_order могут хранится в какой-то отдельной таблице. в первом
примере вам придется автоматически определять шаблон который использовать для определения
порядка следования записи, в другом примере вы сможете с помощью if elseif... использовать
алгоритм в зависимости от входных данных.
первый вариант более предпочтительный с точки зрения performance. а правильный, -
оптимизация структуры СУБД
UPDATE:
с одной стороны полное имя учебного заведения это вроде как-бы единое значение. но
это только на первый взгляд. 

"профессиональное" (опциональный префикс, - можно игнорировать)
"училище" - тип учебного заведения (академия, институт, университет) может быть использовано
для сортировки
"№ 43" - номер учебного заведения.
"Санкт Петербурга" - явно же город.
"имени" васи пупкина - даж незнаю как атрибут назвать но "имени" явно можно использовать
для фильтра, - только есть ли смысл, - хз.

далее логически анализируем данные:
номер учебного заведения + его тип = уникальная комбинация (в пределах одного города) 
учебное заведение может быть расположено только в одном городе, во всех остальных
будут филиалы. хотя называтся могут одинаково. т.е комбинация этих 3х полей не будет
уникальной. 
в результате получается таблица следующего содержимого:
id // уникальный id
type, // профессиональное училище / университет / академия. можно вынести в отдельную
таблицу 
number, // порядковый номер. его в принцыпе может и не быть. (это надо учесть в сортировке)
dedication_id // поле которое будет хранить ссылку на id человека которому посвящено.
если null - то никому не посвящено. null тоже можно учесть при сортировке
foundation_date // время когда было создано учебное заведение. имхо это важное поле.
description // или full_name/display_name - полное имя заведения, то которое вы будете
отображать пользователю. и которое никогда не будет участвовать в сортировке.
location_id // ссылка на таблицу с местоположениями (ессно будет содержать город)

p.s. пожалуй еще лучше было бы создать отдельную таблицу отделения или филиалы. привязанную
к конкретному учебному заведению. где каждый отдельный филиал имеет свой конкретный
адресс. что позволит хранить данные независимые от других филиалов. напр: количество
студентов/наличие кафедр/специальностей итд итп
таблица dedication
id, // уникальное id
prefix, //  его величество
name, // василий пупкин

^^ таблица нужна, т.к. одному ученому может быть посвящено больше чем 1 заведение. 
p.s.s если обобщить одной фразой работу с субд: легко проэктировать = сложно работать
и наоборот.

Java автодополнение в консоли используя статистику списка слов

#java #сортировка #поиск #консоль

                    
Цель - создание консольного Линукс/Win приложения с автодополнением текста используя
файл статистики слов. 

Пример файла статистики:

бумага 223
утро 114
утюг 513
уран 22
тепло 144


Всего около 100000+ слов

Какой наилучший алгоритм для поиска и как лучше отсортировать считанные с файла слова
с их статистикой?

Я думаю записать слова для каждой первой буквы в отдельный список List типа ключ-значение
(SortedMap-TreeMap?) с сортировкой по значению, и разместить те списки в ArrayList.
Когда пользователь начинает писать слово, список с его соответственный его первой букве
сканируется на подходящие слова и они выдаются с сортировкой по значению. Это хороший
способ? как практически лучше это написать, используя что из коллекций и какой алгоритм?
    

Ответы

Ответ 1

Собственно есть два быстрых пути. Можно реализовать, перенеся твой справочник в таблицу БД

 create table dictonary (word Varchar(30) primary key, cost integer not null)


Тогда поиск будет сводиться к 

 select word from dictonary where word like 'начало_твоего_слова%' order by cost desc


Встроенные базы довольно шустрые (H2, HSQLDB)



Но если тебе надо использовать только java, то используй TreeMap. Только для начала
оговоримся, что все твои слова должны содержать только русские буквы (привет кэп),
и желательно только нижнего регистра.  Далее остается использовать метод subMap, но
с одной хитростью. Если ты ищешь слова начинающиеся с бу, то тебе надо передавать параметры
в submap в виде бу\u040f (в конце символ, код которого меньше кода первой буквы алфавита)
и бу\u0450 (в конце символ, код которого больше кода последней буквы алфавита). Хитрость,
но работает. Плюс тебе придётся сортировать результат, согласно статистике повторений
слова.

ValueError: dict contains fields not in fieldnames

#python #сортировка #csv

                    
with open('data.csv', "r") as csv_file:
    csv_reader = csv.DictReader(csv_file)

with open('gaze.csv', 'w') as new_file:
    fieldnames = ['gaze_0_x', 'gaze_0_y', 'gaze_0_z', 'gaze_1_x', 'gaze_1_y', 'gaze_2_z']

    csv_writer = csv.DictWriter(new_file, fieldnames=fieldnames, delimiter='\t')

    csv_writer.writeheader()

    for line in csv_reader:
        csv_writer.writerow(line)


ValueError: dict contains fields not in fieldnames: ' x_59', ' X_18', ' x_27', '
y_42', ' Y_16', ' pose_Rz', ' Y_32', ' Y_54', ' x_26', ' x_16', ' p_5', ' X_67', '
p_14', ' x_17', ' Z_2', '...И так далее 400 переменных, которые я не хочу задействовать. 
    

Ответы

Ответ 1

Так передайте fieldnames в DictReader, чтобы он лишних полей не читал.

Вернуть сортировку в исходное состояние js / сортировка DOM элементов по алфавиту

#javascript #сортировка #dom

Доброго времени суток!

Можно ли вернуть сортировку в исходное состояние при нажатии кнопки?
https://codepen.io/anon/pen/RerZXE

UPD: ниже @REGISTOOOOOO добавил сортировку по алфавиту DOM элементов. Так же я добавил
в название темы "сортировка DOM элементов по алфавиту", поскольку в интернетах информацию
не нашёл, хоть изначальный вопрос был другой. 
Спасибо всем за помощь!



function sort() {
  var nodeList = document.querySelectorAll('li');
  var itemsArray = [];
  var parent = nodeList[0].parentNode;
  for (var i = 0; i < nodeList.length; i++) {    
    itemsArray.push(parent.removeChild(nodeList[i]));
  }
  itemsArray.sort(function(nodeA, nodeB) {
      var textA = nodeA.querySelector('div:nth-child(2)').textContent;
      var textB = nodeB.querySelector('div:nth-child(2)').textContent;
      var numberA = parseInt(textA);
      var numberB = parseInt(textB);
      if (numberA < numberB) return -1;
      if (numberA > numberB) return 1;
      return 0;
    })
    .forEach(function(node) {
      parent.appendChild(node)
    });
}
body {  
  font-family: 'Trebuchet MS', sans-serif;
  color: #444;
  font-size: 14px;
}
ul {
  margin: 15px;
  padding: 5px 15px;
  border: 1px solid #eee;
  background: #fff;
  border-radius: 3px;
  list-style: none;
}
li {
  padding: 10px; 
}
li:not(:last-child) {
   border-bottom: 1px dotted #ddd;
}
button {
  margin: 10px 15px;
  border: 1px solid #eee;
  border-radius: 3px;
  background: #fff;
  padding: 8px;
  min-width: 100px;
  cursor: pointer;
  font-family: inherit;
  font-size: inherit;
  color: #444;
}
button:hover {
  background-color: #fbfbfb;
}


  
	
	
	
	
	
	
  
 
	  

    
Текст
5
Текст
    
Текст
15
Текст
    
Текст
2
Текст
    
Текст
20
Текст
    
Текст
1
Текст
  
  
  
 




    

Ответы

Ответ 1

function sort(aRestore) { // !!! - параметр
  var nodeList = document.querySelectorAll('li');
  var itemsArray = [];
  var parent = nodeList[0].parentNode;
  
  for (var i = 0; i < nodeList.length; i++) {
    // !!! - здесь
    if (!nodeList[i].dataset.originalorder)
      nodeList[i].dataset.originalorder = i + 1;

    itemsArray.push(parent.removeChild(nodeList[i]));
  }
  
  itemsArray.sort(function(nodeA, nodeB) {
    // !!! - и здесь
    if (aRestore) {
      return nodeA.dataset.originalorder - nodeB.dataset.originalorder;
    }

    var textA = nodeA.querySelector('div:nth-child(2)').textContent;
    var textB = nodeB.querySelector('div:nth-child(2)').textContent;
    var numberA = parseInt(textA);
    var numberB = parseInt(textB);
    if (numberA < numberB) return -1;
    if (numberA > numberB) return 1;
    return 0;
  }).forEach(function(node) {
    parent.appendChild(node)
  });
}
body {
  font-family: 'Trebuchet MS', sans-serif;
  color: #444;
  font-size: 14px;
}

ul {
  margin: 15px;
  padding: 5px 15px;
  border: 1px solid #eee;
  background: #fff;
  border-radius: 3px;
  list-style: none;
}

li {
  padding: 10px;
}

li:not(:last-child) {
  border-bottom: 1px dotted #ddd;
}

button {
  margin: 10px 15px;
  border: 1px solid #eee;
  border-radius: 3px;
  background: #fff;
  padding: 8px;
  min-width: 100px;
  cursor: pointer;
  font-family: inherit;
  font-size: inherit;
  color: #444;
}

button:hover {
  background-color: #fbfbfb;
}

  
Текст
5
Текст
  
Текст
15
Текст
  
Текст
2
Текст
  
Текст
20
Текст
  
Текст
1
Текст





Ответ 2

Тоже сделал сортировку, изучил вариант @igor и некоторое позаимствовал. Добавил сортировку
методом Intl.js с изменением расположения flex элементов.



function sort() {
  // находим нужные элементы
  const nodes = document.querySelectorAll('li');
  // создаем объект Collator библиотеки Intl.js   для поиска
  const collator = new Intl.Collator("ru", {numeric: true, caseFirst: 'upper'});
  // коллбэк для сортировки
  const innerSort = (x, y) => {
    const a = x.querySelector('div:nth-of-type(2)');
    const b = y.querySelector('div:nth-of-type(2)');
    return collator.compare(a.textContent, b.textContent);       
  }
  // делаем массив из nodeList и сортируем согласно коллбэка         
  const arr = [].slice.call(nodes).sort(innerSort);
  // добавляем каждому элементу инлайновый класс 
  // с порядковым номером отображения
  arr.forEach((item, i) => item.style.order = `${i+1}`);
}

function originer() { 
  // удаляем классы для возврата в первоначальное состояние      
  const nodes = document.querySelectorAll('li');
  const deleteOrder = () => nodes.forEach((item) => item.style.order = '')
  deleteOrder()
}
body {  
  font-family: 'Trebuchet MS', sans-serif;
  color: #444;
  font-size: 14px;
}
ul {
  margin: 15px;
  padding: 5px 15px;
  border: 1px solid #eee;
  background: #fff;
  border-radius: 3px;
  list-style: none;
}
li {
  padding: 10px; 
}
li:not(:last-child) {
   border-bottom: 1px dotted #ddd;
}
button {
  margin: 10px 15px;
  border: 1px solid #eee;
  border-radius: 3px;
  background: #fff;
  padding: 8px;
  min-width: 100px;
  cursor: pointer;
  font-family: inherit;
  font-size: inherit;
  color: #444;
}
button:hover {
  background-color: #fbfbfb;
}
ul{
  display:flex;
}


  
    
    
    
    
    
    
  
 
 

    
Текст
5
Текст
    
Текст
АА
Текст
    
Текст
55
Текст
    
Текст
20
Текст
    
Текст
фыв
Текст
    
Текст
аа
Текст
    
Текст
15
Текст
  
  
  
 

Пирамидальная сортировка на C++

#алгоритм #сортировка #cpp

Приведите пример пирамидальной сортировки (сортировки кучи) на C++.    

Ответы

Ответ 1

Сортировка "кучи" на C++.
#include 

template 
inline void swap( T & arg1, T & arg2)
{
    T temp = arg1;
    arg1 = arg2;
    arg2 = temp;
};
template 
void shiftup(T * a, int size, int indexToShift) {
    int i = indexToShift;
    while(i > 1) {
        if(a[i] < a[i/2]) {
            swap(a[i], a[i/2]);
            i /= 2;
        } else
            break;
    }
}

template 
void shiftdown(T * a, int size, int indexToShift) {
    int i = indexToShift;
    int min;
    while ( i < size) {
        if ( i*2 <= size) {
            if (i*2+1 <= size) {
                min = a[i*2] < a[i*2+1] ? i*2 : i*2+1;
            } else 
                min = i*2;
            if (a[i] > a[min]) {
                swap(a[i], a[min]);
                i = min;
            } else
                break;
        } else 
            break;
    }
}

template  
void heap_sort( T * a, int size) {
    for (int i = 1; i < size; ++i) 
        shiftup(a, size, i);
    for (int i = size-1; i > 1; i--) {
        swap(a[1], a[i]);
        shiftdown(a, i-1, 1);
    }
}


Ответ 2

В С++ уже есть функции для работы с кучей - std::make_heap и std::sort_heap, по этому
сортировка кучей реализуется тривиально:

template>
void heap_sort(RandomAccessIter first, RandomAccessIter last, Compare cmp = Compare{}) {
    std::make_heap(first, last, cmp);
    std::sort_heap(first, last, cmp);
}

Отсортировать массив объектов по значеням второго массива

#сортировка #javascript

Нужно отсортировать массив sel по массиву resources или можно создать другой массив,
вида sel, только отсортированный по resources.
Есть 2 массива:
Первый массив:
var resources = [
    ["1717", "1859", "3000"],
    ["1616", "1600"]
];

Второй массив, который нужно отсортировать или создать подобный, но отсортированный
по первому:
var sel = [
    [
        {"id":"3000","title":"3G"},
        {"id":"1859","title":"4G"},
        {"id":"1717","title":"Customer"}
    ],
    [
        {"id":"1600","title":"Should"},
        {"id":"1616","title":"Ranking"}

    ]
];

Первый элемент массива sel
[
        {"id":"3000","title":"3G"},
        {"id":"1859","title":"4G"},
        {"id":"1717","title":"Customer"}
]

должен иметь порядок, как в массиве resources
["1717", "1859", "3000"]
Заранее спасибо.    

Ответы

Ответ 1

var sorted_sel = [];
resources.forEach(function(line, i){
    sorted_sel[i] = [];
    line.forEach(function(resources_el){
        sel[i].forEach(function(sel_el){
            if(sel_el.id === resources_el) sorted_sel[i].push(sel_el);
        });
    });
});

Killer-sequence для Quick Sort

#cpp #алгоритм #сортировка

Имеется код для Quick-Sort, представленный ниже. Здесь пивотом будет являться серединный
элемент. А как построить пример, при котором данная сортировка будет работать за O(n^2)?
Нашёл лишь статью http://www.cs.dartmouth.edu/~doug/mdmspe.pdf, но не разобрался, так
как плохо владею английским. Можно ли ещё прикрепить пример кода, который будет генерировать
killer-sequence за O(n)?

void qsort(int *a,int l,int r)
   {
   if(l>=r)
   return;
    int x = a[(l+r)/2];
    int i = l,j = r;
    while(i<=j){
            while(a[i] < x) ++i;
        while(a[j] > x) --j;
        if(i<=j){
            swap(a[i],a[j]);
            ++i,--j;
        }
    }
    qsort(a,l,j);
    qsort(a,i,r);
}

    

Ответы

Ответ 1

Эх, тряхнём стариной :) Давайте-ка протрассируем индексы назад. Получается вот что:

void prepare_killer(int* a, int length)
{
    int origidx[length];
    for (int i = 0; i < length; i++)
        origidx[i] = i;

    // эмулируем прохождение qsort по плохому пути
    // r будет всё время константой
    int r = length - 1;

    // а l будет каждый раз увеличиваться на 1
    for (int l = 0; l < r; l++)
    {
        // так будет выбран pivot:
        int p = (l + r) / 2;

        // элементы с индексами l и p поменяются местами
        swap(origidx[l], origidx[p]);
    }

    // имея позиции, куда придут данные, можно теперь их расставить:
    for (int i = 0; i < length; i++)
        a[origidx[i]] = i + 1;
}


Для проверки напишем модифицированную версию qsort, которая будет проверять, что
данные отправляют её всё время по «плохому» пути: одно из двух подзаданий будет всегда
пустым.

bool qsort_check_failed = false;

void qsort_with_check(int *a, int l, int r)
{
    if (l >= r)
        return;
    int x = a[(l + r) / 2];
    int i = l, j = r;
    while (i <= j)
    {
        while (a[i] < x) ++i;
        while (a[j] > x) --j;
        if (i <= j)
        {
            swap(a[i], a[j]);
            ++i, --j;
        }
    }

    if (!(l >= j))
    {
        cout << "Mistake: have non-empty first subtask!" << endl;
        qsort_check_failed = true;
    }
    qsort_with_check(a, l, j);
    qsort_with_check(a, i, r);
}


Проверка здесь: http://ideone.com/a9L22p


Ответ 2

Самое простое решение твоей задачи, это уже отсортированный массив. В этом случае
у тебя quick sort будет давать худший результат.

int * array = new int[7];
for(int size = 0; size < 7; size++)
{
   (*array)[size] = size;
}


Это как вариант заполнения

Сортировать записи из таблицы mysql в определённом порядке

#mysql #база_данных #алгоритм #сортировка

Имеется таблица mysql с записями, которые через php выводятся на страницу в определённом
порядке, например: 128, 59, 70, 293, 19 и т.д. Каждая новая запись должна занимать
определённое место в данном порядке (порядок записей определяю сам в зависимости от
контента). Например, новая запись 476 должна быть вставлена между 59 и 70, т.е. образуется
такой массив.

Сейчас я делаю это так: каждой записи даю некоторое число и в запросе указываю сортировку
по этим числам. Но я думаю такой алгоритм не очень эффективен, тем более, что данные
числа я прописываю вручную.

Есть идеи как можно сделать это по нормальному, не нагружая сильно сервер?
    

Ответы

Ответ 1

На самом деле отдельное поле с идентификаторами задающими порядок - не такая плохая
идея. Поле числовое, поэтому сортировка по нему осуществляется очень быстро, оно может
быть проиндексировано, поэтому запрос может быть еще более ускорен и практически не
зависеть по скорости от объема таблицы.

Заполнять это поле не обязательно вручную, можно прикрутить интерфейс, позволяющий
перетаскивать позиции пользователю и пересчитывать это поле автоматически.

Альтернатив не так много и они уже не так эффективны. Например, MySQL-функция FIELD(),
которая возвращает позицию вхождения первого аргумента в список, который задается оставшимися
аргументами.

В качестве первого параметра передается поле id, а в качестве остальных аргументов
используется список 128, 59, 70, 293, 19. Так как все не входящие в список значения
будут получать значение 0, его лучше заменить на 65536

SELECT
  *
FROM
  tbl
ORDER BY
  IF(FIELD(id, 128, 59, 70, 293, 19) = 0, 65536, FIELD(id, 128, 59, 70, 293, 19))


или в качестве альтернативы можно обратить список и использовать ключевое слово DESC,
тогда значения 0, возвращаемые функций FIELD() выстроятся в конец и их можно будет
отсортировать по какому-то другому полю

SELECT
  *
FROM
  tbl
ORDER BY
  FIELD(id, 19, 293, 70, 59, 128) DESC, name;


Однако этот подход хуже, чем дополнительное поле, так как вычисления позиции осуществляются
при выборки каждой строки, такое динамическое поле невозможно проиндексировать (по
крайней мере в MySQL).

Лучше оставить отдельное поле для сортировки, однако рассмотреть возможность его
автоматического заполнения. Например, по умолчанию присваивать ему максимальное значение
+ 1, т.е. размещать в конце, а при перетаскивании элемента, вычислять смещение и изменять
(UPDATE) это поле у всех строк в интервале смещения.

Как распределить числа из массива js

#javascript #массивы #сортировка

Задача такая:

var streak = {
  min: '',
  max: '',
  length: '',
  series: []
}

var allStreaks = []


У меня есть массив чисел:

var arr = [19, 20, 21, 22, 17, 18, 19, 7, 8, 9]


Мне нужно распределить их по массивам чтобы в нем были эти числа в порядке возрастания,
и записать все это в таком формате:

[{
  min: 19,
  max: 22,
  length: 4,
  series: [19, 20, 21, 22]
}, {
  min: 17,
  max: 19,
  length: 3,
  series: [17, 18, 19]
}, {
  min: 7,
  max: 9,
  length: 3,
  series: [7, 8, 9]
}]


В исходном массиве числа идут в том порядке в котором они мне нужны будут (как будто
если бы эти числа шли по датам - одно число - один день) Мне нужно отловить сколько
"дней" эти числа увеличивались, с какого числа началось и на каком остановилось и потом
все сначала. Первые 4 числа массива arr (19 20 21 22) должны создать объект в котором
будет записано минимальное число (19), максимальное число (22), сколько всего чисел
было записано (4) и собственно сам массив этих чисел [19, 20, 21, 22]. Точно так же
со вторым возрастающим стриком с 17 до 19 итд
        Числа в исходном массиве абсолютно рандомные и нужно отследить эту череду
увеличений и как только встречается число меньше предыдущего начать новый массив

На данный момент делаю так:

for (var i = 0; i < arr.length-1; i++) {
  if (arr[i] < arr[i+1]) {
    streak.series.push(arr[i])
  } else {
    streak.series.push(arr[i]) //Сохранит последний элемент первого стрика
    break;
  } 
}


Так я успешно получаю первый стрик, однако если мне надо продолжить, то возникают
трудности: 

for (var i = 0; i < arr.length-1; i++) {
  if (arr[i] < arr[i+1]) {
    streak.series.push(arr[i])
  } else if ((arr[i] > arr[i-1]) && (arr[i] > arr[i+1])) {
    streak.series.push(arr[i]) // Это ловит и записывает последний элемент первого
стрика, получается steak.series = [19,20,21,22]
    // но он на этом не останавливается и продолжает записывать все числа исходного
массива
    // так как они потом подходят под первый if (arr[i] < arr[i+1])
    // и в результате у меня просто переписывается весь исходный массив
  } else {continue;} 
}

    

Ответы

Ответ 1

var arr = [19, 20, 21, 22, 17, 18, 19, 7, 8, 9]
    var resArr = [];
    var min = max = length = 0;
    var tempArr = [];
    var prev = 0;
    
    arr.forEach(function(item) {
      if(prev > item && prev){
         resArr.push({'min':min,'max':max,'length':length, 'series':tempArr});
         min = 0;
         max = 0;
         tempArr = [];
         length = 0;
      }
      if(item > max) max = item;
      if(item < min || min == 0) min = item;
      length++;
      tempArr.push(item);
      prev = item;
    });
    resArr.push({'min':min,'max':max,'length':length, 'series':tempArr});
    console.log(resArr);


Ответ 2

var allStreaks = [];
var arr = [19, 20, 21, 22, 17, 18, 19, 7, 8, 9];
var prevMaxPos = 0;

doWork();
console.log(allStreaks);

// функции работы и заноса в итоговый массив
function doWork() {
  for (var i = 1; i < arr.length; ++i) {
    if (arr[i] < arr[i - 1]) {
      allStreaks.push(setStreak(arr.slice(prevMaxPos, i)));
      prevMaxPos = i;
    }
  }

  if (arr.slice(prevMaxPos).length > 0)
    allStreaks.push(setStreak(arr.slice(prevMaxPos)));
}

function setStreak(arr) {
  return streak = {
    min: arr[0],
    max: arr[arr.length - 1],
    length: arr.length,
    series: arr
  }
}


Ответ 3

решение в стиле минимализм ...



var arr = [19, 20, 21, 22, 17, 18, 19, 7, 8, 9];

function go(d) {
  var a;
  return d.reduce(function(c, b) {
    a && b == a.max + 1 ? (a.max = b, a.length++, a.series.push(b)) :
      (a = {
        min: b,
        max: b,
        length: 1,
        series: [b]
      }, c.push(a));
    return c
  }, [])
};
console.log(go(arr))


Ответ 4

ещё одно минималистическое, но читаемое решение



var arr = [19, 20, 21, 22, 17, 18, 19, 7, 8, 9],        
    distribute = function(arr) {
      var out = [], series = [], i = 1;
      while (i < arr.length + 1) {
        series.push( arr[i-1] );
        if (! (arr[i-1] < arr[i++])) {
            out.push({
             min:     series[0],
             max:     series[series.length-1],
             length:  series.length,
             series:  series.slice()
           });
           series = [];
         }
      }
      return out;
    }


console.log( distribute(arr) );

Как ускорить процесс сортирования дат

#php #сортировка #оптимизация #дата

функция pc_date_sort(), приведен
ная в примере  показывает, как сортировать даты.

function pc_date_sort($a, $b) {
    list($a_month, $a_day, $a_year) = explode('/', $a);
    list($b_month, $b_day, $b_year) = explode('/', $b);
    if ($a_year > $b_year ) return 1;
    if ($a_year < $b_year ) return -1;
    if ($a_month > $b_month) return 1;
    if ($a_month < $b_month) return -1;
    if ($a_day > $b_day ) return 1;
    if ($a_day < $b_day ) return -1;
    return 0;
}
$dates = array('12/14/2000', '08/07/1999', '08/10/2001');
usort($dates, 'pc_date_sort');
echo '
';
print_r($dates);


Во время сортировки функция usort() часто – каждый раз, когда ей
надо сравнить два элемента – выполняет пересчет значений, возвра
щаемых функцией сортировки, что замедляет процесс.

Помогите пожалуйста оптимизировать код
Как избежать ненужной работы? 
    

Ответы
Ответ 1

использовать стандартный встроенный класс. Это раньше приходилось свои велосипеды
городить с датами. 


встроенный datetime написан на C, он будет быстрее, 
он оттестирован и будет безопасней
он предлагает больше возможностей чем свой велосипед


дополнить его вы можете обернув в свой класс/функцию, унаследовав (не проверял)

createFromFormat() создаст объекты из вашего формата дат без всяких дополнительных
ухищрений и ручных explode-ов строчек


Ответ 2

Я добавлю свой вариант, но скорей всего буду рассматривать ваши предложния.Несмотря
что протестировал вроде быстрее ,и памяти жрет меньше.

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

function pc_array_sort($array, $map_func, $sort_func = '') {
    $mapped = array_map($map_func, $array); // cache $map_func() values
    if ('' == $sort_func) {
        asort($mapped); // функция asort() быстрее функции usort()
    } else {
     uasort($mapped, $sort_func); // необходимо сохранить ключи
    }
    while (list($key) = each($mapped)) {
        $sorted[] = $array[$key]; // используем отсортированные ключи
    }
    return $sorted;
}


Чтобы избежать ненужной работы, функция pc_array_sort() использу
ет временный массив $mapped для кэширования возвращаемых значе
ний. Затем она сортирует массив $mapped, используя или порядок сор
тировки по умолчанию, или определенную пользователем процедуру
сортировки. Важно, что она использует сортировку, сохраняющую
связи ключ/значение. По умолчанию она использует функцию
asort(), потому что она быстрее, чем функция uasort(). (Медленность
функции uasort() это всетаки значительный довод в пользу функции
pc_array_sort().) Наконец, она создает отсортированный массив $sort 
ed, при этом отсортированные ключи в массиве $mapped выступают в ка
честве индексов значений исходного массива.
Для небольших массивов или коротких функций сортировки функция
usort() работает быстрее, но как только число сравнений вырастает,
функция pc_array_sort() обгоняет функцию usort().

Ну или сравнивать в пeрвом примере как и посоветовали следующим образом

$date1 = DateTime::createFromFormat('!Y/m/d', '2012/10/17');
$date2 = DateTime::createFromFormat('!Y/m/d', '2012/10/17');
var_dump($date1 == $date2); //will be true
var_dump($date1 > $date2); //will be false
var_dump($date1 < $date2); //will be false

Нисходящая сортировка слиянием. Метод абстрактного обменного слияния

#cpp #алгоритм #сортировка

Нужно реализовать нисходящую сортировку слиянием методом абстрактного обменного слияния.
Вот функция абстрактного обменного слияния:

template 
void merge(Item a[], int l, int m, int r) {
    int i, j;
    static Item aux[maxN];
    for (i = m + 1; i > l; i--)
        aux[i - 1] = a[i - 1];
    for (j = m; j < r; j++)
        aux[r + m - j] = a[j + 1];
    for (int k = l; k <= r; k++)
        if (aux[j] < aux[i])
            a[k] = aux[j--];
        else
            a[k] = aux[i++];
}


Как сделать эту сортировку нисходящей, то есть рекурсивной?
    

Ответы

Ответ 1

Я немного изменил вашу функцию. Среднее значение вычисляется внутри. Принцип работы
алгоритма таков, что сначала исходный массив разбивается на два других. Каждый из них
также разобьется ещё на два. Это будет продолжаться до тех пор, пока длина каждого
подмассива будет равна 1.

template 
void merge(Item a[], int l, int r) {

    if (abs(r - l) <= 1) return; //конец рекурсивных вызовов
    int i, j;
    int m = (l + r) / 2;
    merge(a, l, m); //вызов для левой части
    merge(a, m+1, r); //вызов для правой части
    static Item aux[1000];
    for (i = m + 1; i > l; i--)
        aux[i - 1] = a[i - 1];
    for (j = m; j < r; j++)
        aux[r + m - j] = a[j + 1];
    for (int k = l; k <= r; k++)
    {
        if (aux[j] < aux[i])
            a[k] = aux[j--];
        else
            a[k] = aux[i++];
    }   
}


Замечание: при вызове функции необходимо указывать длину массива - 1. То есть:

int main()
{
    int a[N];
    merge(a, 0, N-1);
}

Отсортировать список предложений по количеству букв и слов в python 2.7

#python #сортировка #python_27

Начинаю учить Python 2.7. Надо отсортировать список предложений по количеству букв
и слов. song - собственно сам файл со списком.

Чтобы отсортировать, подозреваю, надо играться с key, но не хватает у меня пока мыслей,
как именно.

song = sys.argv[1]
w = open(song)
for line in sorted(w, key = int(len(line)))   
    print line

    

Ответы

Ответ 1

Параметр key должен быть функцией, принимающей текущий элемент и возвращающей значение,
по которому сортируем. В данном случае достаточно просто len (приведение длины к целому
излишне, т.к. len и так возвращает целое число):

song = sys.argv[1]
w = open(song)
for line in sorted(w, key=len)   
    print line


В более сложных случаях сортировки может понадобиться создать lambda-функцию (или
даже выносить код в отдельную именованную функцию).

Для сортировки по количеству слов можно разбивать строку по пробельным символам с
помощью метода строки split, и сортировать по количеству полученных кусков:

song = sys.argv[1]
w = open(song)
for line in sorted(w, key=lambda x: len(x.split()))
    print line


Чтобы отсортировать строки по количеству слов, а слова в строках по количеству букв,
можно сделать так:

Сначала просто создаем список строк, каждую строку разбиваем на слова:

lines = [line.rstrip().split() for line in file]


Добавляем сортировку слов внутри строк (это та же строка, просто добавили сортировку):

lines = [sorted(line.rstrip().split(), key=len) for line in file]


Добавляем сортировку строк по количеству слов (заменяю генератор списка на итератор
- круглые скобки вместо квадратных):

lines = sorted((sorted(line.rstrip().split(), key=len) for line in file), key=len)


Т.к. строки уже разбиты на слова, то еще раз делать split не нужно, а просто сортируем
по длине списка.

Ну и при выводе на экран собираем списки слов обратно в целые строки:

for line in lines:
    print ' '.join(line)


Дополнение. Как правильно заметил jfs в комментариях к ответу, если файл сохранен
например в utf-8 (вообще в любой не однобайтовой кодировке), то будет не подсчет символов,
а подсчет байт, плюс не будет работать разбивка по юникодным пробельным символам.

Чтобы открыть файл в нужной кодировке, нужно использовать функцию io.open(). При
открытии будет использоваться кодировка системы по-умолчанию. Чтобы использовать конкретную
кодировку, можно указать ее при открытии:

import io
...
w = io.open(song, encoding='utf-8')


Ответ 2

Чтобы отсортировать список предложений sentences по количеству слов:

sentences.sort(key=word_count)


где функция word_count() принимает предложение и возвращает количество слов в нём.

Если вы ещё хотите, чтобы слова внутри отдельных предложений были отсортированы по
количеству букв, то следует разбить каждое предложение на слова и отсортировать слова:

words = get_words(sentence)
words.sort(key=char_count)


Здесь get_words() функция принимает предложение и возвращает список слов в нём. char_count()
функция принимает слово и возвращает количество букв в нём. 

Как конкретно выглядят функции word_count, get_word, char_count зависит существенно
от задачи.

К примеру, если входной файл, заданный в командной строке, содержит предложения каждое
на новой строке, а слова просто отделены пробелом, тогда чтобы отсортировать предложения
по количеству слов в них, а слова внутри предложений по количеству букв:

#!/usr/bin/env python
import io
import sys

with io.open(sys.argv[1]) as file:
    sentences = file.read().splitlines()  # NOTE: line ends are not included
    result = sorted([sorted(get_words(s), key=char_count)
                     for s in sentences], key=word_count)

for words in result: # for each sentence
    print(' '.join(words))


где:

get_words = unicode.split  # split on arbitrary whitespace
word_count = len           # number of items in the list of words
char_count = len           # unicode word length


Замечания по коду:


io.open() используется, чтобы текст как unicode прочитать, а не байты (используя
locale.getpreferredencoding() кодировку). Количество байт в слове может не совпадать
с количеством символов в нём. См. Длина строки считается неверно
unicode.splitlines() возвращает список строк, убирая концы строк 
unicode.split() разбивает строку по произвольному пробелу (не только u' ', но к примеру
и неразрывный пробел U+00A0 понимает). В качестве альтернативы, можно было бы регулярное
выражение использовать, чтобы список слов получить:

import re

words = re.findall(r'\w+', sentence, flags=re.UNICODE)


это полезно, если вы не хотите к примеру, пунктуацию рассматривать частью слов (если
просто по пробелам разбить, то точки, запятые в словах остаются)
word_count = len работает, так как каждое предложение как список слов представлено в коде
unicode объект в Питоне является неизменяемой последовательностью символов (Unicode
codepoints), поэтому char_count = len. То есть количество букв считается равным количеству
символов в слове. Стоит заметить, что одно видимая буква, может из нескольких символов
состоять:

>>> len(u"ё")
2
>>> u"ё"
u'\u0435\u0308'


Для целей перемещения по тексту, для копирования в GUI мы бы не хотели только половину
буквы получить. См. Разделить в Python 3 слово на символы

Дополнительно, существуют так называемые "узкие" сборки python 2 исполняемого файла,
в которых не-BMP символы такие как U+1F602 (FACE WITH TEARS OF JOY) в виде суррогатной
пары представлены (абстракция нарушена — дефект в реализации). В "широких" сборках
(часто на Linux) или на Питоне 3 этой проблемы не существует: индексация (Unicode)
строк не разбивает символ (Unicode codepoint):

>>> print(u'\U0001f602')
😂
>>> len(_)
1

Как сортировать массив структур по одному из параметров структуры?

#cpp #visual_cpp #сортировка #структуры

struct Student
{
    char last_name[m];
    char name[m];
    char surname[m];
    int proga[n];
    int sda[n];
    int mat_analiz[n];
    int lin_algebra[n];
    int sum_ball;
}student[k];


Подскажите как отсортировать данную структуру по переменой sum_ball, и если совпадает
то по last_name 
Как ни пробовал, ничего не получается, просто выдает какую-то ахинею.
Раньше с таким не приходилось работать.

Student temp;   

for (int i = 0; i < k; i++)
{
    for (int j = i; j < k; j++)
    {
        if (student[j].sum_ball < student[i].sum_ball)
        {
            temp.last_name = student[i].last_name;
            student[i].last_name = student[j].last_name;
            student[j].last_name = temp;
            //и так дали с другими 

        }
    }
}


Ну например вот так, с массивами так можно а с структурами как? Это ж не правильно
я понимаю
    

Ответы

Ответ 1

Требуемый компаратор может выглядеть, например, так:

[](const Student&a, const Student&b)
{
    if (a.sum_ball < b.sum_ball) return true;
    if (a.sum_ball == b.sum_ball) 
        return strcmp(a.last_name,b.last_name) < 0;
    return false;
}


Вроде бы так...

Есть какая-нибудь замена sort в ArrayList?

#java #android #сортировка #arraylist

Нужно отсортировать ArrayList, но Android Studio пишет 


  "Call requires API level 24 (current min is 21): java.util.ArrayList#sort"


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

Ответы

Ответ 1

Collections.sort(list); — сортирует коллекцию, используя компаратор
Collections.shuffle(list); — перемешивает коллекцию в случайном порядке

Сортировка потока в обратном направлении

#java #сортировка #lambda #java_stream

На вход подается текстовая строка. Нужно вернуть слово с наибольшей сумой значений
кодов символов. Сортировку нужно выполнить в обратном направлении. Использую метод
reversed(), но тогда не могу использовать метод chars(), так как w типа Object. Как
правильно осуществить сортировку в обратном порядке?  

public static String high(String s) {

        return Stream.of(s.split(" "))
                .sorted(Comparator.comparingInt(w -> w.chars().sum()).reversed())
                .toArray(String[]::new)[0];

}

    

Ответы

Ответ 1

Попробуйте так:  

public static String high(String s) {

        return Stream.of(s.split(" "))
                .sorted(Comparator.comparing(String::chars, Comparator.comparingInt(IntStream::sum)).reversed())
                .toArray(String[]::new)[0];

    }


Данный метод первым аргументом принимает key extractor, т.е. какие данные нам нужно
вытащить для сортировки, а второй аргумент принимает то, КАК мы будем сортировать.
Ну то есть все просто, вытащили IntStream чаров и отсортировали по их сумме

Как высчитывается количество секций (partitions) в массиве

#c_sharp #net #сортировка

Array.Sort() в C# использует алгоритм разумной сортировки (introsort) следующим образом:

Если размер раздела меньше 16 элементов, он использует insertion sort алгоритм.

Если количество секций превышает 2 * log(N), где N диапазон входного массива, он
использует Heapsort алгоритм.

В противном случае он использует Quicksort алгоритм.

У меня такой вопрос: как этот алгоритм высчитывает количество секций в массиве? Было
бы глупо предположить, что встроенная сортировка сначала высчитывает на сколько секций
квиксорт разделит этот массив, а потом уже выбирает алгоритм.

Может быть есть какая-то формула?
    

Ответы

Ответ 1

Я думаю, что понятие "количество секций в массиве" здесь появилось вследствие какого-то
недоразумения - возможно, кривой перевод.

Интросорт использует быструю сортировку, которая выполняет разделение массива (partition)
на части по выбранному опорному элементу (pivot). Вот если массив особо гнусный и опоры
выбираются неудачно, то этих самых разделений будет слишком много. Интросорт следит
за этим (глубина), и переключается на сортировку кучей. Для идеального случая глубина
log2(n). Каков критерий глубины для переключения - зависит от конкретной реализации.
Вот пример:


  The GNU Standard C++ library is similar: uses introsort with a maximum
  depth of 2×log2 n


И опять мы видим использование кривого перевода - log это логарифм, а не журнал

Алгоритмы слияния двух неупорядоченных массивов

#алгоритм #сортировка

Недавно начал знакомство с сортировкой слиянием и понял, что я понятия не имею как
происходит слияние неупорядоченных массивов, и какие алгоритмы существуют для этой
цели. Как реализовать сортировку слиянием рекурсивно я прекрасно понимаю, а вот именно
подробное описание алгоритма(ов) слияния подмассивов, я так и не нашел.

Можете подробно рассказать про алгоритм(мы) слияния массивов, либо дать короткое
четкое и понятное объяснение на эту тему, или дать ссылку на источники, где это все
подробно объясняется?
    

Ответы

Ответ 1

Во-первых, в алгоритме сортировки слиянием действительно в качестве под-алгоритма
используется алгоритм слияния двух последовательностей (массивов, списков и т.п.).
Однако слияние выполняется именно для упорядоченных последовательностей. В этом вся
суть алгоритма сортировки слиянием. Поэтому не ясно, почему в своем вопросе вы говорите
о "слиянии неупорядоченных массивов". Откуда взялись неупорядоченные массивы? И какое
это имеет отношение к сортировке слиянием?

Во-вторых, алгоритм слияния двух упорядоченных последовательностей тривиален: просто
на каждом шаге алгоритма выбираем минимальный из начальных элементов наших входных
последовательностей и перемещаем его на выход. Повторяем, пока не исчерпаем входные
последовательности. Все.

В-третьих, если речь идет именно о массивах, то вышеупомянутый тривиальный алгоритм
слияния легко применим только в том случае, если мы имеем возможность на основе двух
входных массивов формировать третий (отдельный) слитый массив. Так обычно и реализуется
сортировка массивов слиянием - она требует дополнительной памяти для формирования слитых
результатов. Однако существуют эффективные алгоритмы, которые умеют сливать соседствующие
в памяти массивы прямо на месте ("in-place"), без привлечения третьего массива. Эти
алгоритмы, однако, далеко не тривиальны и, как правило, не используются в практических
реализациях сортировки слиянием.

функция для сортировка многомерного массива

#php #массивы #функции #сортировка

есть массив

$menu = [
     'tasks' => [
         'title' => 'Задачи',
         'path' => '/route/tasks/',
         'sort' => 3
     ],
     'obj' => [
         'title' => 'Цели',
         'path' => '/route/obj/',
         'sort' => 2
     ],
     'index' => [
         'title' => 'Главная',
         'path' => '/route/index/',
         'sort' => 1
     ],
     'message' => [
         'title' => 'Сообщения и предложения',
         'path' => '/route/message/',
         'sort' => 5
     ],
     'friends' => [
         'title' => 'Друзья',
         'path' => '/route/friends/',
         'sort' => 4
         ]
];


нужно отсортировать его по ключу 'sort'.
через функцию usort сортируется как надо:

$key = 'sort';
$sort = 'desc';

usort($menu, function ($a, $b) use ($key, $sort) {
    if ($sort == 'asc') {
        if ($a[$key] == $b[$key]) {
          return 0;
        }
        return ($a[$key] > $b[$key]) ? 1 : -1;
    }
    if ($sort == 'desc') {
        if ($a[$key] == $b[$key]) {
          return 0;
        }
        return ($a[$key] > $b[$key]) ? -1 : 1;
    }
});

echo '
';
var_dump($menu);


вывод: 

array(5) {
  [0]=>
  array(3) {
    ["title"]=>
    string(44) "Сообщения и предложения"
    ["path"]=>
    string(15) "/route/message/"
    ["sort"]=>
    int(5)
  }
  [1]=>
  array(3) {
    ["title"]=>
    string(12) "Друзья"
    ["path"]=>
    string(15) "/route/friends/"
    ["sort"]=>
    int(4)
  }
  [2]=>
  array(3) {
    ["title"]=>
    string(12) "Задачи"
    ["path"]=>
    string(13) "/route/tasks/"
    ["sort"]=>
    int(3)
  }
  [3]=>
  array(3) {
    ["title"]=>
    string(8) "Цели"
    ["path"]=>
    string(11) "/route/obj/"
    ["sort"]=>
    int(2)
  }
  [4]=>
  array(3) {
    ["title"]=>
    string(14) "Главная"
    ["path"]=>
    string(13) "/route/index/"
    ["sort"]=>
    int(1)
  }
}


делаю функцию, чтобы принимать значение $array, $key, $sort:

function array_sort($array, $key, $sort) {
   return usort($array, function($a, $b) use ($key, $sort) {
        if ($sort == 'asc') {
            if ($a[$key] == $b[$key]) {
                return 0;
            }
            return ($a[$key] > $b[$key]) ? 1 : -1;
        }
        if ($sort == "desc") {
            if ($a[$key] == $b[$key]) {
            return 0;
        }
        return ($a[$key] > $b[$key]) ? -1 : 1;
        }
    });
}
array_sort($menu, $key = 'sort', $sort = 'asc');
echo '
';
var_dump($menu);


вывод:

array(5) {
  ["tasks"]=>
  array(3) {
    ["title"]=>
    string(12) "Задачи"
    ["path"]=>
    string(13) "/route/tasks/"
    ["sort"]=>
    int(3)
  }
  ["obj"]=>
  array(3) {
    ["title"]=>
    string(8) "Цели"
    ["path"]=>
    string(11) "/route/obj/"
    ["sort"]=>
    int(2)
  }
  ["index"]=>
  array(3) {
    ["title"]=>
    string(14) "Главная"
    ["path"]=>
    string(13) "/route/index/"
    ["sort"]=>
    int(1)
  }
  ["message"]=>
  array(3) {
    ["title"]=>
    string(44) "Сообщения и предложения"
    ["path"]=>
    string(15) "/route/message/"
    ["sort"]=>
    int(5)
  }
  ["friends"]=>
  array(3) {
    ["title"]=>
    string(12) "Друзья"
    ["path"]=>
    string(15) "/route/friends/"
    ["sort"]=>
    int(4)
  }
}


подскажите пожалуйста, почему не работает функция, в чем я допустил ошибку? 
    

Ответы
Ответ 1

Вы передаете в свою функцию массив по значению, а не по ссылке. В итоге функция array_sort
принимает копию исходного массива и сортирует ее не трогая оригинальный массив.

Измените объявление функции на

function array_sort(&$array, $key, $sort) {
                   ^^^


и все будет работать

Python, Как отсортировать список на основе другого списка?

#python #python_3x #алгоритм #сортировка

box_b = [7, 3, 9, 5]
box_a = [apple, banana, cherry, lemon]


Суть в том, что после сортировки box_b мне нужен box_a отсортированный таким же образом.

*after sorting box_b and some algorithm*

box_b = [3, 5, 7, 9]
box_a = [banana, lemon, apple, cherry]

    

Ответы

Ответ 1

box_b = [7, 3, 9, 5]
box_a = ['apple', 'banana', 'cherry', 'lemon']

new_b, new_a = zip(*[(b, a) for b, a in sorted(zip(box_b, box_a))])

print(new_b)
(3, 5, 7, 9)

print(new_a)
('banana', 'lemon', 'apple', 'cherry')


Ответ 2

Ещё можно сделать arg_sort — получить список индексов, по которым нужно пройти, чтобы
получить отсортированный список. Это удобно, если данные тяжёлые, а вам нужна только
итерация по отсортированным данным.

box_b = [7, 3, 9, 5]
box_a = ['apple', 'banana', 'cherry', 'lemon']

arg_sort = sorted(range(len(box_b)), key=lambda i: box_b[i])
print([box_b[i] for i in arg_sort])
print([box_a[i] for i in arg_sort])
# [3, 5, 7, 9]
# ['banana', 'lemon', 'apple', 'cherry']

Сортировка массива точек, расположенных вдоль замкнутого контура.

#алгоритм #сортировка

Есть массив точек X{x,y}, образующих замкнутый гладкий контур (аэродинамический профиль).
Точки изначально расположены в массиве хаотично и неравномерно. Подскажите алгоритм
сортировки, позволяющий расположить точки по логическому порядку.

UPD. Лимит коментариев((. Точки на профиле расположены примерно так (в большинстве
случаев)



т.е. в местах с большим радиусом кривизны пореже и наоборот. Шаг точеки может быть
как маленьким, так и относительно большим. (@alexz) 
    

Ответы

Ответ 1

Или я неправильно понял условие или однозначного решения нет.
Например на приведеной ниже картинке точки можно расположить как минимум в 2-х разных
порядках:


UPD: если предположить, что профиль выпуклый, то можно просто найти выпуклую оболочку
множества (одним из алгоритмов из приведенных в конце статьи на Википедии), а затем
взять точки в том порядке, в котором они встречаются в выпуклой оболочке.


Ответ 2

По мне - для начала достаточно отсортировать по возрастанию координат. Например,
по x. Если будут точки с одинаковой координатой x - отсортировать их по y. Теперь если
их соединить получается ломаная. Зигзагообразная. А теперь нужно придумать как разбить
точки на два класса - на одну кривую аэродинамического профиля и на другую. Пока идеи
нет как это сделать.
Если фигура стабильно выпуклая - можно заюзать алгоритмы триангуляции. Они как раз
делают массив "ребер" на выходе, а затем уже можно выбрать среди них нужные.


Ответ 3

Находим центр. Точка с коорд x0 = средняя X всех точек, y0 аналогично. Вариант: (xmin+xmax)/2,
и y так же
Вычисляете угол между центром и точкой (центр в полярной системе координат) в диапазоне
 от 0 до 2pi (или -pi до pi)
Сортируете в нужном Вам порядке обхода


Но это только для выпуклых фигур.

Пример неправильного порядка при обходе против часовой стрелки (для вогнутого участка)
Профиль конечно от огурца, но тут уж увы.



Вот тут одна из проблем автоматического построения


Ответ 4

Берем произвольную точку.
Вычеркиваем из общего списка неразобранных точек, помещаем в выходной список.
Находим точку, которая ближе всего к исходной. Используем обычную декартовскую меру
расстояния.
Вычеркиваем ее из списка неразобранных, помещаем в выходной список.
Если есть еще неразобранные точки - идем к п.3.

По замечаниям и обсуждениям усисливаем позицию :-) :

Классический сплайн одной переменной строится так: область определения разбивается
на конечное число отрезков, на каждом из которых сплайн совпадает с некоторым алгебраическим
полиномом. Максимальная степень из использованных полиномов называется степенью сплайна.
Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна.
Например, непрерывная ломаная есть сплайн степени 1 и дефекта 1.

Если простая декартова мера оказывается недостаточной, можно воспользоваться старыми
добрыми сплайнами. Заметьте, не я усложняю задачу... строим сплайн для комбинаций из
4 ближайших точек и выбираем ту, для которой степень слайна оказывается минимальной.
Но начинать надо с одного из концов фигуры - чтобы мы сразу начали двигаться по одной
из долей - верхней или нижней.