Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Реализация quicksort, проблемы в сортировкой

87K
09 июня 2013 года
Melanxolik
6 / / 09.06.2013
Добрый день.
Уважаемая просьба к 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;
}
360
09 июня 2013 года
P*t*
474 / / 15.02.2007
Примерно так:
Код:
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;
}
87K
09 июня 2013 года
Melanxolik
6 / / 09.06.2013
P*t*, очень благодарен за реализацию, но while не допустим.
414
10 июня 2013 года
CassandraDied
763 / / 24.05.2012
Melanxolik, а где

 
Код:
if (i == mediana) mediana = j;
else if (j == mediana) mediana = i;
в твоём коде?
87K
10 июня 2013 года
Melanxolik
6 / / 09.06.2013
Добавил, и ретурню mediana, но все равно получаю массив:
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 в конце не правильно подсчитывается

414
10 июня 2013 года
CassandraDied
763 / / 24.05.2012
После первого прохода функции partition, массив должен выглядеть так:
 
Код:
1, 2, 5, 3, 7, 14, 7, 26, 12
А он выглядит так, как будто ошибка в циклах и индексы i и j не доходят до медианного элемента.
87K
10 июня 2013 года
Melanxolik
6 / / 09.06.2013
Несколько раз пересчитал, при всем желании даже на бумаге в первом результате кроме:
Цитата:
1, 2, 5, 7, 3, 14, 7, 26, 12

у меня не получается.

414
10 июня 2013 года
CassandraDied
763 / / 24.05.2012
Цитата: Melanxolik
Несколько раз пересчитал, при всем желании даже на бумаге в первом результате кроме:
Цитата:
1, 2, 5, 7, 3, 14, 7, 26, 12

у меня не получается.


Ну, все ошибаются, особенно часто те, кто мало спит. :) Пересчитал ещё раз и у меня получилось вот что:

 
Код:
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
Это если считать, как Страуструп предлагает. Ты, случайно, не его алгоритмы пытаешься реализовать? Очень уж у тебя имена функций на его похожи.
Если его, то не работает, вероятно, из-за его особенной функции выбора медианного элемента, которой у тебя нет.
Ну и из-за того, что у тебя не учитывается возможность менять местами медиану и курсоры.
87K
11 июня 2013 года
Melanxolik
6 / / 09.06.2013
Реализацию брал здесь:
http://www.algolist.net/Algorithms/Sorting/Quicksort
но получается и это не сходится, явно чего-то не так или что-то упускаю.
414
11 июня 2013 года
CassandraDied
763 / / 24.05.2012
Цитата: Melanxolik
Реализацию брал здесь:
http://www.algolist.net/Algorithms/Sorting/Quicksort
но получается и это не сходится, явно чего-то не так или что-то упускаю.


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

414
12 июня 2013 года
CassandraDied
763 / / 24.05.2012
А вот так заработало:

Код:
#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;
}
87K
12 июня 2013 года
Melanxolik
6 / / 09.06.2013
Неожиданно, тремя циклами не думал, попробую еще так.

Тут неожиданно для себя открыл из первого куска кода ошибку при сортировке уже второй части массива когда он выглядит так:
Цитата:

1 2 5 3 7



кажется тут моя и ошибка, все таки наверное если медиана берется из центра её надо уносить или в начало или в конец, потому что:
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
или где-то не так мыслю.

414
12 июня 2013 года
CassandraDied
763 / / 24.05.2012
Варианта I=0, J=0 быть не может, если только у тебя весь массив не состоит из одинаковых элементов.
Варианта I=4 J=4 тоже быть не может. Всегда должно получаться так, чтобы i != j.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог