Quicksort Algorithm (Recursion)

Question

I made a quicksort algorithm out of the visual presentation of the algorithm in youtube that I watched, but my recursion does not work at all. :( If I commented out these 2 lines,

quicksort(array,0,start-1);
quicksort(array,start+1,temp);

.. The program does not crash and the output becomes 2,1,3,5,4 which is partly correct.. But it crashes when it enters the recursion. After the whole while loop, the start becomes the same as the end..

#include <stdio.h>
#include <conio.h>

void swap(int *a, int *b){

int temp = *a;
*a = *b;
*b = temp;
}

void quicksort(int *array, int start, int end){

int pivot = start;
int temp = end;     
while(start != end){

if(pivot==start){
    if(array[pivot] > array[end]){
    swap(&array[end],&array[pivot]);
    pivot = end;
    start++;
    }
    else
    end--;
}
else{
if(array[pivot] < array[start]){
    swap(&array[start],&array[pivot]);
    pivot = start;
    end--;
}  
else
start++;   

}               
}

quicksort(array,0,start-1);
quicksort(array,start+1,temp);
}




main(){

int x[5] = {3,1,5,2,4};
int i;
quicksort(x,0,4);
for(i=0;i<5;i++)
printf("%d ", x[i]);
getch();
}

I made revision of the code.. I added if(start==end) return; // for terminating condition. But it encounters error when it enters the second recursion which is quicksort(array,start+1,temp); — Xegara
– Xegara, Commented Apr 5, 2012 at 10:58

Nitram · Accepted Answer · 2012-04-05 10:48:52Z

2

What is missing is the point to cancel the algorithm. If you check the control flow of you function, you'll see that on every path the application can walk though this function the quicksort function is called again. Finding out when you are done is simple. You just need to exit the function without calling quicksort again in case the parameters start and end are equal. That should do the trick.

answered Apr 5, 2012 at 10:48

Nitram

6,7462 gold badges26 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

James Kanze Over a year ago

I don't think the arguments to the first recursive call are correct either. (I've not verified the rest, but if start isn't 0, then the first call ends up passing a lower bound less than the segment we're working on.)

Xegara Over a year ago

Thank you :) hm.. I can't think of any other way because the quicksort algorithm is a divide and conquer algorithm, once the first pivot is sorted (usually ends up in the middle), quicksort will occur again in the left side and the right side of the pivot and so on until the list is sorted.. :)

Xegara Over a year ago

You were right about the lower bound which is zero of being wrong. I got it working now. Thank you so much!! :)

jpalecek · Accepted Answer · 2012-04-05 10:48:16Z

0

To the crasher: Your code is missing the terminating condition for the recursion. It means that even if the input range is empty, you still enter the recursive calls (with negative indicies to the array, which is probably causing the crash). You should add condition like

if(there's at most 1 element in the input range)
  return; // already sorted

answered Apr 5, 2012 at 10:48

jpalecek

47.9k7 gold badges105 silver badges147 bronze badges

Comments

user1596193 · Accepted Answer · 2013-02-27 15:38:29Z

QuickSort Algorithm:

    - QuickSort( A[], l, r)
      - P = A[l] // Select pivot as the beginning element from array or you can do better //with good pivots.
      - i = l + 1 // index i to be next of pivot
      - for j = l + 1 to r
         - if A[j] < P
           - swap (A[j], A[i])
           - increment i
         - end if
     - end for
     - swap (A[i-1], A[l]);
     -- Call recursive on left partitioned array
     -- Call recursive on right partitioned array.




// QuickSort_2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#define ARR_SIZE            200
#define PR_ARR_SIZE         200
unsigned int input_arr[ARR_SIZE];

void swap(unsigned int *a, unsigned int *b)
{
    unsigned int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void print_input(unsigned int input[], unsigned int l, unsigned  int n)
{
    unsigned int i;
    for (i = l; i < n; i++)
        printf("%d ", input[i]);
    printf("\n");
}

void QuickSort(unsigned int input[], unsigned int l, unsigned int r)
{
    unsigned int i = l + 1, j;
    unsigned int pivot = input[l];
    if (l + 1 < r) {
        for (j = l + 1; j < r; j++) {
            if (input[j] < pivot) {
                swap(&input[j], &input[i]);
                i++;
            }
        }
        swap(&input[i - 1], &input[l]);

        QuickSort(input, l, i);
        QuickSort(input, i, r);
    }
}


int _tmain(int argc, _TCHAR* argv[])
{
    unsigned int i = 0;
    unsigned int val;
    FILE *fp;

    errno_t err = fopen_s(&fp, "IntegerArray.txt", "r+");
    if (err) {
        printf("unable to open a file\n");
        return -1;
    }
    while (fscanf_s(fp, "%ld\n", &val) != EOF) {
        input_arr[n++] = val;
    }

    print_input(input_arr, 0, n);
    QuickSort(input_arr, 0, n);
    print_input(input_arr, 0, n);

    return 0;
}

Put these values in "IntegerArray.txt" file and 

2
3
4
5
6
10
11
12
1
17
18
19
20
7
8
9
13
14
15
16

Collectives™ on Stack Overflow

Quicksort Algorithm (Recursion)

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related