C Lang: быстрая сортировка 5 элементов, но не сортировка 10 элементов - PullRequest
Новая
       8

C Lang: быстрая сортировка 5 элементов, но не сортировка 10 элементов

0 голосов
/ 09 марта 2020

Меня смущает, почему код сортирует только 5 элементов, но не 10 элементов. Этот метод был описан мне во время моего визита в кабинет с моим профессором. Поэтому я следовал его инструкциям, когда закодировал это. Может кто-нибудь помочь мне решить эту проблему? Мой код работает, но он не работает с большим массивом. Я знаю, что уже слишком поздно, чтобы кто-то мог помочь, но я просто хочу понять, что я сделал в этом коде.

Спасибо 

/* Homework3.c
Qucksort arrays
Jared DaRocha
3/1/2020

 */


#include <stdio.h>// preprocessor 

int partition(int arr[], int first, int end);// function declaration

void quickSort(int arr[], int first, int end);// function declaration

int main(void)// beginning of main

{
    //Data
    int array[5];// creates an array of 5 elements
    int size = sizeof(array) / sizeof(array[0]); // calculates size of the array


    // prompt user to input data to input int the array
    printf("Enter 5 numbers to add in the array");
    // prompts user to input 10 numbers
    for(int i =0;i<size; i++)
    {
      scanf("%d", &array[i]);// stores user-defined data into the array
    }


    // call the function to sort the array
    quickSort(array, 0, size -1);


    // prints array 
    for (int i = 0; i < size; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}


int partition(int arr[], int low, int high)// Function declaration
{
    //Data
    int partition = arr[low]; // partition number


        // infinite for loop
        for (;;)
        {
          // decrement high while partition is smaller than element of high
            while(partition <arr[high]) 
            {

              high--;


            }


            // if partition is greater than element of high, swap high with low element since low element is the pivot
            if(partition > arr[high]){
              int temp = arr[low];

              arr[low] = arr[high];
              arr[high] = temp;
              low++;

            }           
            // increment low while partition is greater than element of low
            while(partition > arr[low])
            {

              low++;

            }

            // swap low and next element in the right if  partition is less than element of low
            if(partition < arr[low])
            {
              int temp = arr[low];
              arr[low] = arr[low+1];
              arr[low+1] = temp;
            }

            // if low is same as high then  exit loop
            if(high == low)
            {
              break;
            }


    }


    return low;
}

void quickSort(int arr[], int first, int end) // function definition
{
    if (first < end) 
    {
        int partitionIndex = partition(arr, first, end);
        quickSort(arr, first, (partitionIndex - 1));
        quickSort(arr, (partitionIndex+1 ), end);
    }
}

`

1 Ответ

0 голосов
/ 10 марта 2020

Если вы проверите быструю сортировку алгоритма, вы обнаружите, как массив делится на два среза, которые не перекрываются, но также не оставляют ни одного элемента. Вы делаете это, просто между двумя срезами, вы оставляете один элемент. Вы делите массив на два среза и один элемент массива, который не участвует в рекурсивных вызовах других срезов .... и это неверно. То, что вы знаете, это то, что все элементы нижнего среза меньше токена, а остальные больше или равны токену ... но точкой деления может быть любой элемент из соответствующей части массива.

Кстати, код или раздел совершенно неверный. Сначала вы выбираете один элемент, который будет действовать как токен, вы можете выбрать его как любой элемент массива или как среднее значение для всех из них, это не имеет значения ... вы не собираетесь помещать его в массив , затем поиск по конечным элементам, которые находятся под массивом, и поиск по начальным элементам, которые находятся над токеном, если у вас есть одна такая пара, переключите их, но вы обмениваетесь найденными элементами с токеном, который не только не делать то, что ожидается, но вводит копии токена (и изменяет его значение), который будет sh вашего массива.

Вы не ищете элемент массива ... вы ищете место (между соседними элементами), где разделить ваш массив, и подмассивы будут от начала, до пос-1 и от пункта к концу (или от начала до пункта, затем от пункта + 1 до конца), но не игнорируйте центральный элемент, потому что вы знаете, что он принадлежит массиву, но токен не нужен.

...