Реализация quicksort, проблемы в сортировкой
Уважаемая просьба к ALL помочь в поиске неучтенной ошибки которую не могу уловить для того чтобы данный код начал работать.
Другая реализация к сожалению по правилам учебы не возможна, по этому код составлен из базы и чтения мануалов по quicksort.
На входе имеется массив:
ARRAY_PRINT: 1 12 5 26 7 14 3 7 2
Но на выходе получаю:
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
Вижу что сортировка выполнена только частично, но к сожалению в printf уже просидел больше 5ти дней, в различных вариациях и не получается воспроизвести полностью работающее решение которое позволит в достаточной мере изучить данный вид сортировки.
Код:
#include <stdio.h>
#define SIZE 9
void arrayPrint(int array[], int size) {
int last = size - 1;
printf("ARRAY_PRINT: ");
for ( int i = 0; i < last; i++ ) {
printf("%d ", array[i]);
}
printf("%d\n", array[last]);
}
int partition(int array[], int start, int end) {
int temp;
int i = start, j = end;
int mediana = start / 2 + end / 2;
int pivot = array[mediana];
int flag = 1;
for ( ; i <= j ; i++ ) {
if ( array[i] >= pivot ) {
for ( ; j >= i & flag; j-- ) {
if ( pivot >= array[j] ) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
flag = 0;
}
}
}
flag = 1;
}
arrayPrint(array, SIZE);
return i-1;
}
int quicksort(int array[], int start, int end) {
int pivot;
if ( start < end ) {
pivot = partition( array, start, end );
quicksort( array, start, pivot - 1);
arrayPrint(array, SIZE);
quicksort( array, pivot + 1, end );
}
return 0;
}
int main() {
int size = 9;
int array[9] = { 1, 12, 5, 26, 7, 14, 3, 7, 2 };
int start = 0;
int end = 8;
quicksort(array, start, end);
arrayPrint(array, size);
return 0;
}
#define SIZE 9
void arrayPrint(int array[], int size) {
int last = size - 1;
printf("ARRAY_PRINT: ");
for ( int i = 0; i < last; i++ ) {
printf("%d ", array[i]);
}
printf("%d\n", array[last]);
}
int partition(int array[], int start, int end) {
int temp;
int i = start, j = end;
int mediana = start / 2 + end / 2;
int pivot = array[mediana];
int flag = 1;
for ( ; i <= j ; i++ ) {
if ( array[i] >= pivot ) {
for ( ; j >= i & flag; j-- ) {
if ( pivot >= array[j] ) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
flag = 0;
}
}
}
flag = 1;
}
arrayPrint(array, SIZE);
return i-1;
}
int quicksort(int array[], int start, int end) {
int pivot;
if ( start < end ) {
pivot = partition( array, start, end );
quicksort( array, start, pivot - 1);
arrayPrint(array, SIZE);
quicksort( array, pivot + 1, end );
}
return 0;
}
int main() {
int size = 9;
int array[9] = { 1, 12, 5, 26, 7, 14, 3, 7, 2 };
int start = 0;
int end = 8;
quicksort(array, start, end);
arrayPrint(array, size);
return 0;
}
Код:
int partition(int array[], int start, int end) {
int temp;
int i = start, j = end;
int mediana = (start + end) / 2;
int pivot = array[mediana];
while (i < j) {
while (array[i] <= pivot && i < mediana) i++;
while (array[j] >= pivot && j > mediana) j++;
temp = array[i];
array[i] = array[j];
array[j] = temp;
if (i == mediana) mediana = j;
else if (j == mediana) mediana = i;
}
return mediana;
}
int temp;
int i = start, j = end;
int mediana = (start + end) / 2;
int pivot = array[mediana];
while (i < j) {
while (array[i] <= pivot && i < mediana) i++;
while (array[j] >= pivot && j > mediana) j++;
temp = array[i];
array[i] = array[j];
array[j] = temp;
if (i == mediana) mediana = j;
else if (j == mediana) mediana = i;
}
return mediana;
}
P*t*, очень благодарен за реализацию, но while не допустим.
Код:
if (i == mediana) mediana = j;
else if (j == mediana) mediana = i;
else if (j == mediana) mediana = i;
ARRAY_PRINT: 1 2 3 7 5 14 7 12 26
А если брать по выводу:
./test.run
ARRAY_PRINT: 1 2 5 7 3 14 7 26 12
MEDIANA:6, ARRAY[MEDIANA]:7
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
MEDIANA:4, ARRAY[MEDIANA]:5
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
MEDIANA:1, ARRAY[MEDIANA]:2
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
MEDIANA:2, ARRAY[MEDIANA]:3
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
ARRAY_PRINT: 1 2 3 7 5 14 7 12 26
MEDIANA:8, ARRAY[MEDIANA]:26
ARRAY_PRINT: 1 2 3 7 5 14 7 12 26
ARRAY_PRINT: 1 2 3 7 5 14 7 12 26
MEDIANA:6, ARRAY[MEDIANA]:7
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
MEDIANA:4, ARRAY[MEDIANA]:5
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
MEDIANA:1, ARRAY[MEDIANA]:2
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
MEDIANA:2, ARRAY[MEDIANA]:3
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
ARRAY_PRINT: 1 2 3 7 5 14 7 26 12
ARRAY_PRINT: 1 2 3 7 5 14 7 12 26
MEDIANA:8, ARRAY[MEDIANA]:26
ARRAY_PRINT: 1 2 3 7 5 14 7 12 26
ARRAY_PRINT: 1 2 3 7 5 14 7 12 26
То похоже mediana в конце не правильно подсчитывается
Код:
1, 2, 5, 3, 7, 14, 7, 26, 12
Несколько раз пересчитал, при всем желании даже на бумаге в первом результате кроме:
Цитата: Melanxolik
Ну, все ошибаются, особенно часто те, кто мало спит. :) Пересчитал ещё раз и у меня получилось вот что:
Код:
1, 12, 5, 26, 7, 14 3, 7, 2 l = 1, r = 8
1, 2, 5, 26, 7, 14, 3, 7, 12 l = 3, r = 6
1, 2, 5, 3, 7, 14, 26, 7, 12 l = 4, r = 3
1, 2, 5, 26, 7, 14, 3, 7, 12 l = 3, r = 6
1, 2, 5, 3, 7, 14, 26, 7, 12 l = 4, r = 3
Если его, то не работает, вероятно, из-за его особенной функции выбора медианного элемента, которой у тебя нет.
Ну и из-за того, что у тебя не учитывается возможность менять местами медиану и курсоры.
http://www.algolist.net/Algorithms/Sorting/Quicksort
но получается и это не сходится, явно чего-то не так или что-то упускаю.
Цитата: Melanxolik
Реализацию брал здесь:
http://www.algolist.net/Algorithms/Sorting/Quicksort
но получается и это не сходится, явно чего-то не так или что-то упускаю.
http://www.algolist.net/Algorithms/Sorting/Quicksort
но получается и это не сходится, явно чего-то не так или что-то упускаю.
Не сходится, потому что реализация, взятая мною из книги по структурам данных, отличается от той, что дана на сайте. Главное — это идея алгоритма, а реализацию можно и оптимизировать.
Код:
#define SIZE 9
template< typename T>
void arrayPrint(T& arr)
{
for(auto &num : arr)
std::cout << num << " ";
std::cout << std::endl;
}
int partition(int array[], int start, int end)
{
int pivot, i , j;
pivot = i = j = 0;
if(start == end)
return 0;
if(end - start == 1)
{
if(array[end] < array[start])
std::swap(array[end], array[start]);
return 0;
}
pivot = array[(start + end) / 2];
for(i = start, j = end ; i < j;)
{
for(; array[i] < pivot && i < end; ++i);
for(; array[j] >= pivot && j > start; --j);
if(i < j)
std::swap(array[i++], array[j--]);
}
if(j == 0)
return i;
else
return j;
}
void quicksort(int array[], int start, int end)
{
int median = partition(array, start, end);
if(median != 0)
{
quicksort(array, start, median);
quicksort(array, median +1, end);
}
}
int main()
{
int array[SIZE] = { 1, 12, 5, 26, 7, 14, 3, 7, 2 };
int start = 0;
int end = SIZE - 1;
quicksort(array, start, end);
arrayPrint(array);
return 0;
}
template< typename T>
void arrayPrint(T& arr)
{
for(auto &num : arr)
std::cout << num << " ";
std::cout << std::endl;
}
int partition(int array[], int start, int end)
{
int pivot, i , j;
pivot = i = j = 0;
if(start == end)
return 0;
if(end - start == 1)
{
if(array[end] < array[start])
std::swap(array[end], array[start]);
return 0;
}
pivot = array[(start + end) / 2];
for(i = start, j = end ; i < j;)
{
for(; array[i] < pivot && i < end; ++i);
for(; array[j] >= pivot && j > start; --j);
if(i < j)
std::swap(array[i++], array[j--]);
}
if(j == 0)
return i;
else
return j;
}
void quicksort(int array[], int start, int end)
{
int median = partition(array, start, end);
if(median != 0)
{
quicksort(array, start, median);
quicksort(array, median +1, end);
}
}
int main()
{
int array[SIZE] = { 1, 12, 5, 26, 7, 14, 3, 7, 2 };
int start = 0;
int end = SIZE - 1;
quicksort(array, start, end);
arrayPrint(array);
return 0;
}
Тут неожиданно для себя открыл из первого куска кода ошибку при сортировке уже второй части массива когда он выглядит так:
кажется тут моя и ошибка, все таки наверное если медиана берется из центра её надо уносить или в начало или в конец, потому что:
I=0, J=0
1 > 5 = 0 I=1, J=4
2 > 5 = 0 I=2, J=4
5 > 5 = 0 I=3, J=4
3 > 5 = 0 I=4 J=4
I < J
или где-то не так мыслю.
Варианта I=4 J=4 тоже быть не может. Всегда должно получаться так, чтобы i != j.