CODEWITHSUNDEEP
c++
Xegara
Xegara

Reputation: 563

Quicksort Algorithm (Recursion)

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();
}

Upvotes: 1

Views: 9103

Answers (3)

user1596193
user1596193

Reputation: 100

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

Upvotes: 0

Nitram
Nitram

Reputation: 6716

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.

Upvotes: 2

jpalecek
jpalecek

Reputation: 47762

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

Upvotes: 0

Related Questions