Reputation: 545
Segmentation Fault While Sorting
I have implemented quick-sort.But this code is giving me segmentation fault.
#include<stdio.h>
#include<stdlib.h>
void Quick_Sort(int *a,int p,int r);
int partition(int *a,int p,int r);
int main(){
int testcase,num,search;
int i,j,*array;
scanf("%d",&testcase);
for(i=0;i<testcase;i++){
scanf("%d",&num);
array=malloc(sizeof(int)*num);
for(j=0;j<num;j++){
scanf("%d",(array+j));
}
Quick_Sort(array,0,num-1);
scanf("%d",&search);
/*for(j=0;j<num;j++){
if(search==*(array+j)){
printf("%d\n",j+1 );
break;
}
}*/
}
for(i=0;*(array+i)!='\0';++i){
printf("%d ",*(array+i));
}
}
void Quick_Sort(int *a,int p,int r){
int q;
if(p<r){
q=partition(a,p,r);
Quick_Sort(a,p,q);
Quick_Sort(a,q+1,r);
}
}
int partition(int *a,int p,int r){
int i,j,x,temp;
i=p-1;
j=r+1;
x=*(a+p);
while(1){
do{
j=j-1;
}
while(x<=(*(a+j)));
do{
i=i+1;
}
while(x>=(*(a+i)));
if(i<j){
temp=*(a+i);
*(a+i)=*(a+j);
*(a+j)=temp;
}else{
return j;
}
}
Upvotes: 0
Views: 278
Answers (2)
Reputation: 755026
Reading the data
Your data file seems to be structured as:
T
N1 V11 V12 V13 ... V1N S1
N2 V21 V22 V23 ... V2N S2
...
You have a total number of test cases, T. Then for each test case, you have a number of entries in the array (N1, N2, etc), each time followed by the appropriate number of values, V11 .. V1N, and a spare value which you're supposed to search for (all described using 1-based array notations; in C, you'll be using 0-based arrays). Although I've shown the data for each test set all on a single line, the actual data file could have the numbers laid out in any sequence — everything could be on one line, or each number on a line of its own possibly with blank lines separating them, or any mixture of these formats.
The main() program you show does not do a particularly good job of reading that data. It lacks all error checking. It uses the (legal but) bizarre *(array + i) notations instead of the simpler to understand array[i] notation, apparently in the belief that it will be more efficient. When you use pointers for efficiency, you don't keep on adding i to the value before dereferencing the pointer. Your code dynamically allocates memory but never frees it, leaking horribly.
Reading the data using subscript notation
In this revised code, I'm using return 1; to exit from the program. It should print an error message too, but I'm moderately lazy.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int testcase, num, search;
int i, j, *array;
if (scanf("%d", &testcase) != 1)
return 1;
for (i = 0; i < testcase; i++)
{
if (scanf("%d", &num) != 1)
return 1;
array = malloc(sizeof(int)*num);
if (array == 0)
return 1;
for (j = 0; j < num; j++)
{
if (scanf("%d", &array[j]) != 1)
return 1;
}
//Quick_Sort(array, 0, num-1);
if (scanf("%d", &search) != 1)
return 1;
for (j = 0; j < num; j++)
{
if (search == array[j])
{
printf("%d\n", j+1);
break;
}
}
// Print the array - best encapsulated in a small function
for (j = 0; j < num; j++)
{
printf(" %d", array[j]);
if (j % 10 == 9)
putchar('\n');
}
if (j % 10 != 0)
putchar('\n');
// Prevent memory leaks
free(array);
}
return 0;
}
I note in passing that the search loop will work whether or not the QuickSort sorts the data; it makes no use of the fact that the array is sorted. You could print the data before the sort and after the sort. You should tag the output to identify what you're printing. For example, the search code might write:
printf("Found %d at %d\n", search, j);
You also do not identify when the value being searched for is not found.
It is also often a good idea to print the data you read after you've read it and before you process it, just to make sure that your program is getting the data you expect it to get. It can lead to confusion if the program isn't working on the data you think it is working on.
Note that this code does not make any assumptions about the values in the arrays beyond 'they are valid integers'. And it does check every input operation. Tedious though it may seem, it is necessary to head off trouble.
Reading the data using pointer notation
Here is code making more or less idiomatic use of pointers:
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int testcase;
if (scanf("%d", &testcase) != 1)
return 1;
for (int i = 0; i < testcase; i++)
{
int num;
if (scanf("%d", &num) != 1)
return 1;
int *array = malloc(sizeof(int)*num);
if (array == 0)
return 1;
int *end = array + num;
int *ptr;
for (ptr = array; ptr < end; ptr++)
{
if (scanf("%d", ptr) != 1)
return 1;
}
//Quick_Sort(array, 0, num-1);
int search;
if (scanf("%d", &search) != 1)
return 1;
for (ptr = array; ptr < end; ptr++)
{
if (search == *ptr)
{
break;
}
}
if (ptr < end)
printf("Found %d at %td\n", search, ptr - array + 1);
else
printf("Missing %d\n", search);
// Print the array - best encapsulated in a small function
printf("Array (%d):", num);
int j;
for (j = 0; j < num; j++)
{
printf(" %d", array[j]);
if (j % 10 == 9)
putchar('\n');
}
if (j % 10 != 0)
putchar('\n');
// Prevent memory leaks
free(array);
}
return 0;
}
The printing loop is simplest if written using indexing, so I didn't change it to use pointers. It could be done, but using (ptr - array) instead of j in the 'is it time to print a newline' code makes it less worthwhile. The code uses C99 features like declaring variables as they're needed and the t qualifier in %td for the ptrdiff_t value. It could be written to use a VLA instead of malloc(), too.
Sample input data
3
2 1 2 1
3 3 2 0 1
4 5 4 3 2 4
Sample output
Found 1 at 1
Array (2): 1 2
Missing 1
Array (3): 3 2 0
Found 4 at 2
Array (4): 5 4 3 2
Working Quicksort Code
Your partition algorithm was defective. It is fixed, with key changes marked. The debugging scaffolding that I used while sorting out the issues is left in place, with many of the printing operations that guided me commented out. Read Programming Pearls by Jon Bentley, especially 'Column 11: Sorting' (chapter 11, but the chapters were originally columns in the Communications of the ACM, hence the designation Column 11). It was an invaluable guide while fixing the problems.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Quick_Sort(int *a, int p, int r);
static int partition(int *a, int p, int r);
static void dump_partition(char const *tag, int const *data, int lo, int hi);
/* Debugging functions */
static void check_sorted(int const *data, int lo, int hi);
static int *copy_partition(int const *data, int lo, int hi);
static void check_consistency(int const *a1, int const *a2, int lo, int hi);
int main(void)
{
int testcase, num, search;
int i, j, *array;
if (scanf("%d", &testcase) != 1)
return 1;
for (i = 0; i < testcase; i++)
{
if (scanf("%d", &num) != 1)
return 1;
array = malloc(sizeof(int)*num);
if (array == 0)
return 1;
for (j = 0; j < num; j++)
{
if (scanf("%d", &array[j]) != 1)
return 1;
}
printf("\nData set %d:\n", i);
int *copy = copy_partition(array, 0, num-1);
dump_partition("Before:", array, 0, num-1);
//dump_partition("Copy", copy, 0, num-1);
Quick_Sort(array, 0, num-1);
dump_partition("After: ", array, 0, num-1);
check_sorted(array, 0, num-1);
check_consistency(array, copy, 0, num-1);
free(copy);
if (scanf("%d", &search) != 1)
return 1;
for (j = 0; j < num; j++)
{
if (search == array[j])
break;
}
if (j < num && search == array[j])
printf("Found %d at %d\n", search, j+1);
else
printf("Missing %d\n", search);
// Prevent memory leaks
free(array);
}
return 0;
}
/* Although we're interested in data[lo]..data[hi], the copy must have data[0]..data[lo-1] too */
static int *copy_partition(int const *data, int lo, int hi)
{
assert(lo <= hi);
size_t nbytes = (hi + 1) * sizeof(int);
int *space = (int *)malloc(nbytes);
if (space == 0)
{
fputs("Out of memory\n", stderr);
exit(1);
}
memmove(space, data, nbytes);
return(space);
}
/* Check that the two arrays contain the same sets of data */
/* Each value in a1 must be present in a2 and vice versa */
static void check_consistency(int const *a1, int const *a2, int lo, int hi)
{
int *a3 = copy_partition(a1, lo, hi);
int a3_lo = lo;
int a3_hi = hi;
//printf("-->> check_consistency:\n");
//dump_partition("a1", a1, lo, hi);
//dump_partition("a2", a2, lo, hi);
//dump_partition("a3", a3, lo, hi);
for (int i = lo; i <= hi; i++)
{
int found = 0;
for (int j = a3_lo; j <= a3_hi; j++)
{
if (a2[i] == a3[j])
{
/* Found a match for a2[i] at a3[j] */
/* Move a3[j] to end of array and ignore it from here on */
//printf("Found a2[%d] = %d at a3[%d] = %d\n", i, a2[i], j, a3[j]);
int t = a3[a3_hi];
a3[a3_hi] = a3[j];
a3[j] = t;
a3_hi--;
//dump_partition("a3-free", a3, a3_lo, a3_hi);
//dump_partition("a3-used", a3, a3_hi+1, hi);
found = 1;
break;
}
}
if (!found)
{
printf("No value %d for a2[%d] in a1\n", a2[i], i);
dump_partition("a2", a2, lo, hi);
dump_partition("a1-free", a3, a3_lo, a3_hi);
dump_partition("a1-used", a3, a3_hi+1, hi);
}
}
free(a3);
//printf("<<-- check_consistency\n");
}
static void dump_partition(char const *tag, int const *data, int lo, int hi)
{
printf("%s [%d..%d]%s", tag, lo, hi, (hi - lo) > 10 ? "\n" : "");
int i;
for (i = lo; i <= hi; i++)
{
printf(" %2d", data[i]);
if ((i - lo) % 10 == 9)
putchar('\n');
}
if ((i - lo) % 10 != 0 || i == lo)
putchar('\n');
}
static void check_sorted(int const *data, int lo, int hi)
{
//printf("-->> check_sorted:\n");
for (int i = lo; i < hi; i++)
{
if (data[i] > data[i+1])
printf("Out of order: a[%d] = %d bigger than a[%d] = %d\n", i, data[i], i+1, data[i+1]);
}
//printf("<<-- check_sorted\n");
}
void Quick_Sort(int *a, int p, int r)
{
if (p < r)
{
int q = partition(a, p, r);
//dump_partition("Lo Range", a, p, q-1);
//printf("Pivot: a[%d] = %d\n", q, a[q]);
//dump_partition("Hi Range", a, q+1, r);
Quick_Sort(a, p, q-1); // JL: Optimization
Quick_Sort(a, q+1, r);
}
}
static int partition(int *a, int p, int r)
{
assert(p <= r);
if (p == r) // JL: Key change
return p; // JL: Key change
int i = p; // JL: Key change
int j = r + 1;
int x = a[p];
//printf("-->> partition: lo = %d, hi = %d, pivot = %d\n", p, r, x);
while (1)
{
do
{
j--;
//printf("---- partition 1: a[%d] = %d\n", j, a[j]);
} while (x < a[j]); // JL: Key change
do
{
i++;
//printf("---- partition 2: a[%d] = %d\n", i, a[i]);
} while (i <= r && x > a[i]); // JL: Key change
if (i <= j) // JL: Key change
{
//printf("---- partition: swap a[%d] = %d with a[%d] = %d\n", i, a[i], j, a[j]);
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
else
{
// This swap step is crucial.
int temp = a[p]; // JL: Key change
a[p] = a[j]; // JL: Key change
a[j] = temp; // JL: Key change
//dump_partition("a-lo", a, p, j-1);
//printf("a-pivot[%d] = %d\n", j, a[j]);
//dump_partition("a-hi", a, j+1, r);
//printf("<<-- partition: return j = %d; a[%d] = %d; (i = %d; a[%d] = %d)\n", j, j, a[j], i, i, a[i]);
return j;
}
}
}
Extended Sample Input
10
2 1 2 1
3 3 2 0 1
4 5 4 3 2 4
4 3 1 9 3 8
5 3 4 1 9 3 8
9 3 6 4 9 5 1 9 3 3 8
10 3 6 4 9 6 5 1 9 3 3 8
16
3 6 4 9 6 5 1 9 3 3
8 2 1 7 3 5
3
26
3 6 4 9 6 5 1 9 3 3
2 7 8 2 0 8 4 4 7 5
8 2 1 7 3 5
7
96
3 6 4 9 6 5 1 9 3 3
4 0 5 0 7 5 6 3 6 0
1 2 0 7 3 1 7 6 2 3
0 4 6 6 9 8 9 5 3 4
1 9 2 9 2 7 5 9 8 9
4 7 5 8 7 8 5 8 2 7
5 8 2 9 8 3 7 6 5 3
9 1 2 0 3 4 6 5 1 0
2 7 8 2 0 8 4 4 7 5
8 2 1 7 3 5
6
Extended Sample Output
Data set 0:
Before: [0..1] 1 2
After: [0..1] 1 2
Found 1 at 1
Data set 1:
Before: [0..2] 3 2 0
After: [0..2] 0 2 3
Missing 1
Data set 2:
Before: [0..3] 5 4 3 2
After: [0..3] 2 3 4 5
Found 4 at 3
Data set 3:
Before: [0..3] 3 1 9 3
After: [0..3] 1 3 3 9
Missing 8
Data set 4:
Before: [0..4] 3 4 1 9 3
After: [0..4] 1 3 3 4 9
Missing 8
Data set 5:
Before: [0..8] 3 6 4 9 5 1 9 3 3
After: [0..8] 1 3 3 3 4 5 6 9 9
Missing 8
Data set 6:
Before: [0..9] 3 6 4 9 6 5 1 9 3 3
After: [0..9] 1 3 3 3 4 5 6 6 9 9
Missing 8
Data set 7:
Before: [0..15]
3 6 4 9 6 5 1 9 3 3
8 2 1 7 3 5
After: [0..15]
1 1 2 3 3 3 3 4 5 5
6 6 7 8 9 9
Found 3 at 4
Data set 8:
Before: [0..25]
3 6 4 9 6 5 1 9 3 3
2 7 8 2 0 8 4 4 7 5
8 2 1 7 3 5
After: [0..25]
0 1 1 2 2 2 3 3 3 3
4 4 4 5 5 5 6 6 7 7
7 8 8 8 9 9
Found 7 at 19
Data set 9:
Before: [0..95]
3 6 4 9 6 5 1 9 3 3
4 0 5 0 7 5 6 3 6 0
1 2 0 7 3 1 7 6 2 3
0 4 6 6 9 8 9 5 3 4
1 9 2 9 2 7 5 9 8 9
4 7 5 8 7 8 5 8 2 7
5 8 2 9 8 3 7 6 5 3
9 1 2 0 3 4 6 5 1 0
2 7 8 2 0 8 4 4 7 5
8 2 1 7 3 5
After: [0..95]
0 0 0 0 0 0 0 0 1 1
1 1 1 1 1 2 2 2 2 2
2 2 2 2 2 3 3 3 3 3
3 3 3 3 3 3 4 4 4 4
4 4 4 4 5 5 5 5 5 5
5 5 5 5 5 5 6 6 6 6
6 6 6 6 6 7 7 7 7 7
7 7 7 7 7 7 8 8 8 8
8 8 8 8 8 8 9 9 9 9
9 9 9 9 9 9
Found 6 at 57
The code was also tested on some bigger data sets (2097 random entries, etc). Automated check functions are crucial when the data is that big — hence check_sorted() and check_consistency(). They check that the data is output in sorted order, and the conservation property, that all the values in the input appear in the output (as often as they appeared in the input). Sorting is not supposed to add new data or remove pre-existing data.
Upvotes: 2
Reputation: 12392
As pointed out in the comments the loop end test *(array + i) != '\0' for your print loop is an error. array holds normal integers, and C does also consider '\0' to be an integer 0, as it considers all character literal values to be integers, and the comparison is legal, but since this is a (hopefully) sorted array of integers that may have any values (including negative values and 0) it could be that there are multiple 0s in some test data or more likely in this case, no 0s in your test data. If you work out what this code would do in those cases then you should understand the error.
Upvotes: 0
Related Questions
- Segmentation Fault While Sorting - Malloc
- segmentation fault because of sorting function
- segmentation fault in sorting program C
- Segmentation fault in C sorting program
- Sorting strings with insertion sort in C - segmentation fault
- Segmentation fault on little function
- Segmentation Fault With Pointers In Sorted Lists In C
- Having Trouble Segmentation Fault in C
- c: segmentation fault (selection sort)
- segmentation fault, lists in C