Рубрики

C Программа для сортировки блинчиков

По несортированному массиву отсортировать по массиву. Вам разрешено делать только следующую операцию над массивом.

flip(arr, i): Reverse array from 0 to i 

/ * C программа для сортировки блинов * /
#include <stdio.h>
#include <stdlib.h>

  
/ * Обращает arr [0..i] * /

void flip(int arr[], int i)

{

    int temp, start = 0;

    while (start < i) {

        temp = arr[start];

        arr[start] = arr[i];

        arr[i] = temp;

        start++;

        i--;

    }

}

  
/ * Возвращает индекс максимального элемента в arr [0..n-1] * /

int findMax(int arr[], int n)

{

    int mi, i;

    for (mi = 0, i = 0; i < n; ++i)

        if (arr[i] > arr[mi])

            mi = i;

    return mi;

}

  
// Основная функция, которая сортирует данный массив с помощью flip
// операции

int pancakeSort(int* arr, int n)

{

    // Начинаем с полного массива и по одному уменьшаем

    // текущий размер на единицу

    for (int curr_size = n; curr_size > 1; --curr_size) {

        // Найти индекс максимального элемента в

        // arr [0..curr_size-1]

        int mi = findMax(arr, curr_size);

  

        // Переместить максимальный элемент в конец текущего массива

        // если это еще не в конце

        if (mi != curr_size - 1) {

            // Чтобы переместиться в конец, сначала переместим максимальное число

            // к началу

            flip(arr, mi);

  

            // Теперь перемещаем максимальное число, чтобы закончить, обращая

            // текущий массив

            flip(arr, curr_size - 1);

        }

    }

}

  
/ * Утилита для печати массива размером n * /

void printArray(int arr[], int n)

{

    for (int i = 0; i < n; ++i)

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

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = { 23, 10, 20, 11, 12, 6, 7 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    pancakeSort(arr, n);

  

    puts("Sorted Array ");

    printArray(arr, n);

  

    return 0;

}

Выход:

Sorted Array 
6 7 10 11 12 20 23

Пожалуйста, обратитесь к полной статье о сортировке блинов для более подробной информации!

Рекомендуемые посты:

C Программа для сортировки блинчиков

0.00 (0%) 0 votes