27 Окт


2017

Быстрая сортировка, передача среза через указатель.

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

Изначально опорный элемент выбирается центральным, Но после первого прохода partition может разбить массив на 2 неравные части, вернув I индекс, он же индекс смещения слева при свапе элементов, сильно отличный от центрального, После индекса данного элемента все значения будут больше чем опорный (взятый изначально как сумма low hi значений деленая на 2). Отсюда и мое непонимание этого, по началу я очень долго бился с нерабочей процедурой partition, уже тупо взятой с википедии на си.

Собственно моя реализация на языке Go (по сути алгоритм взят с википедии, но разобран мной по байтикам) 

func partition(mas_pointer *[]float64, l int, h int) int {
  mas := *mas_pointer
  midl := mas[(l + h) / 2]
  for l <= h {
    for mas[l] < midl {
      l++
    }
    for mas[h] > midl {
      h--
    }
    if l <= h {
      tmp := mas[l]
      mas[l] = mas[h]
      mas[h] = tmp
      l++
      h--
    }
  }
  fmt.Printf("l - %d, h - %d\n", l, h)
  fmt.Println(mas)
  return l
}

func quick_sort(mas_pointer *[]float64, l int, h int) {
  if l < h{
    p := partition(mas_pointer, l, h)
    quick_sort(mas_pointer, l, p - 1)
    quick_sort(mas_pointer, p, h)
  }
}

func main() {
  mas := []float64{12, 11, 1923, 8942, 123, 941, -643}
  fmt.Println("Массив до начала сортировки\n", mas)
  quick_sort(&mas, 0, len(mas) - 1)
  fmt.Println("Массив после начала сортировки\n", mas)
}

Ну и сорцы

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