Реализация собственной быстрой сортировки на динамическом массиве

Question

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

string * sortArray;

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

sortArray = new string[_numberOfNames];

for(int i = 0; i < _numberOfNames; ++i){
    sin >> _data[i];
}

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

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

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

Любая помощь будет высоко ценится.

PS Я знаю о STD:: sort, у меня уже есть это в программе, я просто пытаюсь реализовать сортировку самостоятельно.

Answer 1

Два варианта, как в комментариях выше:

1.) Используйте std :: vector. Там вы можете иметь массивы переменного размера.

2.) Используйте «быструю» версию быстрой сортировки, которая выполняет сортировку в исходном массиве. Смотри http://en.wikipedia.org/wiki/Quicksort#In-place_version

Answer 2

Допустим, у вас есть размер массива N
, а ваше значение поворота равно x

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