如何在C中为整数数组创建快速排序。

huangapple go评论68阅读模式
英文:

How to create quicksort for array of ints in C

问题

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

I'm trying this code:
print_arr is a function that prints all the elements of an array.
swap changes two elements from an array
partition changes the array so that the pivot is between the upper elements and the lower elements, and it returns the position where the pivot is going to be.
quicksort is the function that 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 pivot = arr[low];
    int i = low + 1;
    
    for (int j = i; j < high; j++) {
        if (arr[j] < pivot) {
            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

英文:

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 &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;

void print_arr(int arr[], int lon) {
    for (int i = 0; i &lt; lon; i++) {
        printf(&quot;%d &quot;, 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 &lt; high; j++) {
        if (arr[j] &lt; pivote) {
            swap(&amp;arr[i], &amp;arr[j]);
            i++;
        }
    }

    return (i);
}

void quicksort(int arr[], int low, int high) {
    if (low &lt; 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(&quot;&quot;);

    return 0;
}

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

答案1

得分: 1

以下是要翻译的内容:

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

上述代码仅交换指针,不改变指向的数据。应重写为:

void swap (int *a, int *b) 
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
英文:
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;
}

答案2

得分: 0

Sure, here is the translated code:

为了解决这个问题,我需要更改 'swap' 和 'partition' 函数。以下是解决方案:

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

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

I've translated the code while maintaining its functionality.

英文:

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 &lt; high; j++) {
        if (arr[j] &lt;= pivote) { 
             i++;
             swap(&amp;arr[i], &amp;arr[j]); 
        }
     }
     swap(&amp;arr[i + 1], &amp;arr[high]);
     return (i + 1);
}

答案3

得分: 0

以下是代码的中文翻译部分:

#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("数组为空");
        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("未排序的数组:\n");
    printArray(arr, 100);

    printf(
        "\n\n"
        "已排序的数组:\n"
    );
    sortArray(arr, 100);
    printArray(arr, 100);
    printf("\n");

    free(arr);
}

如果需要进一步的说明或翻译,请告诉我。

英文:

Here is a code i've made a while ago

#include &lt;stdio.h&gt;
#include &lt;stdbool.h&gt;
#include &lt;time.h&gt;
void printArray(int arr[], int _size) {
int i;
for (i = 0; i &lt; _size - 1; i++) {
printf(&quot;%i, &quot;, arr[i]);
}
printf(&quot;%i&quot;, arr[i]);
}
bool isEmpty(int arr[], int _size) {
for (int i = 0; i &lt; _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 &lt; end - 1; j++) {
if (arr[j] &lt;= 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 &gt;= 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(&quot;Array is empty&quot;);
return;
}
quickSort(arr, 0, _size);
}
int main() {
int arr[100];
srand(time(NULL));
for (int i = 0; i &lt; 100; i++) {
*(arr + i) = rand() % 100;
}
printf(&quot;UNSORTED ARRAY: \n&quot;);
printArray(arr, 100);
printf(
&quot;\n\n&quot;
&quot;SORTED ARRAY: \n&quot;
);
sortArray(arr, 100);
printArray(arr, 100);
printf(&quot;\n&quot;);
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]);

huangapple
  • 本文由 发表于 2023年5月14日 21:20:03
  • 转载请务必保留本文链接:https://go.coder-hub.com/76247691.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定