1 / 1 / 1
Регистрация: 02.03.2013
Сообщений: 185
1

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

03.05.2019, 21:10. Показов 1993. Ответов 1

Решил реализовать алгоритм быстрой сортировки. Иногда, программа работает корректно. Иногда, падает с ошибкой сегментации.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
typedef int ELEMENT;
 
void quick_sort(ELEMENT *arr, size_t size)
{
  if (arr != NULL && size > 1)
     __quick_sort__(arr, 0, size - 1);
}
 
static void __quick_sort__(ELEMENT *arr, size_t index_low, size_t index_hight)
{
  size_t m = 0;
  if (index_hight > index_low)
  {
      m = __partition__(arr, index_low, index_hight);
    __quick_sort__(arr, index_low, m - 1);
    __quick_sort__(arr, m + 1, index_hight);
  }
}
 
static size_t __partition__(ELEMENT *array, size_t index_low, size_t index_hight)
{
  ELEMENT key = array[index_low];
  size_t j = index_low;
 
  for (size_t i = index_low + 1; i <= index_hight; ++i)
  {
    if(array[i] <= key)
    {
      j = j + 1;
      swap(&array[j], &array[i], sizeof(ELEMENT));
    }
 
  }
  swap(&array[index_low], &array[j], sizeof(ELEMENT));
  return j;
}

Вот что выдаёт gdb:
Кликните здесь для просмотра всего текста

Program received signal SIGSEGV, Segmentation fault.
0x0000555555554de4 in __partition__ (array=0x555555757260, index_low=0,
index_hight=18446744073709551615)
at /home/dosart/Programing_Language/C/Sort/src/QuickSort.c:37
37 if(array[i] <= key)



Ошибка пропадает, если заменить size_t на int. Не могу понять в чём причина. Насколько я понимаю, size_t обычно применяется для счетчиков циклов, индексации массивов, хранения размеров, адресной арифметики.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.05.2019, 21:10
Ответы с готовыми решениями:

Реализация алгоритма быстрой сортировки quickSort
это алгоритм быстрой сортировки quickSort прошу напишите значение строк файл исходного...

Реализация быстрой сортировка и сортировки "сливом"
Помоги те с реализацией быстрой сортировки и сортировки сливом на базовом уровне.

Пример быстрой сортировки массива строк и сортировки методом выбора
Добрый вечер. Скиньте пожалуйста пример быстрой сортировки массива строк и сортировки массива строк...

Визуализатор быстрой сортировки
Добрый день! Нужно написать программу, которая иллюстрирует работу быстрой сортировки. В...

1
32 / 21 / 12
Регистрация: 13.09.2017
Сообщений: 74
03.05.2019, 23:56 2
Лучший ответ Сообщение было отмечено schoolboy_ как решение

Решение

Дело в том, что переменная m может принимать значение 0:

C++
1
2
3
4
5
6
7
8
9
10
static void __quick_sort__(ELEMENT *arr, size_t index_low, size_t index_hight)
{
  size_t m = 0;
  if (index_hight > index_low)
  {
      m = __partition__(arr, index_low, index_hight); // здесь возможна ситуация, когда m = 0
    __quick_sort__(arr, index_low, m - 1); // здесь index_hight должен быть равен -1 ? Но не будет
    __quick_sort__(arr, m + 1, index_hight);
  }
}
Почему же это тогда работает, если мы заменим size_t на int ? На самом деле, все просто: переменная типа int может принимать отрицательные значения, поэтому при вызове рекурсивной функции, сработает условие

C++
1
  if(index_hight > index_low)
И мы больше не зайдем в этот блок. Однако когда мы имеем дело с size_t - необходимо помнить, что он не может принимать отрицательные значения. При попытке присвоить отрицательное число переменной типа size_t, мы в действительности присвоим ему число наибольшее. Поэтому когда m будет равным нулю, в переменную index_hight запишется что-то вроде 18446744073709551615. Соответственно, условие того, что правая граница больше - выполнится, и тогда мы в функции __partition__ попытаемся обратиться к элементу за границами массива, и в результате получим segmentation fault.

Самый простой метод исправления - просто добавить проверку:

C++
1
2
3
4
m = __partition__(arr, index_low, index_hight);
 
if(m > 0)
      __quick_sort__(arr, index_low, m - 1);
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.05.2019, 23:56

Алгорим быстрой сортировки
В одной из тем выложен алгоритм быстрой сортировки. Возник вопрос: если индексы i и j указывают на...

Алгоритм Быстрой Сортировки на C++
Можно ли этот алгоритм использовать для последовательности чисел? Просто в книге Сэджвика...

Тонкости быстрой сортировки
Излазил кучу мест в сети. Нашел массу этих алгоритмов, но на поверку практически каждый не совсем...

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

Алгоритм быстрой сортировки
Написать программу, реализующую алгоритм быстрой сортировки(рекурсивный) для массива целых чисел.

Не алгоритм быстрой сортировки
Просто как подключить эту функцию Не работаеееет #include&lt;iostream&gt; #include&lt;iomanip&gt; #include...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.