14 Сен


2017

Сортировка слиянием. Merge Sort.

Алгоритм сортировки со средней сложостью O(n), достаточно прост в реализации в отличии от того же QuickSort. Я чуть отошел от c++ и реализовал данный алгоритм  на Go, т.к. начал его изучать и мне очень понравился синтаксис, конечно не питон но по сравнению с си он шикрен. В связи с этим возможно я упустил какие-то моменты связанные непосредственно с языком. На c++/c в принципе реализация будет весьма похожей, за исключением того что там нужно будет выделтяь память под массив врчную с помощью Malloc или New.

Ну просто нафиг никому не нужная лирика.

Чуть приблизлся в своем изучении различных алгоритмов сортировки и разборе их на практике. Алгоритм простой для восприятия, лично для осознания его мне хватило краткого описания и картинки (см ниже) с википедии. Кроме того данный алгоритм не столь бесполезен как предыдущие (ну кроооме богсорта, он великолепен).

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

Собственно сам алгоритм сортировки слиянием отлично воспринимается пикчей с википедии:

Для простоты восприятия я декомпозировал алгоритм на 2 функции, первая банально соединяет 2 (отсортированных массива) в 1 отсортированный. Таким образом если у нас есть много массивов из 1 элемента то можно собрать 1 отсортированный. 

func combine_mas(first_mas []float64, second_mas []float64) []float64 {
  var left_pos = 0
  var right_pos = 0
  var result_mas = []float64{}

  for true {
    if left_pos >= len(first_mas) {
      result_mas = append(result_mas, second_mas[right_pos:len(second_mas)]...)
      break
     } else if right_pos >= len(second_mas) {
      result_mas = append(result_mas, first_mas[left_pos:len(first_mas)]...)
      break
     } else {
          if first_mas[left_pos] < second_mas[right_pos] {
            result_mas = append(result_mas, first_mas[left_pos])
            left_pos++
          } else {
            result_mas = append(result_mas, second_mas[right_pos])
            right_pos++
          }
     }
  }
  return result_mas
}

Зная это нам остается рекурсивно разбить существующий массив на множество составляющих подмассивов с длинной равной единице. Что я собственно и сделал, дословно: если длина полученного массива == 1 то возвращаем его в качестве результата, в противном случае разбиваем его на 2 части и вызываем для каждой из них рекурсивно функцию, по возвращению результата комбинируем из полученных значений (функция combine_mas) и возвращаем массив как результат.

func merge_sort(slice []float64) []float64  {
  var result_mas = []float64{}
  if len(slice) == 1 {
    fmt.Println(slice)
    return slice
  } else {
    var left_slice = slice[0:len(slice)/2]
    var right_slice = slice[len(slice)/2:len(slice)]
    left_slice = merge_sort(left_slice)
    right_slice = merge_sort(right_slice)
    result_mas = combine_mas(left_slice, right_slice)
  }
  return result_mas
}

Собственно на этом все, сорцы можно посмотреть тут. В следующий раз реализую быструю сортировку.

сортировка