Отсортировать числа в массиве лексикографически - 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; }
Объяснение кода листинга программы
В данном коде реализована сортировка массива методом выборочного (сегментного) сортирования. Список действий, которые происходят в коде:
- Сравнение элементов массива и выбор опорного элемента
- Функция
sravnenie
сравнивает элементы массиваmas
с индексамиi
иj
и возвращает 1, если элемент с индексомi
меньше, и 0 в противном случае. Это нужно для определения, в какую сторону необходимо «подровнять» массив при каждом проходе цикла.
- Функция
- Перестановка элементов массива
- Функция
perest
меняет местами элементы массиваmas
с индексамиi
иj
.
- Функция
- Основной цикл сортировки
- Внешний цикл
do
организует проходы по массиву до тех пор, пока есть элементы, которые необходимо переставить. - Внутренний цикл
while
отслеживает границы, внутри которых необходимо искать элементы для перестановки. - Если текущий элемент меньше опорного, то цикл смещается вправо, иначе - влево.
- Если границы пересеклись, то это означает, что опорный элемент был найден, и элементы с его индексами были переставлены местами.
- Внешний цикл
- Рекурсивная сортировка
- Если после прохода по массиву остались неотсортированные элементы, то сортировка повторяется рекурсивно для соответствующих диапазонов.
- Ввод-вывод данных
- В функции
main
создаётся массивa
с десятью элементами. - Массив сортируется с помощью функции
sort
. - Отсортированный массив выводится на экран с помощью цикла
for
и функцииprintf
.
- В функции
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д