CODEWITHSUNDEEP
csortingquicksort
Prateek Mathur
Prateek Mathur

Reputation: 333

Quick Sort algorithm behaving strangely

This is a program which attempts to sort an array using the quick sort algorithm. All seems to be fine, except that the output is not correct.

(Try the program for n=5, and then n=10. It works correctly for the former, but not the latter.)

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

int partition(int arr[], int left, int right)   {
    int i = left, j = right;
    int temp;

    //Choosing the middle element as the pivot
    //int pivot=arr[left];
    int pivot = arr[(left+right)/2];

    while (i <= j) {
        while (arr[i] < pivot) {i++;}
        while (arr[j] > pivot) {j--;}

        if (i <= j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }

    return i;
}

void quick_sort(int arr[], int p, int r)   {
    if (p<r)   {
       int q=partition(arr, p, r);
       quick_sort(arr, p, q-1);
       quick_sort(arr, q+1, r);
    }
}

int main()  {
    int values[100], n, i;

    //clrscr();

    printf("Enter no. of elements ");
    scanf("%d", &n);

    if (n>100) {
        printf("Invalid input. Exiting now");
        //getch();
        return 0;
    }

    for (i=0; i<100; i++) values[i]=0;

    printf("Enter the numbers\n");
    for (i=0; i<n; i++) scanf("%d", &values[i]);

    printf("The numbers you entered are\n");
    for (i=0; i<n; i++) printf("%d ", values[i]);

    printf("\n");

    quick_sort(values, 0, n-1);

    printf("Numbers after sorting are\n");
    printf("(The output might not be the expected one (Be careful).\n");
    for (i=0; i<n; i++) printf("%d ", values[i]);

    //std::cin.get();

    return 0;
}

Upvotes: 2

Views: 192

Answers (2)

isolat
isolat

Reputation: 9

is better to use the std sort from algorithm.h :

http://www.cplusplus.com/reference/algorithm/sort/

Upvotes: -1

charliehorse55
charliehorse55

Reputation: 1990

There are two problems. First, the comparison i <= j is wrong. If i == j, you should not swap an element with itself. This should be changed to i < j in both places. Secondly, you should not move the i and j array indicies along after swapping. If it is the last swap, this pushes i past the actual pivot and causes your error. 

int partition(int arr[], int left, int right)   {
    int i = left, j = right;
    int temp;

    //Choosing the middle element as the pivot
    //int pivot=arr[left];
    int pivot = arr[(left+right)/2];

    while (i < j) {
        while (arr[i] < pivot) {i++;}
        while (arr[j] > pivot) {j--;}

        if (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    return i;
}

Upvotes: 2

Related Questions