How to create quicksort for array of ints in C

Question

I'm trying to design a function quicksort in C which sorts a array of ints in a decendent way.

I'm trying this code: print_arr ista a function that prints all the elements of an array. swap changes to elements from an array partition changes the array so to have have the pivote in the between the upper elements and the lower elements, and it returns the position where the pivote is going to be. quicksort is the function which sorts the array. Main is the main function where I create the array to sort.

#include <stdlib.h>
#include <stdio.h>

void print_arr(int arr[], int lon) {
    for (int i = 0; i < lon; i++) {
        printf("%d ", arr[i]);
    }
}

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

int partition(int arr[], int low, int high) {
    int pivote = arr[low];
    int i = low + 1;
    
    for (int j = i; j < high; j++) {
        if (arr[j] < pivote) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }

    return (i);
}

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

int main() {
    int arr[5] = {3, 4, 1, 2, 5};
    quicksort(arr, 0, 5);

    print_arr(arr, 5);
    puts("");

    return 0;
}

So I expect an output like: 1 2 3 4 5 but I get: 3 4 1 2 5

Your `swap` function does absolutely nothing. It would have to be `void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }`. Can't you use the built-in [`qsort`](https://en.cppreference.com/w/c/algorithm/qsort) function? — Ted Lyngmo, May 14 '23 at 13:22
This is a very good time to learn how to [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your programs. For example by using a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through the code line by line while monitoring variables and their values. — Some programmer dude, May 14 '23 at 13:40
Also, once you have learned about quicksort, and gotten your code to work (and you understand what the problem was, and how it really works) then throw it all away. In the future don't write your own sorting, Use the standard [`qsort`](https://en.cppreference.com/w/c/algorithm/qsort) function instead. — Some programmer dude, May 14 '23 at 13:41

score 1 · Accepted Answer · answered May 14 '23 at 13:27

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

The above code merely exchanges pointers and leaves the pointed to data unchanged. It should be rewritten as:

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

score 0 · Answer 2 · answered May 14 '23 at 14:04

To solve it I needed to change the 'swap' and 'partition' functions. This is a solution:

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

int partition(int arr[], int low, int high) {
    int pivote = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivote) { 
             i++;
             swap(&arr[i], &arr[j]); 
        }
     }
     swap(&arr[i + 1], &arr[high]);
     return (i + 1);
}

score 0 · Answer 3 · answered May 14 '23 at 14:10

Here is a code i've made a while ago

#include <stdio.h>
#include <stdbool.h>
#include <time.h>

void printArray(int arr[], int _size) {
    int i;

    for (i = 0; i < _size - 1; i++) {
        printf("%i, ", arr[i]);
    }

    printf("%i", arr[i]);
}

bool isEmpty(int arr[], int _size) {
    for (int i = 0; i < _size; i++) {
        if (arr[i]) {
            return false;
        }
    }

    return true;
}

void swap(int arr[], int root, int child) {
    int aux = arr[root];
    arr[root] = arr[child];
    arr[child] = aux;
}

int partition(int arr[], int start, int end) {
    int i = start - 1, pivot = arr[end - 1];

    for (int j = start; j < end - 1; j++) {
        if (arr[j] <= pivot) {
            i += 1;
            swap(arr, j, i);
        }
    }

    swap(arr, i + 1, end - 1);
    return i + 1;
}

void quickSort(int arr[], int start, int end) {
    if (start >= end) {
        return;
    }

    int pi = partition(arr, start, end);
    quickSort(arr, start, pi);
    quickSort(arr, pi + 1, end);
}

void sortArray(int arr[], int _size) {
    if (isEmpty(arr, _size)) {
        printf("Array is empty");
        return;
    }

    quickSort(arr, 0, _size);
}

int main() {
    int arr[100];

    srand(time(NULL));
    for (int i = 0; i < 100; i++) {
        *(arr + i) = rand() % 100;
    }

    printf("UNSORTED ARRAY: \n");
    printArray(arr, 100);

    printf(
        "\n\n"
        "SORTED ARRAY: \n"
    );
    sortArray(arr, 100);
    printArray(arr, 100);
    printf("\n");

    free(arr);
}

It works fine. In case you don't know the size of the array, you can figure it out using size_t n = sizeof(arr) / sizeof(arr[0]);

How to create quicksort for array of ints in C

3 Answers3