SIGSEV in quicksort implementation

general
, , , ,
1

please help me fix the SIGSEV violation at line 5(acc to gdb) of this quicksort implementation @: http://ideone.com/i04HMG

2

I don’t understand what your are doing in your partition function.

Follow along here for the pseudocode.

Here is an implementation of the in-place quicksort function.

3

Line 30 calls quicksort(a, 0, 9)
Line 21 calls partition(a, 0, 0, 9)

original array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1} //from line 28,29

Now, look at the def. of partition()

i = 0, j = 9, x = 0
a[i] = 10, a[j] = 1, a[x] = 10.

Line 5: while(a[i]<=a[x]) i++;

10 <= 10 True (i++)
9 <= 10 True (i++)
8 <= 10 True (i++)
…

and so on. Next as soon as i = 10, an attempt to a[10] <= a[0] is made and hence the SIGSEGV.

P.S.: I have mentioned the reason, now I want you to try again and think a little bit and implement again.

2 Likes
4

@xylon97 : the problem in the code was that i did not put a limit on i. In a case where the pivot element is the max i keeps rising and jumps past the right end of the array.Hence the SIGSEV.

1 Like