Блинная сортировка (является этот код им, если нет исправьте) - C (СИ)

Узнай цену своей работы

Формулировка задачи:

#include <stdio.h>
 
void flip(int *data, int m, int n) 
{
    int swap, i;
 
    for (i = m; i < --n; i++)
    {
        swap = data[i];
        data[i] = data[n];
        data[n] = swap;
    }
 
}
int main()
{
    int i, j, a, max, moves = 0, length, data[100];
 
    printf("Input length: ");
    scanf_s("%d", &length);
    printf("Input numbers:\n");
 
    if (length < 2)гЂЂ
        return 0;
 
    for (j = 0; j < length; j++) 
    {
        scanf_s("%d", &data[j]);
    }
 
    for (i = length; i > 1; i--)гЂЂ
    {
        max = 0;
        for (a = 0; a < i; a++)   
        {
            if (data[a] > data[max])
                max = a;
        }
 
        if (max == (i - 1))гЂЂ
            continue;

        if (max >= 0) 
        {
            flip(data, max, i);
            moves++;
        }
 
    }
 
    for (j = 0; j < length; j++)
    {
        printf("%d ", data[j]);
    }
    printf("\nFlip: %d ", moves);
    scanf_s("%d", &length);гЂЂ
    return moves;
}
прочитал в хабрахаб об блинной сортировке, попробовал написать показал преподу говорит неправильно, ибо есть действия нарушаюшую условия сортировки (вроде нельзя замену переменных, как в пузырьке)

Решение задачи: «Блинная сортировка (является этот код им, если нет исправьте)»

textual
Листинг программы
#define MAXLEN  100
void pancake_sort(int *arr, int size) 
{
    for (int i = size - 1; i >= 0; --i)
    {
        int pos = i;
        // Find position of max number between beginning and i
        for (int j = 0; j < i - 1; j++)
        {
            if (arr[j] > arr[pos])
            {
                pos = j;
            }
        }
 
        // is it in the correct position already? 
        if (pos == i)
        {
            continue;
        }
 
        // is it at the beginning of the array? If not flip array section so it is
        if (pos != 0)
        {
            flip(arr, pos + 1);
        }
 
        // Flip array section to get max number to correct position    
        flip(arr, i + 1);
    }
}
 
void flip(int *arr, int n)
{
    printf("n: %d\n", n);
    for (int i = 0; i < n; i++)
    {
        --n;
        int tmp = arr[i];
        arr[i] = arr[n];
        arr[n] = tmp;
    }
}
int main(void)
{
    int i, j, a, max, moves = 0, length, data[MAXLEN];
 
    printf("Input length: ");
    scanf("%d", &length);
    printf("Input numbers:\n");
  
    for (j = 0; j < length; j++) 
    {
        scanf("%d", &data[j]);
    }
 
    pancake_sort(data, length);
 
    for (j = 0; j < length; j++)
    {
        printf("%d ", data[j]);
    }
 
    free(data);
    return 0;
}

Объяснение кода листинга программы

  1. В функции pancake_sort происходит сортировка массива методом Блинная сортировка.
  2. Начинается с цикла, который проходит по всем элементам массива, начиная с последнего.
  3. В каждой итерации находится позиция максимального элемента в неотсортированной части массива.
  4. Если максимальный элемент уже находится в правильной позиции, то происходит переход к следующей итерации.
  5. Если максимальный элемент находится не в начале массива, то выполняется перестановка элементов, чтобы он оказался в начале.
  6. После этого выполняется перестановка элементов, чтобы максимальный элемент оказался на своей правильной позиции.
  7. В функции flip происходит перестановка элементов массива.
  8. В функции main происходит ввод длины массива и самих чисел для сортировки.
  9. Затем вызывается функция pancake_sort для сортировки введенных чисел.
  10. Выводится отсортированный массив.
  11. В конце программа возвращает 0, что означает успешное выполнение.

Оцени полезность:

11   голосов , оценка 4.182 из 5
Похожие ответы