Отсортировать числа в массиве лексикографически - C (СИ)

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

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

Есть числа. Пусть это числа 102 211 121 010(Все числа одного размера N. В данном примере N=3) В массиве они записаны следующим образом 1 0 2 2 1 1 1 2 1 0 1 0. Нужно их отсортировать лексикографически в этом массиве. (010 102 121 211) То есть записать так 0 1 0 1 0 2 1 2 1 2 1 1. Подайте идею как это можно сделать ?

Решение задачи: «Отсортировать числа в массиве лексикографически»

textual
Листинг программы
#include <cstdio>
using namespace std;
void swap(int & a, int &b)
{
    int temp=a;
    a=b;
    b=temp;
}
void perest(int mas[],int & i,int & j,int n)
{
 
for (int k=0;k<n;k++)
swap(mas[k+i],mas[k+j]);
 
}
int sravnenie (int mas[],int  i, int  j,int n)
{
    for (int k=0;k<n;k++)
        {if (mas[i+k]<mas[j+k]) return 1;
        else if (mas[i+k]>mas[j+k]) return 0;
        }
   
        return 0;
}
void sort(int mas[],int nach,int  raz,int n)
{
int kolvo_chisel=(raz+n-nach)/n;
int a=nach+(kolvo_chisel/2)*n;
int i=nach,j=raz;
do
{
    
    while(sravnenie(mas,i,a,n )) i+=n;
while (sravnenie(mas,a,j,n ) ) j-=n;
if (i<=j)
{
if (i==a) a=j;
else if(j==a) a=i;
perest(mas,i,j,n);
i+=n;j-=n;
}
}while(i<=j);
if (i<raz) {sort(mas,i,raz,n);}
if (j>nach) {sort (mas,nach,j,n);}
}
int main()
{
int a[]={1, 0 ,2 ,2, 1 ,1, 1 ,2 ,1 ,0 ,1 ,0};
int n=3;
sort(a,0,12-n,n);
for (int i=0;i<12;i++)
printf("%d ",a[i]);
return 0;
}

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

В данном коде реализована сортировка массива методом выборочного (сегментного) сортирования. Список действий, которые происходят в коде:

  1. Сравнение элементов массива и выбор опорного элемента
    • Функция sravnenie сравнивает элементы массива mas с индексами i и j и возвращает 1, если элемент с индексом i меньше, и 0 в противном случае. Это нужно для определения, в какую сторону необходимо «подровнять» массив при каждом проходе цикла.
  2. Перестановка элементов массива
    • Функция perest меняет местами элементы массива mas с индексами i и j.
  3. Основной цикл сортировки
    • Внешний цикл do организует проходы по массиву до тех пор, пока есть элементы, которые необходимо переставить.
    • Внутренний цикл while отслеживает границы, внутри которых необходимо искать элементы для перестановки.
    • Если текущий элемент меньше опорного, то цикл смещается вправо, иначе - влево.
    • Если границы пересеклись, то это означает, что опорный элемент был найден, и элементы с его индексами были переставлены местами.
  4. Рекурсивная сортировка
    • Если после прохода по массиву остались неотсортированные элементы, то сортировка повторяется рекурсивно для соответствующих диапазонов.
  5. Ввод-вывод данных
    • В функции main создаётся массив a с десятью элементами.
    • Массив сортируется с помощью функции sort.
    • Отсортированный массив выводится на экран с помощью цикла for и функции printf.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

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

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