void quickSortR(int * a, long N) {
long i = 0, j = N;
int temp, p;
// опорный элемент прописан жестко, просто для примера
p = a[1];
do {
while ( a < p ) i++;
while ( a[j] > p ) j--;
if (i <= j) {
temp = a; a = a[j]; a[j] = temp;
i++; j--;
}
} while ( i<=j );
//рекурсию убрал, вопрос не в ней
}
Быстрая сортировка
Никак не пойму.
Есть стандартный алгоритм быстрой сортировки, первая его часть: разбивка массива на две части больше и меньше опорного.
На вики есть (и здесь на форуме тоже) примеры реализации, например:
почему алгоритм на наборе {1,2,3,0}, с опорным элементом с индексом 1, выдает неверный результат? {1, 0, 3, 2}
Есть стандартный алгоритм быстрой сортировки, первая его часть: разбивка массива на две части больше и меньше опорного.
На вики есть (и здесь на форуме тоже) примеры реализации, например:
Код:
почему алгоритм на наборе {1,2,3,0}, с опорным элементом с индексом 1, выдает неверный результат? {1, 0, 3, 2}
может не j=N, а j=N-1?
и еще i++ j-- нужно заменить на
и еще i++ j-- нужно заменить на
Код:
if (a!=p) i++;
if (a[j]!=p) j--;
if (a[j]!=p) j--;
Видно всем пофиг)
Тем не менее: думаю ошибку тут
инкремент после каждого свапа недопустим.
С другой стороны, если этого не сделать на наборах, типа {1,2,15,15,2}, с опорным элементом 15 мы попадаем в бесконечный цикл.
Тем не менее: думаю ошибку тут
Код:
if (i <= j) {
temp = a; a = a[j]; a[j] = temp;
i++; j--;
}
temp = a; a = a[j]; a[j] = temp;
i++; j--;
}
инкремент после каждого свапа недопустим.
С другой стороны, если этого не сделать на наборах, типа {1,2,15,15,2}, с опорным элементом 15 мы попадаем в бесконечный цикл.
Цитата: ChickenIdol
Видно всем пофиг)
Тем не менее: думаю ошибку тут
Тем не менее: думаю ошибку тут
Ну, думайте дальше...
Разобрался. Идея стандартной реализации немного отличается от описания алгоритма в вики:
>>Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него
На деле справа могут оказаться элементы равные опорному, но в конечном счете это не важно. Т.е на месте опорного проводится черта, слева от которой <=, а справа >=
>>Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него
На деле справа могут оказаться элементы равные опорному, но в конечном счете это не важно. Т.е на месте опорного проводится черта, слева от которой <=, а справа >=
Вынос мозга)
При тестах у меня выходит именно так, как написал.
Если есть элементы равные опорному, происходит swap одного на другой, а затем увеличение счетчиков на единицы,
а дальше штатно. Т.е элементы равные опорному могут быть как слева, так и справа.
По коду например: http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8#C
При тестах у меня выходит именно так, как написал.
Если есть элементы равные опорному, происходит swap одного на другой, а затем увеличение счетчиков на единицы,
а дальше штатно. Т.е элементы равные опорному могут быть как слева, так и справа.
По коду например: http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8#C
Цитата: ChickenIdol
почему алгоритм на наборе {1,2,3,0}, с опорным элементом с индексом 1, выдает неверный результат? {1, 0, 3, 2}
Гг... да не было в коде никакой проблемы. Всё правильно - считаем:
Первый проход:
1 2 3 0
while(массив[x]<2) x++;
while(массив[y]>2) y--;
x=1//2
y=3//0
поменяли их местами
1 0 3 2
x++;y--; x=y=2;
2-й проход
1 0 3 2
while(массив[x]<2) x++;//ниразу
while(массив[y]>2) y--;//ниразу
x++;y--;
выход из цикла, т.к. x>y;
Вот ваш код подфиксеный работает:
Код:
#include <iostream>
#include <stdlib.h>
using namespace std;
void qs(int * a, long N) {
long i = 0, j = N-1;
int temp, p;
// опорный элемент прописан жестко, просто для примера
p = a[1];
do {
while ( a < p ) i++;
while ( a[j] > p ) j--;
if (i <= j) {
temp = a; a = a[j]; a[j] = temp;
i++; j--;
}
} while ( i<j );
if(i<N-1)
qs(a+i,N-i);
if(j>0)
qs(a,j+1);
}
int main()
{
int sort[14]={1,0,3,2,7,6,0,5,7,1,4,2,3,7};
cout<<"Начальный массив:"<<endl;
for(int x=0;x<14;x+=1)
cout<<sort[x]<<" ";
cout<<endl;
qs(&sort[0],14);
cout<<"Конечный массив:"<<endl;
for(int x=0;x<14;x+=1)
cout<<sort[x]<<" ";
cout<<endl;
return 0;
}
#include <stdlib.h>
using namespace std;
void qs(int * a, long N) {
long i = 0, j = N-1;
int temp, p;
// опорный элемент прописан жестко, просто для примера
p = a[1];
do {
while ( a < p ) i++;
while ( a[j] > p ) j--;
if (i <= j) {
temp = a; a = a[j]; a[j] = temp;
i++; j--;
}
} while ( i<j );
if(i<N-1)
qs(a+i,N-i);
if(j>0)
qs(a,j+1);
}
int main()
{
int sort[14]={1,0,3,2,7,6,0,5,7,1,4,2,3,7};
cout<<"Начальный массив:"<<endl;
for(int x=0;x<14;x+=1)
cout<<sort[x]<<" ";
cout<<endl;
qs(&sort[0],14);
cout<<"Конечный массив:"<<endl;
for(int x=0;x<14;x+=1)
cout<<sort[x]<<" ";
cout<<endl;
return 0;
}
Но лучше как в описании за опорный брать случайный:
Код:
...
#include <time.h>
...
p = a[rand()%N];
...
int main()
{
srand(time(NULL));
...
#include <time.h>
...
p = a[rand()%N];
...
int main()
{
srand(time(NULL));
...